Production Scheduling Approaches
Read these sections, which highlight key problems in production scheduling. How can job sequencing and priority rules help to alleviate the key problems? Can you identify the different rules that affect job sequencing and priority rules in operations management?
4. Meta-heuristics for solving the JSSP
4.4. Electromagnetism like Method (EM)
The Electromagnetic Like Algorithm is a population based meta-heuristics proposed by Birbil and Fang to tackle with combinatorial optimisation problems. Algorithm is based on the natural law of attraction and repulsion between charges (Coulomb's law). EM simulates electromagnetic interaction. The algorithm evaluates fitness of solutions considering charge of particles. Each particle represents a solution. Two points into the space had different charges in relation to what electromagnetic field acts on them. An electrostatic force, in repulsion or attraction, manifests between two points charges. The electrostatic force is directly proportional to the magnitudes of each charge and inversely proportional to the square of the distance between the charges. The fixed charge at time iteration (t) of particle i is shown as follows:
E12
Where
The particles move along with total force and so diversified solutions are generated. The following formulation is the resultant force of particle
E13
The following notes described an adapted version of EM for JSSP. According to this application, the initial population is obtained by choosing randomly from the list or pending tasks, as for the feasibility of solution, particles' path. The generic pseudo-code for the EM is reported in figure 6. Each particle is initially located into a source node (see disjunctive graph of figure 2). Particle is uniquely defined by a charge and a location into the node's space. Particle's position in each node is defined in a multigrid discrete set. While moving, particle jumps in a node based on its attraction force, defined in module and direction and way. If the force from starting line to arrival is in relation of positive inequality, the particles will be located in a plane position in linear dependence with force intensity. A selection mechanism could be set in order to decide where particle is directed, based on node force intensity. Force is therefore the resultant of particles acting in node. A solution for the JS is obtained only after a complete path from the source to the sink and the resulting force is updated according to the normalized makespan of different solutions.
Figure 6.
The Electromagnetic like
Method; 6a. the EM pseudo code; 6b. the flow chart of a general EM
procedure.