The algorithm terminates either by delivering an optimal solution or by exceeding
pre-scribed maximal time. The former case is indicated by the emptiness of the active list.
The incumb entof permutationscheduleis thenoptimaland the incumb entupperbound
is the optimalvalue.
Computational experiments
Wehavetested the performance of several variantsof the proposed branch-and-cut
tech-nique using instances where the processing times on the second machine were generated
randomly. The objective of these experiments is to evaluate the performance of the
de-velop ed heuristics. Herewereport the resultswhere:
numb er of jobs rangesfrom 9to 13;
processing time onthe rst machine ranges from31 to59;
processingtimes b
1 and b
n
onthe second machineare xed atb
1
=30and b
n
=59,
resp ectively, and remaining pro cessing times on the second machine are generated
froma discrete uniformdistribution with a range30 to59.
We have tested the variants of the proposed lowerbounds and dominance rules. As
describedinsection5.2,wehaveproposedthreekindsoflowerbounds,inshort,simple(B),
improved(I) and LP(L) lowerb ounds. Moreover insection 5.4, wehave designed agroup
of dominance rule(D
ij ).
Forease of reference toa particular algorithm, weuse the following notation:
A B
, A I
and A L
denote the algorithms which are based onlyon the simple bounds,
improved b ounds and LP-bounds,respectively. Nodominance rule is used.
A
where 2 fB;I;Lg, 1 4 and 0 3; denotes the algorithm based
onbounds and dominancerules D
ij
with 1i and 0j .
Our exp erimentsconsist of ve parts. The purposeof eachexperimentare asfollows:
1. the evaluation of the inuence of pro cessing time a on the rst machine on the
diculty of problem F2jp
1j
=a;nmitj P
C
j
(see Figure 6.1, 6.2);
WeshowtheresultofalgorithmA B
only. TheresultsofA I
andA L
are similar.
We adopt the most simple algorithmsuchthat wehave develop ed.
2. the comparison of eciency ofthe lowerb ounds algorithm(see Figure6.3, 6.4);
We show the result of algorithm A
2
( = B;I;Land 1 3) only. The
resultsof A
( =0;1;3;4) are similarand 2-gap dominance rule isthe most
eectivegap rule.
i0
We showthe resultof algorithm A I
0
(0 4)only. The results of A B
and
A L
(1)aresimilarandthe algorithmwithimprovedboundsisthe fastest.
4. the evaluation ofnonzero-gap rules D
ij
(see Figure6.7, 6.8);
We showthe result of algorithm A I
(0 ; 3) only. The results of A B
andA L
are similarandthe algorithmwithimprovedb oundsisthefastesttoo.
5. Finally, in order to make it possible to compare the prop osed technique with
var-ious mixed integer solvers, we formulated the problem as the mixed integer linear
programming problem. Weuse the mixed integer formulationof the problem given
in the subsection 5.2.3. The results of comparison with the mixed integer solverof
the CPLEX system are summarized inFigure 6.9.
0 5 10 15 20 25 30
30 35 40 45 50 55 60
Searched Nodes(%)
10 instances n=9 jobs Algorithm A B
Figure6.1:
In all variants we used the least-b ound strategy for selecting a node from the active
list. The percentage of searched nodes refers to the value of 100m=n! where m denotes
the numb er of searched nodes and n is the numb er of jobs. The experiments were done
onSparc Station 20with 128Mbytememory.
0 1 2 3 4 5 6 7
30 35 40 45 50 55 60
Solution Time(sec.)
10 instances n=9 jobs
A B
Algorithm
Figure6.2:
2.2 2.4 2.6 2.8 3 3.2 3.4 3.6 3.8 4 4.2
Searched Nodes(%)
n=10 jobs No. of jobset=1
a=45(most difficult case)
LP bounds Improved bounds
Simple bounds
A 12
A B
12
I
A 12 L
A B
22
A B
32
A 22 I
A 32 I
A 22
A L 32 L
Figure6.3:
0 200 400 600 800 1000 1200
Simple bounds Improved bounds LP bounds
Solution time(sec.)
A 22 L
A 12 L
A 32 L
A 32 I
A 22 I
A 12 I
A B A 22
B
A 12 B
32
n=10 jobs No. of jobset=1
a=45(most difficult case)
Figure6.4:
1.5 2 2.5 3 3.5 4 4.5 5 5.5
Searched Nodes(%)
n=11
No. of jobset=1
a=45(most difficult case)
A I
A 10 I
A 20
I A
30
I A
40 I
Figure6.5:
60 80 100 120 140 160 180 200 220 240
Solution time(sec.)
n=11
No. of jobset=1
a=45(most difficult case)
A 10 I
A 20
I A
30
I A
40 I
A I
Figure6.6:
1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2
Searched Nodes(%)
n=11
No. of jobset=1
a=45(most difficult case)
A I
A I
A 12
A 13 10
11
I
I
A I
A I
A 22 A
23 20
21
I
I
A I
A I
A 32 A
33 30
31
I I
Figure6.7:
60 65 70 75 80 85 90
Solution time(sec.)
n=11
No. of jobset=1
a=45(most difficult case)
A I
A I
A 12
A 13 10
11
I
I
A I
A I
A 22
A 23 20
21
I
I
A I
A I
A 32
A 33 30
31
I
I
Figure6.8:
0 10 20 30 40 50 60 70 80
30 35 40 45 50 55 60
Solution time(sec.)
n=11
No. of jobset=1
CPLEX(mip)
Algorithm A
32 I
Figure6.9:
Concluding remarks
Throughout this dissertation we have b een concerned with deterministic owshop
prob-lems where the objective is to minimize the sum of completion times of all jobs. Since
the problem is knownto bevery hardin general,wehaverestricted our attention totwo
subcases: problemswith specialdominance relations amongmachines andproblems with
twomachines.
In Chapter 3,we haveconsidered owshopproblems with special structuredmachine
dominancerelation. AdiriandPohoryles[1]designedtwopolynomialtimealgorithms
con-structingthebestpermutationschedulesforFmjnmit;idmj P
C
j
andFmjnmit;ddmj P
C
j
respectively. Wehaveprovedthat allofthe ab ovealgorithmsconstruct not onlythe b est
permutationschedulesforthegivenproblem,butthattheyinfactproduceoptimal
sched-ules. In fact we have proved a much more general result, namely that under the above
machine dominance constraints, the search for optimalschedule can be restricted to the
set of all permutation schedules not only for the sum of completion times criterion but
for anarbitrary regularobjectivefunction.
In Chapter 4 and 5, we have considered the case of two machines. Two theorems of
paper[1] whichdeal with the F2jnmitj P
C
j
problem contain incorrect claims. We have
showed that both claims are incorrect by constructing a counter example. Moreover we
have managed to prove another statement which has a similar \avor" as the original
(incorrect) claims. Furthermore we have describ ed several variants of the
branch-and-cut technique for solving the F2jp
1j
= a;nmitj P
C
j
problem and reported results of
computational exp eriments. Their analysis leads tothe following conclusions.
Figures 6.1 and 6.2 suggest that the instances in which pro cessing time a on the
rst machineisaroundthe middleof therange ofpro cessingtimes b
i
onthesecond
machinearethemostdicult. Thereasonisthatwhenaisaroundthemiddleofthe
rangeof pro cessingtimesonthesecondmachine, many candidatejobswhichmight
b eassignedeitherafterorb eforeblockingpositionexistand,therefore,subproblem
P k
has many feasible solutions.
Figure6.3 showsthatthe improvedboundsand LPb ounds decreasethe numb erof
searchednodes. Figure6.4showsthatthe improvedboundsdecreasesolutiontimes
to o. In the moredetailed observation,wehaverealizedthat LPboundsisthe most
eective aroundthe rootof tree.
Figure6.5 and6.6 showthatD
10
-rules and D
20
-rulesincreasethe eciencyof
algo-rithms, but there is no improvement when dominance is based on the interchange
Similarly gures 6.7 and 6.8 show that D
i1
-rules and D
i2
-rules are eective in our
algorithms,but noimprovementisachievedwhengapisbasedonmorethan 2jobs.
Moreover these gures imply that D
ij
-rules (i = 1;2 and 0 j 2) are the most
eective aroundthe rootof the tree.
A comparisonwith the mixed integer solver ofCPLEXindicates thatthe proposed
branch-and-cuttechniqueis fasterthan CPLEX (see Figure6.9).
[1] Adiri, I. and Pohoryles,D. Flowshop/No-idle or No-wait scheduling to minimize the
sum of completion times, NavalResearchLogistics Quartely29, 495-504(1982)
[2] Baker,K. R.Introduction to sequencing and scheduling, John Wiley & Sons,(1974)
[3] Conway, R. W., Maxwell, W. L., and Miller, L. W. Theory of Scheduling,
Addison-Wesley, Reading,Mass. (1967)
[4] Della Croce, F., Narayan, V., and Tadei,R. The two-machine total completion time
ow shop problem. , European Journalof Operation Research,90, 227-237(1996)
[5] Garey,M. R.,Johnson,D. S.,and Sethi,R. Thecomplexityof owshop and jobshop
scheduling,Mathematics of Operations Research 1,117-129 (1976)
[6] Graham,R.L.,Lawler,E.L.,Lenstra,J.K.andRinnooyKan,A.H.G.Optimization
and approximation in deterministic sequencing and scheduling, a survey. Annals of
Discrete Mathematics 5, 287-326(1979)
[7] Ho, J.C. and Gupta,J. N. D. Flowshop Scheduling with Dominant machines,
Com-puters Ops. Res., 22, No. 2, 237-246(1995)
[8] Hoogeveen, J. A., and Kawaguchi, T. Minimizing total completion time in a
two-machine owshop: analysisof special cases.
[9] Ignall, E.and Schrage, L. Application of the Branch and Bound Technique to Some
Flow-Shop Scheduling Problems, Oper.Res., 13, 400-412(1965)
[10] Johnson,S.M.OptimalTwo-andThree-StageProductionScheduleswithSetupTimes
Included, NavalResearch Quarterly, Vol.1,No. 1 (March,1954)
[11] Kohler, W. H., and Steiglitz, K. Exact, approximate and guaranteed accuracy
algo-rithms for the owshop problem n/2/F/
F., ACM,Vol.22, No. 1,106-114(1975)
[12] Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G. and Shmoys, D. B.
Sequenc-ing and Scheduling : Algorithms and Complexity, Handbooks in OR& MS, Elsevir
SciencePublishers B. V., Vol.4445-522(1993)
[13] Lomnicki, Z. A Branch-and-Bound Algorithm for the Exact Solution of the
Three-Machine SchedulingProblem,Operational ResearchQuarterly,Vol.16,No.1(March,
1965)
Special Cases of the Permutation Flow-Shop Problem, RAIRO, Vol. 17, No. 2
105-119(1983)
[15] Van de Velde, S. L. Minimizing the sum of the job completion times in the
two-machine owshop by Lagrangean relaxation., Annals of Operations Research, 26,
257-268(1990)