JAIST Repository
https://dspace.jaist.ac.jp/
Title
フローショップ問題:特殊条件下の完了時刻和最小化の解析
Author(s)
岡田, 政則Citation
Issue Date
1998‑03Type
Thesis or DissertationText version
authorURL
http://hdl.handle.net/10119/858Rights
Description
Supervisor:Milan Vlach, 情報科学研究科, 博士to Minimize Total Completion Time
By Masanori Okada
A thesis submitted to
School of Information System Science,
Japan Advanced Institute of Science and Technology,
in partial fulllment of the requirements
for the degree of
Doctor of Information System Science
Graduate Program in Information Science
Written under the direction of
Professor Milan Vlach
January 16, 1998
In this dissertation we are concerned with deterministic owshop problems where the
objective is to minimize the sum of completion times of all jobs. Witha few exceptions
owshop problems of this typ e are known to be computationally intractable. Therefore
we haverestricted our attention to the followingtwospecial cases.
The rst case deals with twotypes of specially structured dominance among the ma-
chines. It is known [1, 7] that under such a dominance the best schedule among the so
called\permutationschedules"can be found inpolynomialtime. Hereweprovethat the
schedulesconstructed asin[1,7]arenot onlythe bestpermutationschedulesbut are the
optimalones. In factweprovea muchmore generalresult, namely that underthe 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.
The second case deals with twomachine problems. We studythe twomachine prob-
lems under the assumption that noidle machine time between the consecutive operation
isallowed. First weshowthatsome claimsinthe literature are incorrect. Thenwe prove
statements which havesimilar \avor" as the original incorrect claims. From Chapter 5
on, thefocus ofourstudyisonthesubproblemsp eciedbytheadditionalconstraintthat
all operations on the rst machine have the same length. We describ e several variants
of the branch and cut technique for solving this strongly NP-hard problem and report
results of computational experiments.
The author wishes to express his sincere gratitude to his principal advisor Professor
Milan Vlach of Japan Advenced Institute of Science and Techology for his constant en-
couragement and kind guidance during this work. The author would like to thank his
advisorAssociateProfessorKunihikoHiraishiofJapanAdvancedInstituteofScienceand
Technology.
The authoris grateful to Professor Hiroaki Ishii of OsakaUniversity for their helpful
suggestions and discussions.
TheauthoralsowishestoexpresshisthankstoProfessorMasayukiKimuraandTetuso
Asano of Japan AdvancedInstitute of Scienceand Technology for their suggestions.
The author is grateful to all who have aected or suggested his areas of research.
Visiting Asso ciate Ondrej
Cepek ofJapan Advanced Instituteof Scienceand Technology
inspired the author through his constant activities on scheduling theory, and gave the
author valuablesuggestions and kind encouragements.
The author devotes his sincere thanks and appreciation to all of them, and his col-
leagues.
Abstract i
Acknowledgments ii
1 Intro duction 2
2 Basic denitions, notation, and results 6
3 Flowshop with machine dominance 9
4 Two-machine owshop 14
5 Branch-and-Cut technique 21
5.1 Feasibility . . . 22
5.2 Lower bounds . . . 24
5.2.1 Simplelowerbounds. . . 24
5.2.2 Improvedlowerb ounds . . . 25
5.2.3 Lowerb ounds based onLP relaxation. . . 27
5.3 Branching rule . . . 29
5.4 Dominancerules . . . 30
5.4.1 Zero-gap dominance rules . . . 30
5.4.2 Nonzero-gap dominance rules . . . 31
5.5 Initialization. . . 32
5.6 Termination . . . 32
6 Computational experiments 33
7 Concluding remarks 39
Publications 43
Introduction
Sequencing and scheduling theory is concerned primarilywith the developmentof math-
ematical mo dels and techniquesfor analyzing and solving problems arising in situations
in which scarceresources haveto be allocated to activitiesovertime. The earlyresearch
was motivated mainly by problems from manufacturing and processing industries. The
resources wereusually machinesand activitieswerejobs tob eexecuted onthe machines.
However,analogousproblemsariseinsuchavarietyofsituationsthatthenumberofprob-
lemtyp esispractically unlimited. Forexample,severalnewclassesofpractically relevant
and theoretically interesting scheduling problems have come to existence in connection
withthe developmentofexiblemanufacturingsystems andtechnologicaladvancesinro-
botics. Another fundamentallynew direction has been connected with arapid expansion
of computer science. This inuence has taken several forms. On the one hand, results
in complexitytheory led to deep er understanding of the inherent diculty of scheduling
problems and to devising new techniques for obtaining bounds on performance of ap-
proximation algorithms. On the other hand, scheduling theory has devised new models
in studies of multipro cessors systems, distributed systems and computer networks. The
authors in this area refer to machines as processors and to jobs as tasks. We shall be
using the classical terminology,that is we shall be talking about jobs and machines.
In thisdissertationweare concernedonlywithcases whereallproblemdataare exact
and known in advance. These deterministic problems have the form of the following
optimization problem: Given a nite number of jobs J
1
;J
2
;111;J
n
which have to be
processed on a system of a nite numb er of machines M
1
;M
2
;111;M
m
, nd a feasible
schedule that minimize the value of agiven objective function.
Before sp ecifying exactlythe special structured class of deterministicproblems which
the dissertation is devoted to, we shall briey recall some basic models of deterministic
machinescheduling. Inallthesemo delsthe followingthreeassumptionsare conventional.
Eachmachine isalways availablethroughoutagivenschedulingperiod,usually the
interval[0;1).
No machineis able to process more than one job ata time.
Eachjob can b eprocessed byat most one machine ata time.
It is an established tradition to distinguish three typ es of multi-op eration models:
openshops,jobshops and owshops. In allthese three models, eachjobs J
k
consists of m
operations O
1k
;O
2k
;111;O
mk
. Eachoperation O
ik
must be executed on machine M
i and
ik
the machines is prescribed. In the jobshop and owshop a pro cessing order through the
machines is prescribedfor eachjob. In the jobshop this order may varyfrom job to job,
whereas in the owshop all jobs have the same order through the machines. If m = 1,
then allthree models reduce tothe singlemachine problem.
Generally speaking, a schedule must sp ecify when the jobs are processed on the ma-
chines within the scheduling p eriod. The assumptions stated above make it possible to
expresstherequiredinformationwiththehelpofanorderedm-tupleS =(S
1
;S
2
;111;S
m )
of functionseachofwhichmaps theschedulingperiod intothesetf0;1;111;ng. The cor-
responding interpretation is rather obvious. Namely, the equality S
i
(t) = k means that
jobsJ
k
ispro cessedonmachineM
i
attimet,wheneverk6=0. Ifk =0,thatisifS
i
(t)=0,
then machine M
i
isidle attime t.
Ofcoursenot everyorderedm-tuple(S
1
;S
2
;111;S
m
)of suchpiece-wise constantfunc-
tions represents a feasible schedule. Besides some purely mathematical technicalities
we have to require that the assumptions above are satised and that each job must be
processedtocompletionwithintheschedulingperiod. Inadditiontothesebasicfeasibility
requirements, several other constraints may limit the choice of schedules. In most cases
theyrepresentlimits onthe capacity of availableresources or various typ es of technolog-
ical or organizational requirements. Forexample, the feasibility may depend on whether
or not
the processing of a job on a machine may be interrupted and resumed at a later
time;
a precedenceordering is imposed onthe jobs;
job-dependent deadlines orrelease times are given.
All suchconstraints can be formulated in terms of functions S
1
;S
2
;111;S
m
. In this way
we obtain a well-dened concept of a feasible schedule which can be easily graphically
represented, manipulated and analyzed.
As so on as itis clear which schedules are feasible, then the rst question tobe asked
iswhether a feasible scheduleexists. In general,this question maybevery hard,because
already the problem of deciding whether or not a feasiblescheduleexists isNP-complete
inthe single-machine case, provided arbitraryinteger processingtimes, releasedates and
deadlines arepermitted. However,inthe dissertation,weare concerned withproblems in
which this question is trivial. In fact, we shall deal with situations in which there exist
innite numb er of feasible schedules. In such situation we need a tool for their mutual
comparison. The standard approachisto compare the qualityof scheduleswith the help
of a real valuedfunction f denedon the set of schedulesin sucha way that schedule S
isbetterthanscheduleS 0
if andonlyiff(S)<f(S 0
). Suchfunctioniscalledanobjective
function, and the problem is to minimize f on the set of feasible schedules. Usually the
objectivefunctionsofthe basic mo delsare socalled regularmeasures of performance. By
this term it is meant that f depends on the completion times C
1 (S);C
2
(S);111;C
n (S)
of jobs in schedule S in such a way that if C
j
(S) C
j (S
0
) for each 1 j n, then
f(S)f(S 0
). In other words,if scheduleS is better than S 0
, then at least one job must
be completed under scheduleS earlier than underscheduleS 0
.
Essentiallytwotyp esof regularobjectivefunctionsareappearinginthe basicmodels.
They are composed from nondecreasing real valued functions '
1
;'
2
;111;'
n
asso ciated
f
max
(S) = max
1k n '
k (C
k (S));
f
sum
(S) = n
X
i=1 '
k (C
k (S)):
As arule, these so called cost orpenalty functions'
1
;'
2
;111;'
n
are based onextremely
simplequantitiesinvolvingexplicitlyorimplicitlytheconceptofjobdue dates. Astypical
example we can mention
Lateness : '
k
(t)=L
k
(t)=t0d
k
Tardiness : '
k
(t)=T
k
(t)=maxf0;t0d
k g
UnitPenalty : '
k
(t)=U
k (t)=
(
1 if t >d
k
0 if t d
k
where d
k
stands for the due date of jobs J
k .
Several classicationand notation schemefor deterministicscheduling problems have
been suggested. We have followed the scheme proposed by Graham et al. [6] in which
a problem typ e is specied in term of the following three-eld classication jj. The
rst eld sp eciesthe machine environment. Forexample,if =J then wehave general
jobshop,andif =F2,thenwehavethetwomachineowshopproblem. thesecondeld
isconcerned with jobcharacteristics. Forexample,if =precthen ageneralprecedence
relationis permitted, and if =pmtn then preemptionis allowed. The third eld refers
to the objective function. For example: if = T
max
, then the maximum tardiness is to
be minimized, and if = P
U
j
then the numb er of tardy jobs should be minimized. For
a detailed description of the scheme and a survey of complexity and algorithms we refer
to [12].
In this dissertation we are concerned with a special class of deterministic owshop
problems. As already mentioned,in the deterministic owshop problems, a set of n jobs
J
1
;J
2
;111;J
n
isto be processed through m machines M
1
;M
2
;111;M
m
under the techno-
logical constraintsdemanding that the jobs pass amongthe machines inthe same order.
Without lossof generality we may assumethat the machines are numb ered according to
thetechnologicalconstraints,thatiswemayassumethateachjobmustb epro cessedrst
onmachine M
1
, then onmachine M
2
, and so on, until it isnally processed onmachine
M
m
. The order of jobs on any given machine is not prescribed and may vary from ma-
chineto machine. No machine may process more than one job ata time, and nojob can
be processed by severalmachines simultaneously. Eachjob consists ofm operations, one
operationpermachine. The operationofjob J
j
onmachineM
i
isdenoted byO
ij
and the
processingtime of operationO
ij
is denoted by p
ij
. Once aprocessingof anoperationO
ij
starts, it cannot b e interrupted, i.e. operation O
ij
then occupiesthe machine M
i
for the
nextp
ij
time units. Inschedulingtheory literature op erations fulllingthe last condition
are callednonpreemptable. Someother technologicalororganizationalconstraintsonthe
feasibility of schedules may also b e given. The generalproblem is then to nd a feasible
schedule minimizinga prescribedobjective regularfunction denedon the setof feasible
schedules.
Agreatvarietyofsuchproblemshavebeenstudiedbyb oththeoristsandpractitioners
since the pioneering work of J. M. Johnson [10] from mid 50's, which dealt with two-
machineand three-machineproblems. Inthis dissertation weconsiderowshopproblems
is known to bevery hard ingeneral, weshall restrictour attention totwosub cases. The
rst subcase studied inSection 3deals withtwo typ es of specially structured dominance
among the machines. It is known [1, 7] that under such a dominance the best schedule
among the so called \permutation schedules" can b e found in polynomial time. Here
we prove that the schedules constructed as in [1, 7] are not only the best permutation
schedulesbut are the bestamong allfeasible schedules,i.e. are optimal. In factweprove
amuchmoregeneralresult,namelythatundertheabovemachinedominanceconstraints,
the searchfor optimal schedule can be restricted tothe set of all permutationschedules
not onlyfor the sum of completion times criterion but for an arbitrary regular objective
function whichfullls certain verygeneral properties.
ThesecondsubcasewhichwestudyinSection4isthecaseoftwomachines. Following
the notation and terminology of the classication for the deterministic scheduling prob-
lemsproposedbyGrahametal.[6],wedenotethis problemasF2jj P
C
j
. Oneofthe rst
papersto studythis particular problem was[9] wherea branch-and-b oundalgorithm for
the problem was develop ed. The complexity of the problem was later established in [5].
It was proved that F2jj P
C
j
is NP-hard in the strong sense. Given this intractability
result,itcomesas anosurprise thatalot ofeort wasput intodevelopingheuristics and
approximationalgorithmsbased onseverallowerboundtechniques(see e.g.[11,15] or[4]
forsurvey). Allthe abovealgorithms utilizethe followingfactwhichisaconsequenceofa
more generaltheorem in [3]: it sucesto optimize overa setof those schedules inwhich
both machines process jobs in the same order and moreover in which the rst machine
has no idle time.
This raisesaquestionhowdoesthecomplexityofF2jj P
C
j
changeifweallownoidle
time also on the second machine. We denote this new problem as F2jnmitj P
C
j
where
\nmit"standsfor\nomachineidletime". Sucharestrictionmaybeverynaturalinsome
real life situation, e.g if b oth machines represent an expensive equipment which has to
be rented for the duration between the start of the rst operation and the completion
of the last one. First thing to note is that the argument from [3] carries over for this
no-idle case, i.e. again it suces to optimize over the set of permutation schedules. To
make this dissertation self-contained, we recall in Section 4 the proof of this fact. We
then commence the study of F2jnmitj P
C
j
by statingtwo theorems from[1] whichdeal
with certain properties of optimal schedules. We show that b oth claims are incorrect.
Moreover, we manage to prove another statement which has a similar \avor" as the
original(incorrect) claims. Similarlytothe argumentfrom [3], also thecomplexityresult
from[5]carriesovertoF2jnmitj P
C
j
. Thereforeitislegitimatetodecomposetheproblem
yetfurther, and study subproblemsof F2jnmitj P
C
j .
Thesubproblemthatwillb einthefocusofourstudyfromSection5onhas thefollow-
ing additional constraint: allop erations on the rst machinehave auniform length. The
complexity of this F2jp
1j
=a;nmitj P
C
j
problem wasrecentlyinvestigated in [8]. Once
again, it was proved that the problem is NP-hard inthe strong sense. Although strictly
speaking the authors of [8] work withF2jp
1j
=aj P
C
j
, i.e. theydo not require the \no-
idle" constraint, their proof is valid without any changes for the F2jp
1j
= a;nmitj P
C
j
caseaswell. In Section5wedescribeseveralvariantsofthebranch-and-cuttechniquefor
solving the F2jp
1j
= a;nmitj P
C
j
problem and report results of computational experi-
ments.
Basic denitions, notation, and
results
Let usstart this chapterbyintro ducing some fairly standard notions and stating several
simple results. First we need to formalize the notion of a schedule. A schedule S for a
owshop problem with n jobs on m machines is a set of mn nonnegative numb ers C S
ij ,
1im,1j n,whereeachC S
ij
denotesthecompletiontimeofthe op erationO
ij in
the scheduleS. Since the operationscannotb e preempted,a system of completiontimes
C S
ij
fully sp ecies a schedule as described in the Intro duction. In other words, since the
operations can not be preempted the completion time fully species the span in which
eachoperation ispro cessed,i.e. operationO
ij
ispro cessed inthe interval(C S
ij 0p
ij
;C S
ij ),
where p
ij
denotesthe prescribedduration of operation O
ij
. Forevery jobJ
j
, 1j n,
the job completion time C S
j
isthe completion time of its last operation,i.e. C S
j
=C S
mj .
A schedule S is called feasible if it fullls all feasibility constraints. In addition to
the obvious requirement C S
1j 0p
1j
0, there are two feasibility constraints for general
owshop problems:
Machineconstraint: each machine may process atmost one job at any given time.
Formally
8i2f1;:::;mg8k;`2f1;:::;ng :(k 6=`) =)(C S
ik 0p
ik
;C S
ik )\(C
S
i`
0p
i`
;C S
i`
)=;:
Job constraint: no jobis pro cessed on more than one machine simultaneously, and
moreovertheoperationsofeachjobare processedonallmachinesinthesameorder.
Formally
8i;j 2f1;:::;mg8k 2f1;:::;ng :(i<j)=)(C S
ik C
S
jk 0p
jk ):
In the main part of this dissertation we will require the schedulesto fulll anadditional
feasibility constraint:
No-idle constraint: no machine is allowed to have an idle time b etween processing
any twoop erations. Formally
8i2f1;:::;mg8k;`2f1;:::;ng :(C S
ik
<C S
i`
0p
i`
)=)(9q:C S
ik
<C S
iq
<C S
i`
):
schedule a real numb er. The task is then to nd a feasible schedule which attains the
minimum value of the objective function over the set of all feasible schedules. Every
schedule with this property is called optimal. Typically, the objective function dep ends
only on the job completion times and furthermore possesses a regularity property. An
objectivefunction f issaid toberegularif for every two distinctschedulesS
1
and S
2 the
inequality f(S
1
) < f(S
2
) implies C S
1
j
< C S
2
j
for at least one j. The objective function
studiedinthisdissertationisf(S)= P
n
j=1 C
S
j
. Clearly,thisisaregularobjectivefunction.
Let us observe that because there are no deadlines on the completion times of jobs,
there existsafeasible schedulefor everyinstanceof the abovedescribedno-idleowshop
problem (which is then of course also a feasible schedule for the \idle time allowed"
version of the problem). Given an instance of the problem, such a schedule can for
instancebecreated asfollows: schedule consecutively allop erations on the rst machine
(in an arbitrary order with no idle time allowed) starting from time 0, then schedule
consecutively all operations on the second machine (in an arbitrary order with no idle
time allowed) starting from time P
n
j=1 p
1j
(i.e. starting when the last operation on the
rst machine is completed) and so on. It is easy toverify that such aschedule is indeed
feasible. Moreover, since there are no deadlines on the completion times of jobs, any
feasible scheduleS can be\shifted right" by anarbitrary real numb er r (replacing every
C S
ij by C
S
ij
+r) resulting again in a feasible schedule. Therefore there is an uncountable
numb er of feasible schedules for every instance of every of the owshop problems b eing
considered. In order toreduce the numb er of schedules under investigation, we need the
notion of dominance.
A setof schedulesS is saidtobedominant ifforeveryfeasiblescheduleS thereexists
a feasible schedule S 0
2 S such that f(S 0
) f(S). This guarantees that at least one
optimal schedule lies in S and hence it is enough to optimize over S and disregard all
schedulesnotinS. Nowletusshowthataslongastheobjectivefunctionisregularthere
exists anite size dominant setof schedules.
Duetothenon-preemptivenessrequirementeveryscheduledenesforeachmachinean
orderin whichthe jobs are processed, orinotherwords apermutationof jobs. Ofcourse
the samesetofm p ermutations(onep ereachmachine)maybedenedbymanydierent
schedules. However, it is not hard to see that for each xed set of m p ermutations, say
1
;:::;
m
, there is one schedulewhich dominates allthe others inthe same group. This
schedule (let us denoteit by S
1
;:::;
m
)can beconstructed as follows:
1. Schedule all operations on the rst machine in the order
1
with no idle time in
b etween operationsstarting attime 0.
2. Schedule allop erations on the second machinein the order
2
as follows:
If idle time is allowedthen schedule the op erations one by one inthe order
2
where each operation starts as early as possible, i.e. starts at the time when
the operation of the same jobon the previous machine is completed orat the
timewhenthepreviousoperationonthesamemachineiscompleted,whichever
comeslast. Moreformally,thecompletiontimeofanop erationO
2
2 (i)
foreach
1in is denedby
C S
2
2 (i)
=maxfC S
1
2 (i)
;C S
2
2 (i01)
g+p
22(i)
;
wherewe assume C S
2
2 (0)
=0 and S =S
1;:::;m
to simplifythe notation.
with no idle time in between the operations starting at the time when the
last operation on the previous machine was completed. Then \shift" all the
op erations to the left until the starting time of one of the operations \hits"
the completion time of its corresponding operation on the previous machine.
Thejobthat prohibitsfurthershiftingtotheleft(incasethatthereare several
suchjobs then the leftmost one) iscalled the blo cking jobof S for the second
machineanditspositioninS iscalledtheblockingpositionofSforthesecond
machine(see Figure 2.1).
J
1 (1)
111
J
1 (i)
J
1 (i+1)
111 J
1 (n)
J
2 (1)
111 J
2 (i01)
J
2 (i)
111 J
2 (n)
P
i01
j=1 p
2
2 (j)
-
P
n
j=i+1 p
1
1 (j)
-
C S
11(n)
Figure2.1:
More formally, the operation O
22(i)
(for each 1 i n) is rst assigned
a \tentative completion time"
^
C S
22(i)
= C S
11(n) +
P
i
j=1 p
2
2 (j)
and then the
(nal) completion time is calculated by subtracting the \length of the left
shift"`=min n
i=1 f
P
i01
j=1 p
2
2 (j)
+ P
n
j=i+1 p
1
1 (j)
g. Hence
C S
22(i)
=
^
C S
22(i)
0`=C S
11(n) +
i
X
j=1 p
2
2 (j)
0 n
min
i=1 f
i01
X
j=1 p
2
2 (j)
+ n
X
j=i+1 p
1
1 (j)
g:
3. Repeat step 2 for machinesM
3
;M
4
;:::;M
m .
By constructionitis obviousthatno op eration inS
1;:::;m
can beshifted left without
violating feasibility. On the other hand given any feasible schedule S which denes the
same set of permutations
1
;:::;
m
, it is possible to transform S into S
1
;:::;m
by per-
formingleftshiftsonacertainsetof operations.
1
Thereforef(S
1;:::;m
)f(S)holdsfor
everyregularobjectivefunctionf. ConsequentlythesetS =fS
1
;:::;
m j
1
;:::;
m 2P
n g
where P
n
is the set of all permutations of order n is a dominant set of schedules. Note
that jSj = (n!) m
, i.e. S has a nite size. From now on we shall restrict our attention
exclusively toschedulesfrom the setS.
Forsomeowshopproblems itis possibletorestrict the setS evenfurtherto asetof
the so-called permutation schedules. A schedule S
1;:::;m
2 S is a permutation schedule
if
1
=
2
= 111 =
m
holds, i.e. if the jobs are processed in the same order on all m
machines. The name \permutation schedule" reects the fact that a single p ermutation
species the entire schedule. Wedenote the set of allpermutationschedules by S.
Throughout this dissertation we shall make an assumption that all processing times
p
ij
are integers. It then follows fromthe construction of the schedulesin S that also all
completion times of operationscan beassumed integral.
1
Weomitaformalpro ofofthisfacthere. However,thereadercaneasilyverifytheclaimbyinduction,
startingwiththeleftmostop erationonwhichtheschedulesS andS
1
;:::;
m dier.
Flowshop with machine dominance
As we already mentioned in the intro duction, the problem Fmjj P
C
j
is NP-hard for
m 2 [5]. That implies that there is little hope to nd a polynomial time algorithm
which would generate an optimal solution for this problem in its full generality. Hence,
a questionarises what additional constraints shouldbe imposed onthe problem inorder
to make it tractable. Several such constraints are connected tothe long-studied concept
of machine dominance [1, 14, 7]. A machine i is said to dominate a machine j (denoted
by M
i 1>M
j ) if
n
min
k =1 fp
ik g
n
max
k =1 fp
jk g:
Weshalldealherewithtwospecialcasesstudiedin[1]and[7]. ThemachinesM
1
;:::;M
m
are said to forman increasing series of dominating machines (idm) if
M
m 1>M
m01
1>111 1>M
2 1>M
1
;
and to forma decreasing series of dominating machines (ddm) if
M
1 1>M
2
1>111 1>M
m01 1>M
m :
Bothcasesareknowntob esolvableinp olynomialtimeifwerestrictour attentiontoper-
mutationschedulesonly. AdiriandPohoryles[1]designedtwopolynomialtimealgorithms
constructingthebestpermutationschedulesforFmjnmit;idmj P
C
j
andFmjnmit;ddmj P
C
j
respectively. Ho and Gupta [7] later extended these results for the case when machine
idle time is allowed. In this dissertation we prove that all of the ab ove algorithms con-
structnotonlythebestpermutationscheduleforthe givenproblem,butthattheyinfact
produce optimal schedules. This is achieved by proving that under either of the above
machine dominance schemes (idm or ddm) the set of all permutation schedules S is a
dominantsetof schedules. Moreover,our resultsare more generalinthe sense, that they
are valid not only for the P
C
j
criterion, but rather for an arbitrary regular objective
function. Letus start with the idm case.
Proposition 1 Let f be an arbitrary regular objective function. Then the set S of all
permutationschedulesisadominantsetforbothFmjidmjf andFmjnmit;idmjf owshop
problems.
Proof. First let us note that if the machines form an increasing series of dominating
machines then it is not necessary to distinguish the situations when machine idle time
constraint no schedule S 2 S may have any idle time inbetween any two consecutively
scheduledoperations. However,thisisastraightforwardconsequenceoftheidmconstraint
andthemethodhowtheschedulesinS areconstructed. Alsonotethatforeveryschedule
S 2S, the job scheduledas the rst one on M
i
isthe blockingjob for M
i
, 1im.
Let S 2 S b e arbitrary. We shall construct T 2 S such that f(T) f(S). For that
let be the permutation of jobs dened by the schedule S on the last machine, and let
us denote j =(1) (jobj is scheduledrst onM
m
in S). Before constructing T we rst
dene aschedule R by modifyingS as follows:
On all machines schedule job j at the same time as in S, i.e. set C R
ij
=C S
ij
for all
1i m.
On all machines schedule the remaining jobs in anorder given bythe permutation
with no idle time inbetween operations. Since the job j is already scheduled,
it determines the completion times of all remaining operations on all machines.
Formally: C R
i(k )
=C R
ij +
P
k
`=2 p
i(`)
for all1im and 2kn.
First of all let us note that f(R ) = f(S) because the schedule on the last machine is
identicalinR andS. SecondlyletusprovethatRisafeasible schedule. Bycontradiction
let us assume that R is infeasible. Obviously, the only feasibility constraint that R may
violate is the job constraint. So let the job (k) be such that O
i1(k )
is completed only
after O
i
2 (k )
already starts for some machines i
1
< i
2
, i.e. let C R
i
1 (k)
> C R
i
2 (k)
0p
i
2 (k )
.
After substitutingwe get
C R
i
1 j
+ k
X
`=2 p
i1(`)
>C R
i
2 j
+ k
X
`=2 p
i2(`) 0p
i2(k )
=C R
i
2 j
+ k 01
X
`=2 p
i2(`) :
Moreover,since S isa feasible schedule we also have
C R
i
2 j
0p
i
2 j
=C S
i
2 j
0p
i
2 j
C S
i
1 j
=C R
i
1 j
:
Putting the above twoinequalities together weget
C R
i
1 j
+ k
X
`=2 p
i1(`)
>C R
i
1 j
+p
i2j +
k 01
X
`=2 p
i2 (`)
=C R
i
1 j
+ k01
X
`=1 p
i2(`)
whichimplies
k
X
`=2 p
i
1 (`)
>
k 01
X
`=1 p
i
2 (`)
whichisacontradiction tothe factthat M
i
2 1>M
i
1
. Therefore the scheduleR isfeasible.
Nowwe are ready to construct from the schedule R the scheduleT 2S. This is done by
simplyeliminatingoneachmachinethe (mayb ezerolength)unnecessary idletimebefore
the rst job starts. This is equivalent to shifting the schedule on each of the machines
M
2
;:::;M
m
tothe left untilthe jobj becomesthe blockingjob. This impliesthatalljob
completion times can only decrease(i.e. C T
k
C
R
k
for every1 k n) which together
with the fact that f is regular guarantees that f(T)f(R )=f(S).
Let us nowturn to the ddm case. Unlikein the idm case, this time it is necessary to
distinguish whether a machine idle time is allowed or not. Let us demonstrate this fact
onan example inwhichwetakef = P
C
j .
11 12 13 21 22
p
23
=2. Accordingto[7]the bestpermutationscheduleforF2jddmj P
C
j
isthe onewith
anSPTorder(jobssortedbylengthfromshorttolong)onthe rstmachine, forinstance
the schedule corresponding to the p ermutation h1;2;3i (see Figure 3.1). On the other
hand, according to [1] the best permutation schedule for F2jnmit;ddmj P
C
j
is the one
with an SPT order on the second machine, except maybe the last job. Since p
11
= p
12
and p
21
= p
22
it suces to check the schedules where J
3
is last on M
2
and where (say)
J
2
is last on M
2
, for instance the schedules corresp onding to permutations h1;2;3i and
h1;3;2i. It can be easilyveried that the latter is the better of the two(see Figure3.1).
Notethat not only may twoschedules corresp ondingto the same permutationunder the
J
1
J
2
J
3
J
1
J
2
J
3
4 7 12
J
1
J
3
J
2
J
1 J
3 J
2
8 10 11
Figure3.1:
no-idleconstraint and withoutthis constraintbe dierent(whichimplies that the sets S
andalso S aredierent),butmoreoverthat thebestpermutationscheduleisineachcase
attainedforadierentpermutationofjobs. Thisshowsthattheproblems Fmjddmj P
C
j
and Fmjnmit;ddmj P
C
j
are genuinely dierentevenfor m=2.
Now we are ready to state the variants of Proposition 1 for the problems Fmjddmjf
and Fmjnmit;ddmjf.
Proposition 2 Let f be an arbitrary regular objective function. Then the set S of all
permutation schedules is a dominant set for the Fmjddmjf owshop problem.
Proof. Let S 2 S be arbitrary. We shall construct T 2 S such that f(T) f(S). Let
us assume that the jobs are numbered according to their order on M
1
in S. Let M
i be
the rst machine whichhas in S a dierentorder of jobsthan M
1
, and let j bethe rst
(leftmost)job scheduledonM
i
out of the sequencedened by M
1
. Letk bethe jobthat
precedes j on M
i
inS. Letus observeseveral simple facts:
SincetheorderofjobsJ
1
;:::;J
k
isthesameonM
i01
andM
i
inS,theoperationO
ik
starts immediately after the conclusion of the operation O
(i01)k
. This is a simple
consequence of the ddm constraint. Moreover, because p
(i01)(k +1) p
ik
we have
C S
(i01)(k +1) C
S
ik .
Since j k+2 we also get C
(i01)(k +2) C
ij 0p
ij .
The ab ovetwofactsimply that M
i
has anidle timeof lengthat least p
(i01)(k+2) p
i(k+1)
betweenC S
(i01)(k+1)
andthestartofoperationO
ij
. However,thatmeansthattheop eration
O
i(k +1)
whichis scheduledafter O
ij
inS can b e movedinb etweenO
ik
and O
ij
tostart at
C S
(i01)(k +1)
. Therefore, after a nite numb er of such actions, the order of jobs on M
i can
be made to coincide with the order on M
1
. The same can be subsequently done for all
remaining machinespro ducing the scheduleT. Since alloperationseither stayedintheir
placeorweremovedleft,wehaveC T
j C
S
j
for all1j n. This togetherwith the fact
that f is regular impliesf(T)f(S).
Proposition 3 Let f be an arbitrary regular objective function. Then the set S of all
permutation schedules is a dominant set for the Fmjnmit;ddmjf owshop problem.
Proof. Let S 2 S be arbitrary. We shall construct T 2 S such that f(T) f(S). For
that let bethe permutationof jobs denedby the scheduleS on the lastmachine, and
letJ
j
=J
(q )
be the jobscheduledlast onM
1
in S. Before constructingT werst dene
a schedule R by mo difying S as follows:
On all machines schedule job j at the same time as in S, i.e. set C R
ij
=C S
ij
for all
1i m.
Construct a permutation from the permutation as follows
(i)= 8
>
<
>
:
(i) for 1i<q,
(i+1) for q i<n,
(q) for i=n.
ThiscorrespondstotakingthejobsscheduledafterJ
j onM
m
inS andmovingthem
(without changing their order)just in front ofJ
j .
On all machines schedule the remaining jobs in anorder given bythe permutation
with no idle time inb etween operations. Since the job j is already scheduled, it
determines the completion times of allremaining operationson allmachines. Note
that since the job J
j
=J
(q)
=J
(n)
is last onM
1
in S, the changeto the schedule
R amounts on M
1
to reordering the rst n01 jobs according to the permutation
, which obviously keeps the starting time of the rst scheduled job at time zero.
Formally: C R
i(k )
=C R
ij 0
P
n
`=k +1 p
i (`)
for all1im and 1kn01.
Firstof allletusnote thatf(R ) f(S)becausef isregularandthe scheduleonthe last
machineinR wasobtainedfromS byshiftingsome(possiblyzero)operationstothe left.
Secondly let us prove that R is a feasible schedule. By contradiction let us assume that
R is infeasible. Obviously, the only feasibility constraint that R may violate is the job
constraint. Soletthejob (k)besuchthat O
i
1 (k )
iscompleted onlyafterO
i
2 (k )
already
starts for some machines i
1
<i
2
, i.e. let C R
i
1 (k )
>C R
i
2 (k)
0p
i
2 (k )
. After substituting we
get
C R
i
1 j
0 n
X
`=k +1 p
i1 (`)
>C R
i
2 j
0 n
X
`=k+1 p
i2 (`) 0p
i2 (k)
=C R
i
2 j
0 n
X
`=k p
i2(`) :
C R
i
2 j
0p
i2j
=C S
i
2 j
0p
i2j C
S
i
1 j
=C R
i
1 j
:
Putting the above twoinequalities together weget
C R
i1j 0
n
X
`=k +1 p
i
1 (`)
>C R
i1j +p
i2j 0
n
X
`=k p
i
2 (`)
=C R
i1j 0
n01
X
`=k p
i
2 (`)
whichimplies
n
X
`=k +1 p
i
1 (`)
<
n01
X
`=k p
i
2 (`)
whichisacontradiction tothe factthat M
i1 1>M
i2
. Therefore the scheduleR isfeasible.
Nowwe are ready to construct from the schedule R the scheduleT 2S. This is done by
simplyeliminatingoneachmachinethe (mayb ezerolength)unnecessary idletimebefore
the rst job starts. This is equivalent to shifting the schedule on each of the machines
M
2
;:::;M
m
tothe left untilthe jobj becomesthe blockingjob. This impliesthatalljob
completion times can only decrease(i.e. C T
k
C
R
k
for every1 k n) which together
with the fact that f is regular guarantees that f(T)f(R )f(S).
Two-machine owshop
Inthe restof this dissertationweshall dealwith the two-machineowshoponly. Tosim-
plify the notation we replace p
1j by a
j
and p
2j by b
j
for all1 j n, and moreoverwe
assumewithout lossof generality that the jobs are numb eredaccording toa nondecreas-
ingly sorted processing times on the second machine, i.e that b
1 b
2
111 b
n
. Such
an order is often called a ShortestProcessing Time (or simply SPT) order. Nowwe are
ready to provea theorem whichis aspecial case of a moregeneral propositionfrom [3].
Theorem 1 The set of all permutationschedules S is a dominant set for both F2jj P
C
j
and F2jnmitj P
C
j
owshop problems.
Proof. Since S is a dominant set it is enough to prove that for every S 2 S there exists
a permutationscheduleS 0
2S suchthat P
n
j=1 C
S 0
j
P
n
j=1 C
S
j
. Notethat the setS (and
hence also the set S) is dierentfor eachof the twoproblems under consideration. This
is caused by the dierent method of constructing the S
1
;:::;m
typ e schedules, dep ending
on whether idle times are or are not allowed. However,the following simple interchange
argument is the same for both cases and the dierence between the sets S plays no role
in it. So let S 2 S nS be an arbitrary schedule. Since S 62 S there exists a pair of jobs
J
i
and J
j
such thatO
1j
isscheduled immediately after O
1i
in the schedule S (recall that
for allschedulesinS there isno idle time onthe rst machine regardless of whether idle
time is allowedor not) while O
2i
is scheduled after O
2j
in the scheduleS (possibly with
anidle time and/orother jobs scheduledin b etween).
Now it is obvious that interchanging the p osition of O
1i
and O
1j
leads again to a
feasibleschedule. Moreover,suchaninterchangedo esnotaectthe valueofthe objective
function because noop eration onthe secondmachine moves. Quiteclearly,after anite
numb erofthe ab ovedescrib edinterchangeswearrivetoapermutationscheduleS 0
which
has the same value of the objective function asS. This nishesthe proof.
As we indicated in the introduction, the part of the paper [1] which deals with the
F2jnmitj P
C
j
problemcontainsincorrectclaims. Letusshowthatthisisindeedthecase.
Adiriand Pohoryles [1]claim that the optimal scheduleshavethe followingproperties.
1. IfintheoptimalscheduleforF2jnmitj P
C
j
,theblockingjobisthelastone,thenthe
optimalscheduleisaccordingtoSPTonthesecondmachine,exceptfortheblocking
job that isthe one with the minimumprocessing time onthe secondmachine.
F2jnmitj P
C
i
are orderedaccordingtoSPTonM
2
,providedthe no-idleconstraint
isnot violated.
The followingexampleshowsthatneitherof theseclaimsholds,evenif werestrictthe
problem by requiringthat all pro cessingtimes onthe rst machine are the same.
Example 2 Consider the 3-job instance with a
1
= a
2
= a
3
= 4, b
1
= b
2
= 1;b
3
= 6.
Since b
1
=b
2
, it suces to consider three p ermutations only, for example, the permuta-
tionsh1;2;3i;h1;3;2iand h3;1;2i. Thecorrespondingpermutationschedulesare givenin
Figure4.1. Obviously the schedule correspondingto the permutation h3;1;2iis optimal.
J
1
J
2
J
3
J
1 J
2
J
3
1112 18
J
1
J
3
J
2
J
1
J
3
J
2
8 1415
J
3
J
1
J
2
J
3
J
1 J
2
1112 13
Figure4.1:
Its blocking job is the last one, but its rst two jobs are not in an SPT order, which
contradictsthe claims.
Now we shall prove that although the rst claim is incorrect, the special schedule
mentioned in the claim does have an interesting prop erty. Let S k
denote the set of all
schedules fromS whose blockingposition is k, 1k n, and let I k
denotethe setof n!
schedules, b oth feasible and infeasible,dened asfollows: foreachpermutation,create
the schedule in I k
by scheduling the jobs on b oth machines in the order prescrib ed by
(with no idle time), and then aligning the completion time of the operation O
1k with
the starting time of the op eration O
2k
. Furthermore, let S 3
be the schedule (possibly
infeasible) from I n
corresponding to the p ermutation such that the last job is the one
with the shortestoperationonthe secondmachineand the remaining jobsare orderedin
anSPT orderon the second machine.
Lemma 1 S isbest in I .
Proof. LetS beanarbitraryschedulefromI n
, b ethe p ermutationdeningtheschedule
S, and let t
1
denote the starting time of the rst job in S on the second machine. It is
J
(n)
J
(n)
0
t
1
P
a
j
Figure4.2:
easy toverify (see Figure 4.2)that
t
1
= n
X
j=1 a
(j) 0
n01
X
j=1 b
(j)
= n
X
j=1 a
j 0
n
X
j=1 b
j +b
(n) :
Since the completion time C S
(j)
of the job in the jth position of schedule S can b e
calculated by
C S
(j)
=t
1 +
j
X
i=1 b
(i) :
Wehave
n
X
j=1 C
S
j
= n
X
j=1 C
S
(j)
=nt
1 +
n
X
j=1
(n0j+1)b
(j) :
Nowthe substitution for t
1 gives
n
X
j=1 C
S
j
=n(
n
X
j=1 a
j 0
n
X
j=1 b
j
)+(n+1)b
(n) +nb
(1)
+(n01)b
(2)
+111+2b
(n01)
where the rst term of the sum on the right-hand side do es not dep end on the order of
jobs. Theremainingsumontherighthandsidetakesaminimumvalueifthepermutation
corresponds tothe scheduleS 3
whichnishes the proof.
Proposition 4 If S 3
is feasible then it is optimal.
Proof. Let S 2 S be an arbitrary permutation schedule and let S 0
2I n
b e the schedule
dened by the same p ermutation as S. Obviously, S and S 0
are identical on the rst
machine. SinceS isfeasible,the lastoperationonM
2
doesnotstartbeforetheconclusion
ofthelastoperationonM
1
. ThereforeSandS 0
areidenticalalsoM
2 orS
0
canbeproduced
from S byshifting the scheduleon M
2
to the left. Thus P
n
j=1 C
S 0
j
P
n
j=1 C
S
j
. However,
by Lemma 1 P
n
j=1 C
S 3
j
P
n
j=1 C
S 0
j
and therefore S 3
isoptimal.
Remark 1 If a
i b
j
whenever i 6= j, then S 3
2 S n
, and we can conclude that S 3
is
optimal. In particular, if M
1
1> M
2
then S 3
is optimal. The latter is a special case
Theorem 4 of [1], whichdeals with a decreasing series of dominatingmachines.
blockingp osition k withk <n, b ecause thenthe sum P
k
j=1 a
(j)
dep endsonp ermutation
. Consequently the startingtime ofthe blockingjobonthe second machinedepends on
the order of jobs onthe rst machine. This obstacledoes not occur when the processing
times on the rst machine are all equal to a prescrib ed positive numb er a. Before con-
sideringthis special case, we illustrate what typ e of results can hold for k<n in general
case.
Let us consider the case k =1. Let S b e an arbitrary schedule from S 1
and let be
the permutationdeningscheduleS. Completiontime C S
(i)
of thejob intheithposition
of S isobviouslygivenby
C S
(i)
=a
(1) +
i
X
r =1 b
(r ) :
Thus the sum of all completion times resulting from schedule S can be computed as
follows:
n
X
i=1 C
S
(i)
=na
(1) +
n
X
r =1
(n0r+1)b
(r ) :
If the job inthe rst positionof S is jobJ
j
,then weobtain
n
X
i=1 C
S
(i)
=na
j +nb
j +
n
X
r =2
(n0r+1)b
(r ) :
Obviously,this sum is minimized when allthe remaining jobs (i.e. alljobs except of J
j )
are scheduled in anSPT order on the second machine. Let (SPT)
j
denote the schedule
for which this minimum is attained and let S 1
j
be the set of all schedules from S 1
whose
rst jobis J
j
. Bythe ab oveconsiderationitfollowsthat if (SPT)
j
belongstoS 1
j
,then it
is best in S 1
j
. Nowlet S = (SPT)
j
, i.e. let be the p ermutation dening (SPT)
j . The
completiontimeC j
(i)
ofthe jobinthe ithpositionof(SPT)
j
canbecomputed asfollows
(see Figure4.3)
C j
(i)
= (
a
j +b
j +
P
i01
r =1 b
r
for i<j,
a
j +
P
i
r =1 b
r
for ij.
Consequently
n
X
i=1 C
j
i
= n
X
i=1 C
j
(i)
=na
j
+(j01)b
j 0
j01
X
i=1 b
i +
n
X
i=1
(n0i+1)b
i :
Since the last term is independent of j, wecan conclude that the best value is obtained
for j atwhich the minimumvalue of
V
j :=na
j
+(j01)b
j 0
j01
X
i=1 b
i
is attained. Letj 3
besuchthat
V
j 3
= n
min
i=1 V
j
where the minimumis takenover allj such that S 1
j
6=;. Since
S 1
=S 1
1 [S
1
2
[111[S 1
n
= [
fjjS 1
j 6=;g
S 1
j
;
a
j a
j +b
j
C j
(i) J
j
J
j J
1 J
2 111
J
j01 J
j+1
111 J
i
111 J
n a
j a
j +b
j
C j
(i) j
J
j J
1 J
2 111
J
i
111 J
j01 J
j+1
111
J
n
Figure4.3:
we conclude that V
j 3+
P
n
i=1
(n0i+1)b
i
is the minimum value of the objectivefunction
over S 1
, provided (SPT)
j
b elongs to S 1
j
wheneverS 1
j 6=;.
Remark 2 Ifa
i b
j
wheneveri 6=j, thenallsets S 1
j
arenonempty and(SPT)
j
belongs
toS 1
j
foreachj. Consequently(SPT)
j 3
isbestinS 1
. Moreover,S 2
=111=S n
=;inthis
case. Therefore (STP)
j 3
isbestin S. In other words, (SPT)
j 3
is optimal. In particular,
if M
2 1> M
1
then (SPT)
j
3 is optimal. This is a special case of Theorem 3 of the Adiri
and Pohoryles pap er [1]whichdeals with an increasing series of dominatingmachines.
Fromnowonletusconsiderthesp ecial caseinwhichthe processingtimesonthe rst
machineare allequal toagivenpositiveintegera, orformally leta
1
=a
2
=111=a
n
=a.
Moreover,we shallassume thatmin n
i=1 b
i
<a<max n
i=1 b
i
,because otherwisethe problem
is easily solvable due to Remark 2 or Remark 1. For each k, 1 k n, and each
permutation of jobs, let S k
denote the schedule (possibly infeasible) constructed as
follows. On therst machine,thejobsare scheduledasinthe correspondingpermutation
schedule. Onthesecondmachine,thejobsarescheduledinthesameorderbutsothatjob
J
(k 01)
is completed at time t=ka and no machineidle time existsbetween consecutive
jobs (see Figure4.4).
a a
111
a a
111 a
b
(1) 111 b
(k 01) b
(k )
111 b
(n)
k1a
Figure4.4:
-
-
(j01) (j)
J
(j01)
J
(j)
J
(j01)
J
(j)
J
(j01)
J
(j)
J
(j01)
J
(j)
P
l01
k =1 p
k (j01)
P
m
k=l+1 p
k (j01)
Figure4.5:
Let C k
(i)
denotecompletion time of J
(i) in S
k
. Then
C k
(i)
= (
ka0 P
k 01
j=i+1 b
(j)
for 1ik01
ka+ P
i
j=k b
(j)
for k in
and the sum of completiontimes under schedule S k
can becomputed as follows:
n
X
i=1 C
k
(i)
=nka0 k 01
X
i=2
(i01)b
(i) +
n
X
i=k
(n0i+1)b
(i) :
Since k P
n
j=1 b
j
=k P
n
i=1 b
(i)
,wehave
n
X
i=1 C
k
(i)
= k(na0 n
X
j=1 b
j )0
k 01
X
i=2
(i01)b
(i) +
n
X
i=k
(n0i+1)b
(i) +k
n
X
i=1 b
(i)
= k(na0 n
X
j=1 b
j )+
k 01
X
i=1
(k0i+1)b
(i) +
n
X
i=k
(n+k0i+1)b
(i)
: (4.1)
Thetermk(na0 P
n
j=1 b
j
)doesnotdep endontheorderofjobs. Notethatintheremaining
two summations each b
(i)
appears dierent numb er of times: b
(k 01)
is in the sum just
twice (and therefore the longest job J
n
should be scheduled in the (k 01)th position),
b
(k 02)
three times, and so onuntilb
(1)
appears k times. In the second summation b
(n)
ispresentk+1times,b
(n01)
k+2times, andsoonuntilnallyb
(k )
appears n+1times.
Therefore the minimum value of (4.1) is achieved for the permutation constructed as
follows. First, orderthe jobsinanondecreasing orderof b
i
's(SPTorder). Thenschedule
the rst segment of n0k+1jobs fromt=ka and placethe remaining segmentof k01
jobs infrontof t=ka withoutallowing any machine idle time between consecutive jobs.
Sincewehaveassumedthatthe jobsare numb ered inthe nondecreasingorder ofb
i 's,the
resulting job order is
^ =hJ
n0k +2
;J
n0k +3
;111;J
n
;J
1
;J
2
;111;J
n0k +1 i:
Of course the corresponding schedule S
^
is not necessarily in S . Because all schedules
fromS k
havethe formS k
forsome , the scheduleS k
^
providesa lowerbound for S k
. As
a consequence, wehavethe followingproposition.
Proposition 5 IfS k
^
b elongs toS k
, then itis best inS k
.
It should be pointed out that this proposition is of very limited value, b ecause as a
rule S k
^
doesn't b elong to S k
. In particular, if 1<k <n, then b
n
a must hold for the
job J
n
to start only after its operation on the rst machine is completed, and similarly
a b
1
must hold so that the job J
2
starts only after its operation on the rst machine
is completed. Therefore S k
^
belongs to S k
if and only if max
1in b
i
a min
1in b
i .
However, it happens if and only if b
1
= b
2
= 111 = b
n
= a, and then every permutation
schedule is optimal. The usefulness of scheduleS k
^
is in the fact that it providesa lower
bound for S k
.
A further extension of this simple bound and Proposition 5 will be given in the fol-
lowing chapterinconnection with the branch-and-cut technique.
Branch-and-Cut technique
Inthischapter,wedescribetheproposed branch-and-cutproceduresforsolvingtheprob-
lem F2jp
1j
=a;nmitj P
C
j
. Weassume, withoutlossof generality, that
b
1 b
2
111b
n and b
1
<a<b
n :
In general terms, we can describe the procedure as follows. At any stage of our
search the set of all permutationschedules is partitioned into a family of subsets. Each
of these subsets represents an active subproblem consisting of minimizing the objective
function on that subset. The strategy is to select some active subproblem, examine
it, and decide whether or not any solution to that subproblem needs to be considered
further in identifying an optimal solution of the original problem. If not, we consider
that subproblem fathomed, and we remove it from the list of active subproblems. If it
cannot be fathomed,then itis replaced in the list of active subproblems by one ormore
newactivesubproblemseachofwhichisderivedbyimposingsomeadditionalconstraints.
The entire pro cess can b e represented as a tree where nodes in the tree correspond to
subproblems and where branches are formed according to restrictions that are imposed
for creating the subproblems
In the following subsections we specify the general strategy in more detail. For ease
of presentation,we renethe previous notation as follows. A p ermutationof a subset of
jobsis called apartial sequence. If A and B are partialsequences of twodisjointsubsets
ofjobs,then S k
(B;A)denotesthesetof allschedulesfromS k
inwhichB iscompleted at
time ka and A isscheduledimmediately afterB - seeFigure5.1. Inthis notation, setS k
becomes S k
(3;3)where 3 stands forthe partial sequence of empty set. The problem of
B A
ka
Figure5.1:
minimizingthesumofcompletiontimesoverS k
(B;A)willbecalledsubproblemP k
(B;A).
IfS (B;A)isempty,then wesaythatP (B;A)isinfeasible,otherwiseit isfeasible. IfA
is apartial sequence, thenjAj denotes the numb erof elementsof the corresponding set.
5.1 Feasibility
During the run of the branch-and-cut algorithm subproblems need to be tested for fea-
sibility. This can be done as follows. Let A and B be partial sequences of two disjoint
subsets of jobs and let k be a given integer, 1 k n. First obvious condition for a
feasibility of subproblemP k
(B;A)is
0jBjk01 and 0jAjn0k+1: (5.1)
Toformulateother conditions,supp ose thatA=hJ A
1
;J A
2
;111;J A
jAj
i,andletb A
i
denotethe
processingtimeofJ A
i
onthe secondmachine. SincethejobsofAmustb escheduledfrom
timekawithoutany insertedmachineidle time,the followingsystem ofinequalities must
be satised.
r
X
i=1 b
A
i
ra for 1rjAj01 (5.2)
If jAj<n0k+1, then the previous inequality must hold also for r=jAj, i.e
jAj
X
i=1 b
A
i
jAja: (5.3)
Analogously, let B = hJ B
jBj
;J B
jBj01
;111;J B
1
i and let b B
i
denote the processing time of J B
i
on the second machine. Then, for the feasibility of P k
(B;A), the following system of
inequalities musthold:
r
X
i=1 b
B
i
<ra for 1r jBj: (5.4)
The strict inequalities are required, because if the equality holds for some r, then the
resulting schedulesdo es not belong toS k
(B;A) but toS k0r
(C ;D)where
C =hJ B
jBj
;J B
jBj01
;111;J B
r +1 i;
D=hJ B
r
;J B
r 01
;111;J B
1
;Ai:
For easy reference, we say that partial sequence A is right-feasible for position k, when
(5.2)and, ifapplicable, also(5.3)are satised. Similarly,wesaythat B isleft-feasiblefor
position k, when(5.4) is satised. If A is right-feasibleand B isleft-feasible for position
k,then wesay that hB;Ai isfeasible for positionk.
If hB;Ai isfeasible forpositionk,then there isachancethat partial sequencehB;Ai
may be extended into a complete sequence which determines a schedule belonging to
S k
(B;A). Toseewhatconditionsmustbefurtherfullled,werstobservethatk010jBj
jobsmustbescheduledinfrontof B and n0k+10jAjjobs mustb e scheduledafterA.
Let n
A
;n
B
;M
A
and M
B
bedened asfollows:
A B
M
A :=
P
jAj
i=1 b
A
i
0jAja, M
B
:=jBja0 P
jBj
i=1 b
B
i .
Further,letA 0
and B 0
be partialsequencesof n
A and n
B
jobs belonging neithertoA nor
to B. Fordeniteness suppose that
A 0
=hJ A
0
1
;J A
0
2
;111;J A
0
n
A i; B
0
=hJ B
0
n
B
;J B
0
n
B 01
;111;J B
0
1 i:
It is easy to verify that if the permutation schedule dened by hB 0
;B;A;A 0
i belongs to
S k
(B;A),then
r
X
i=1 b
B 0
i
<ra+M
B
for 1r n
B
; (5.5)
r
X
i=1 b
A 0
i
ra0M
A
for 1r n
A
01: (5.6)
Obviously,if these conditions are not satisedfor A 0
and B 0
suchthat
b A
0
1 b
A 0
2
111b A
0
n
A b
B 0
n
B b
B 0
n
B 01
111b B
0
1
;
then they cannot be satised for any other choice of A 0
and B 0
. Consequently, in such
cases S k
(B;A)is empty and problem P k
(B;A)is infeasible.
Example 3 Consider the instance of 7 jobs with a = 30 and b
j
given by the following
Table5.1.
Table 5.1:
j 1 2 3 4 5 6 7
b
j
29 31 32 33 33 36 40
1. Consider P 3
(3;hJ
1
;J
2
i). In this case condition (5.2) is not satised for r = 1,
b ecause
r
X
i=1 b
A
i
=b A
1
=b
1
=29<30=ra:
ThereforeP 3
(3;hJ
1
;J
2
i)is infeasible.
2. Consider P 4
(hJ
1 i;hJ
4
i). Nowall conditions (5.2)-(5.4) are satised. It remains to
verify conditions (5.5) and (5.6) for A 0
= hJ A
0
1
;J A
0
2
;J A
0
3
i and B 0
= hJ B
0
2
;J B
0
1
i such
that
b A
0
1 b
A 0
2 b
A 0
3 b
B 0
2 b
B 0
1
where all jobs are dierent from J
1
and J
4
. It follows that A 0
= hJ
7
;J
6
;J
5 i and
B 0
=hJ
3
;J
2
i Nowit is easyto verifythat conditions (5.6) are satised,because
b
7
= 403003=a0M
A
; (5.7)
b
6 +b
7
= 76213003=2a0M
A :
b
2
= 31=30+1=a+M
B :
Strict inequality is required instead of the above equality and therefore we again
conclude that P 4
(hJ
1 i;hJ
4
i) is infeasible.
3. Consider P k
(3;3) for 1 k 7. First we observe that P k
(3;3) is infeasible for
4k 7. Thisfollowsfromthefactthat(5.5)cannotbesatised,becauseM
B
=0
and b
1 +b
2 +b
3
>3a. Next we observe that P 3
(3;3) is also infeasible because we
must have b B
0
1
< a and b B
0
2 +b
B 0
1
< 2a, the latter being impossible. Finally we
observe that the schedule given by hJ
n
;J
n01
;111J
1
i belongs to S 1
(3;3) and the
schedulegivenbyhJ
1
;J
n
;J
n01
;111J
2
ibelongstoS 2
(3;3). Thereforeboth P 1
(3;3)
and P 2
(3;3) are feasible.
5.2 Lower bounds
During initialization and fathoming some easily computable lower bounds on the value
of optimal solutions of subproblems should be available. In section 4 we have derived
simplelowerboundsonthe valueof the objectivefunctionoverS k
(3;3). In the simplest
versionofourprocedureweusethefollowingextensionofthesesimpleboundstoarbitrary
S k
(B;A).
5.2.1 Simple lower bounds
Let hB;Ai be feasible for blo cking position k. Consider the corresp onding subproblem
P k
(B;A) and its feasible set S k
(B;A). Let be a permutation constructed from the
partialsequence hB;Ai bycompleting itto acomplete sequence asfollows. From among
the jobs that do not appear in hB;Ai put n
B
jobs before B and n
A
jobs after A, in
both cases in an arbitrary order. Having , we associate with it the following, possibly
infeasible, schedule S. On b oth machines the jobs are scheduledas in the corresponding
permutation schedule but on the second machine the schedule is shifted so that the job
inthe (k01)th position iscompleted attime t =ka. LetC k
(i)
denotecompletion time
of J
(i)
under S. Using (4.1) we obtain
n
X
i=1 C
k
(i)
= k(na0 n
X
j=1 b
j )+
k 01
X
i=1
(k0i+1)b
(i) +
n
X
i=k
(n+k0i+1)b
(i)
= k(na0 n
X
j=1 b
j )+
k 010jBj
X
i=1
(k0i+1)b
(i) +
k 01
X
i=k 0jBj
(k0i+1)b
(i)
+
k+jAj01
X
i=k
(n+k0i+1)b
(i) +
n
X
i=k+jAj
(n+k0i+1)b
(i)
: (5.8)
Thetermk(na0 P
n
j=1 b
j
)doesnotdependontheorderofjobs,andtheterms P
k 01
i=k 0jBj (k0
i+1)b
(i) and
P
k +jAj01
i=k
(n+k0i+1)b
(i)
do not dep end onthe order of jobsoutside of
