IFAC
Copyright © IFAC Intelligent Manufacturing Systems, Poman, Poland, 2001
c:
0
C>
Publications www.elsevier.comlIocate/ifac
SCHEDULING AND SEQUENCING JOBS ON MACHINES BY WAY OF SIMULATED ANNEALINGBASED HEURISTICS
Jose Fidel Torres Delgado, Andres Troncoso, Pascal Blanc
Universidad de Los Andes, Departamento de Ingenieria Industrial, Bogota, COLOMBIA Email:
[email protected] , Email:
[email protected] Email:
[email protected]
Abstract: The following paper addresses the problem of scheduling and sequencing a number of jobs to be processed on a set of identical machines. To find solutions to this problem, a set of models is studied with the purpose of maximizing the operational margin of autonomy of the scheduled jobs in the proposed solutions. The article proposes two methods to solve the problem. The first is based on an integer programming model ; the second, on a simulated annealing method supported by a neighborhood heuristic in which two variants are studied: one with a coherence verification mechanism, the other without. Copyright © 20011FAC Keywords: Manufacturing Modeling, Advanced Manufacturing Technology. Scheduling
I.
INTRODUCTION
Some ordinary production programming practices do not respond to competitive demand because most planning programs are computationally inefficient when it comes to obtaining an optimum solution. The present article is intended to resolve the problem of scheduling and sequencing n independent jobs on m machines. The objective is to maximize the Total Load Margin Plan (Erschler, 1976; Erschler and Thuriot, 1992; Torres, 1995) and to determine the Real Load Rate of the machines and the Load Margin Rate for each operation, according to the earliest starting date, the latest completion date and the duration of the job. Two approaches are used. One involves an integer programming method, the other a simulated annealing method. The latter is based on a neighborhood heuristic where two plans are evaluated: one with a coherence verification mechanism and the other without. The paper is organized in the following way: in Section 2, the problem is defined and its terminology and mathematical formulation are presented. A brief description of the methods, the solution procedure and the parameters of the heuristics are given in Section 3. Computational experiments and their results are given in Section 4, followed by a
discussion of the results in Section 5.
2.
DEFINITION OF THE PROBLEM
Let us consider a set of n independent jobs (I , 2, 3,...n) to be scheduled on m identical machines, denoted as 1, 2, 3 ... m, respectively. Eachjob has an index i, in accordance with the number assigned to the job, and has an earliest starting date C(i), a latest completion date F(i) and a duration D (i), denoted respectively as DJ, D 2. D 3 •• •D 11. All the data are assumed to be integer values. The machines fulfill their function completely. Consequently, there are no unfinished jobs. The objective function used in the formulation is the Total Load Margin (TLM) defined as: TLM=I(F(i)C(i)D(i))
(1)
The problem consists of finding the optimum schedule, one in which the Total Margin of the plan is maximized. This is represented graphically as follows.
!
TI
I
T2 T3
F'n = Fn F' nI = Min { F'n  Dn , Fn_1 }
I I
• •
I I
I
MI
F'I = Min {F'z  O2 , Fd
M2 M3
Constraints: C(i)
~
C(i)
Vi,
(3 .1)
F'(i)
~
F(i)
Vi,
(3 .2)
Fig. I. Scheduling the jobs on the machines. Inasmuch as the problem is reduced to scheduling the jobs on a set of machines, the objective function becomes a scheduled function and is defined by the maximum limit of the Total Load Margin Plan.
Z(i' k)= {~
If job i is assigned to machine k Otherwise
(3 .3)
(2) W(i , j) = Therefore, the objective function is: Maximize
L (F' (i) 
(3)
The job scheduling is represented by the following programming scheme (Torres, 2000).
F'(i)
Vi ,
(3 .5)
L m
Z(i,k) = I
(3.6)
Vi
k=!
Fl
C] I
C,
~
Constraint (3.1) shows the earliest starting date for all the jobs is superior or equal to the earliest starting date limit. Constraint (3 .2) indicates the latest completion date for all the jobs is inferior or equal to the latest completion date limit. The machine jobscheduling constraint is given by (3 .3), in the cast of n jobs on m machines. Inasmuch as each job is assigned to one and only one machine,
F' (i) = The latest completion date of job i, after the other jobs have been scheduled C'(i) = The earliest starting date for job i, after the other jobs have been scheduled D(i) = The duration of job i.
cl
Otherwise
C(i) + D(i)
Where :
V I;
If job i comes before job j
(3.4)
C' (i)  D(i»
Cl ~ F, C2 I I
{~
C,
I
V
\/
t
F, Cl' Fl'C]'
Constraint (3.4) represents coordination of the jobs on each machine, where Z(i ,k) E (0, 1) and W(i,j) E (0,1) are, therefore, binary decision variables. For coherence between the starting date and the completion date of each operation, constraint (3.5) must be taken into account, as the difference between the latest completion date and the earliest starting date must allow for the operation to be conducted.
F]
F,
F]' C,'
Fig 2. Programming scheme after scheduling the jobs on the machines.
3. METHODS TO SOL YE THE PROBLEM
If n jobs are scheduled on m machines in the sequence il < iz < i3 < i n < i n I, which represents the order of the jobs, the foregoing scheme can be expressed as :
3.1. Integer Programming
Cl = Cl C 2 = Max {C l + D I , C 2 } C 3 = Max {C 2 + O 2, C 3 }
A mixed integer programming model in GAMS was employed to solve the production scheduling problem defined by equations (3) through (3.5) . Coordination between the starting dates (Pinedo, 1995) of two operations is given by:
• •
Cn
= Max
{ C n. 1 + 0 111 , C 11 }
(B + D(i»
66
* (I
 Z(i ,k»
+ (B + D(i» * (1 Z(j,k» +
(8 + D(i)) * (I  W(i,j» + C(j)  C(i) ~ D(i) Vi,j ,k i*j. (4.a)
Select a solution eo E E
Where j is another index for the operations or jobs and 8 represents a larger integer Additionally, it has: (8 + D(i» (8 + D(i»
Vi ,j ,k
Select the initial temperature T, The number of iterations N in each temperature and the final temperature. Tr.
* (I  Z(i,k» + (8 + D(i» * (1 Z(j,k» + * W(i ,j) + C(i)  C(j) ~ D(j)
i*j.
(4.b)
Coordination between the completion dates of the two operations is calculated as follows :  Z(i,k» + (8 + D(i» * (1 Z(j ,k» + (8 + D(i»  W(i,j» + F'(j)  F'(i) ~ D(j) V i,j ,k i * j. (S.a)
(8 + D(i))
* (I * (I
Select a solution e)
If operations i and j are both assigned to machine k, and i is accomplished before j, operation i has a latest completion date inferior to that of j, less the duration of its operation.
eo = e) ho = h) Si ho> h·, then: h" = ho v e· = en
* (I  Z(i ,k» + (8 + D(i» * (1 Z(j ,k» + (8 + D(i)) * W(i ,j) + F'(i)  F'(j) ~ D(i) (8 + D(i»
Vi ,j,k
i*j.
E, in the neighborhood of eo
Calcul ate P = exp( ~ / T) Generate a random numberxE U(O, I ) If x::; P, then: eo = e) ho = hi
no
Additionally:
E
(S.b)
If operations i and j are both assigned to machine k, and j is accomplished before i, operation j has a latest completion date inferior to that of i, less the duration of its operation.
3.2 The Simulated Annealing Method Problem: Max f( e)
The simulated annealing method is based on a random search technique regulated by following a control parameter known as temperature, where other approximate solutions to combinatorial optimization problems can be obtained (Pham and Karaboga, 2000). This method uses an improved solution algorithm, beginning with an initial configuration as the first solution and specifying a base temperature. Obtaining a random change in the initial condition gives a new solution, as described in Fig 3. The value of the objective function (h) is analogous to the energy in the physical process of tempering. In changing the initial condition, the algorithm finds hI. Therefore, S.t. eE E
>+<
STOP >
Fig 3. Simulated Annealing Flow Chart in a maximization problem, ifhl > h, the new solution is accepted. However, if hi < h, the method accepts the new (but less effective) solution with a probability according to by exp(~h/T) , with ~h = hhJ. to prevent solutions from remaining at local optimums. The following are the design parameters defined to work with the experiments applied to the neighborhood simulated annealing heuristic. a)
Real Load Rate of the machines (RLR):
RLR=
67
L .
D(i) . *100 «Hmax  Hmm) * m)
Where: Hmax = The maximum limit of the planning horizon . Hmin = The minimum limit of the horizon D (i) = Duration of job i. The Real Machine Load Rate is defined as the relationship between the total load and the real capacity of the machines in the planning horizon.
Select Kb and a position in Kb
Allocate i in the selected posi tion of Kb
b) Load Margin Rate of the operation(LMR): LMR = (F(i)  C(i)  D(i» 1 D(i)
* 100
Verify coherence of the new location
NO
The Load Margin Rate of the operation is the relationship between the autonomy margin of the job and its duration.
I I I I I
I I
The following performance measure is also defined:
IL _______ __ _
c) Total Margin Limit Rate (TMLR):
TMLR =
L
~
(F'(i)  C'(i)  D(i»
L
* 100 (F(i)  C(i)  D(i»
The Total Margin Limit Rate is the relationship between the total autonomy margin assigned to the machines and the maximum limit of the total margin plan
Fig 4. Verify coherence of the new locati on
3.3 Development o/the Heuristics •
4. TESTING AND RESULTS
Heuristic without coherence verification
4.1 Integer Programming Method
It involves the following steps: I) 2) 3) 4) 5) •
The following jobs were established to employ the integer programming model in GAMS .
Select machine Ka Select job i in machine Ko Select machine Kb Select j position in machine Kh . Schedule job i at j position in machine Ko.
Table l. Modeling parameters in GAMS. C(i) 0
F(i)
O(i)
I
9
2
2
I
3
2
12 14 10 12 15 15 19 16 17 17 16 20 20 18
I I
N° of Jobs
Coherence Verification Heuristic
This heuristic adds the following steps to the foregoing algorithm : 6) Verify coherence in scheduling job i at j position in machine Ko The process is:
4
4
5 6 7 8 9 10
4 5 6 7
II
9
12 13 14 15
10 10 13 15
8
8
2 2 I I I
2 I
2
2 I
2 I
The result are shown in the following table:
68
Table 11 Maximum Limit of the Total Load Margin and Iteration Length.
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
Maximum Limit of the Total Load Margin 3 N° of Machines 5 38 (00:005) NS (00:03) 5 N° of 7 NS (00:04) NS (00:03) Operations 10 NS (00:05) NS (00:07) 15 NS (00:25) NS (00:27) NS : No solution found. 4.}
Simulated Annealing Heuristics
To test the two simulated annealing heuristics proposed for the problem, different groups of experiments were developed with varying design parameters : Number of Operations (Num. Operat.), Number of Machines (Num . Mac .), Real Load Rate (RLR) and Load Margin Rate (LMR) of the operation . These groups of experiments appear in Table IL with the coherence verification option (Opt. Vec = I), if there is verification, and Opt. Vec=O. if there is not.
Num. lNum. Ooerat mac
RLR
Dur
Min Mare
Max Mare
I 2 3 4 5 6 7 8 9 10 11 12
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 I I I I I I I I I I I
15 15 15 15 15 15 15 15 15 25 25 25 25 25 25 25 25 25 40 40 40 40 40 40 40 40 40 15 15 15 15 15 15 15 15 15 25 25
40 40 40 60 60 60 80 80 80 40 40 40 60 60 60 80 80 80 40 40 40 60 60 60 80 80 80 40 40 40 60 60 60 80 80 80 40 40
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
2 5 10 2 5 10 2 5 10 2 5 10 2 5 10 2 5 10 2 5 10 2 5 10 2 5 10 2 5 10 2 5 10 2 5 10 2 5
5 10 20 5 10 20 5 10 20 5 10 20 5 10 20 5 10 20 5 10 20 5 10 20 5 10 20 5 10 20 5 10 20 5 10 20 5 10
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
3 3 3 3 3 3 3 3 3 5 5 5 5 5 5 5 5 5 8 8 8 8
8 8 8 8 8 3 3 3 3 3 3 3 3 3 5 5
5 5 5 5 5 5 5 8 8 8 8 8 8
40 60 60 60 80 80 80 40 40 40 60 60 60 80 80 80
8 8 8
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 2 5 10 2 5 10
2 5 10 2 5 10 2 5 10
20 5 10 20 5 10 20 5 10 20 5 10 20 5 10 20
Table IV. Limit Margin Rate and Iteration Length.
Basic Algorithm Min Complexifl' (3 machines  f 5 operations) Limit Margin Rate Load Margin Rate
Real Load Rate
Table 111. Configuration of the Experiments. Opt Vec
25 25 25 25 25 25 25 40 40 40 40 40 40 40 40 40
The heuristic s were programmed with macros in Visual Basic, using the operational plans of each group of experiments as entry data. The following are the results of the simulated annealing experiments with the two heuristics.
The heuristics were programmed with macros in Visual Basic, using the operational plans of each group of experiments as entry data .
Test
I I I I I I I I I I I I I I I I
(Iteration Length)
20% 50%
50% 100%
100% 200%
40%
81.66 (00:26.2)
89.5 (00:27 .2)
93.68 (00:28 .5)
60%
42.4 (00:30.6)
66.73 (00:30.1 )
75.82 (00:30.2)
80%
2.77 (00:30.3)
14.56 (00:29.9)
34.01 (00:28.8)
Med Complexifll (5 machines  25 operations) Limit Margin Rate Load Margin Rate
40% Real Load Rate
60% 80%
(Iteration Length)
20% 50%
50% 100%
100%200%
92.06 (00:36.2) 50.61 (00:39.3) 2.6 (00:38.7)
93.75 (00:37.5) 71.35 (00 :39.9) 13.75 (00:37 .7)
96.21 (00:38.7) 78.11 (00:39.6) 27.34 (00:36.8)
Max Complexity (8 machines  40 operations) Limit Margin Rate Load Ma rgin Rate
40% Real Load Rate
(Iteration Length) 50% 100%
100% 200%
92.9 95.35 (00:41.8) (00 :41 .5) 49.92 69 .31 (00:44.4 ) (00:43.9)
96 .12 (00:43.5) 77.3 (00:43.9)
0.18 (00:43.6)
24.8 (00:41.9)
20% 50%
60% 80%
8.58 (00:43.9)
Coherence Verification Algorithm Min Complexifl' (3 machines  15 operations) Limit Margin Rate Load Margin Rate
Real Load Rate
69
(Iteration Length)
20°'05 0° '0
50%100%
100";0200° °
40%
81.41 (00:31 .9)
91.21 (00:30.4)
94.42 (00:32.1 )
60%
48.63 (00:36 .5)
65 .34 (00:35 .7)
78.75 (00:36.3)
80%
5.7 (00:37.8)
17.9 31.49 (00:38.6) (00:35.3) Med Complexity (5 machines  25 operations) Limit Margin Rate (Iteration Length) 20%50%
Load Margin Rate
40% Real Load Rate
60% 80%
Max Complexity Limit Margin Load Margin Rate
40% Real Load Rate
60% 80%
50%100%
EFFECT OF THE LOAD RATE Ye  0
_ _ _ Load
100%200%
"
er:'"
92.69 95.35 97.05 (00:42.8) (00:44.6) (00:45 . 1) 57.19 72.76 76.04 (00:48.2) (00:49.0) (00:47.3) 3.1 18.09 30.53 (00:48.1 ) (00:44.6) (00:42 .0) (8 machines  40 operations) (Iteration Length) Rate 20%50%
50%100%
100%200%
96.99 (00:51.3) 64.24 (00:57.2)
96.88 (00:51.8) 76.51 (00:57 .2)
97.72 (00:52.5) 80.24 (00:53.7)
0.59 (00:56.6)
14.3 (00:55.6)
28.03 (00:50.7)
_
Rate 40% Load Rate 60%
Load Rate 80%
Temperature
Fig 5. Performance of SA heuristic with no verification EFFECT OF THE LOAD RATE
Ve  I
180
 
5. DISCUSSION OF THE RESULTS

The mixed integer programming method lends itself to the problem of scheduling and sequencing n jobs on m machines, provided the complexity does not exceed five jobs for distribution on three machines. Otherwise, the program spends a long time iterating, attempting to find possible solutions. However, they are not optimal. With the simulated annealing method and coherence verification, the greater the load rate, the lower the limit margin rate. Likewise, the greater the autonomy margin of the machines with a fixed load rate, the greater the limit margin rate. This is because the machines have increased availability to work in the planning horizon. When working with a fixed margin rate and a fixed real load rate for the machines, increasing the number of machines and the number of operations proportionally increases the relationship between the autonomy margin assigned to the machines and the maximum limit of the total margin plan. The simulated annealing method reinforced with the coherence verification heuristic shows superior quality results compared with the basic algorithm, but convergence times are longer due to program confirmation in job scheduling.
~

<::
10
0,1
Load Rate 40 %
_
:.:::;
1000
_
er:
Load Rate 60 % Load Rate 80%
0,001
Temperature
Fig 6. Performance of SA heuristic with verification REFERENCES Torres, IF.(2000). Robust Division of Temporal Horizons in Production Planning. IX Congreso IFAC Latinoamericano de Control Automatico. eali. 2000. Ph am D.T., and D. Karaboga (2000). Intelligent Optimisation Techniques: Genetic Algorithms, Tabu Search, Simulated Annealing and Neural Networks. Springer Verlag, New York. Erschler J. (1976). Analyse sous contraintes et aide a la decision pour certains problemes d'ordonnancement. These de Doctorat d'Etat. Universite Paul Sabatier Toulouse 1976. Pinedo, M.(l995). Scheduling Theory, Algorithms, and Systems. Prentice Hall, New Jersey. Erschler J., Thuriot C. (1992). Approche par contraintes pour I'aide aux decisions d'ordonnancement., en Les nouvelles rationalisations de la Production. Editions CEPADUES. Torres I.F. (1995). Un Systeme interactif d'aide a la decision pour la regulation de charges de travail dans les ateliers. These de Doctoral. Universite Paul Sabatier.Toulouse, France.
The following graphs for both heuristics demonstrate the effect of the load rate on the control parameter known as temperature.
70