Seite - 60 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 Parametersand indices: n numberof jobs m numberofmachines i, j job index i=0, . . . ,n, j=0, . . . ,n k machine index k=0, . . . ,m pjk processingtimeof job JjonmachineMk j=1, ...,n,k=1, ...,m dj duedateof job Jj j=1, ...,n B very largepositive integer, thevalueconsidered inSection5 is:B=100∑nj=1∑ m k=1pij J0 dummyjob—thefirst in thescheduling M0 dummymachine—theoreticallyconsideredbefore thefirst (physical)machine Decisionvariables: Cjk completiontimeof job JjonmachineMk j=0, ...,n,k=0, ...,m Uj equals1 if job Jj is just-in-timeor0otherwise j=1, ...,n xij equals1 if job Ji isassignedimmediatelybefore job Jjor0,otherwise j=0, ...,n, j=1, ...,n, i = j. ThemixedintegerprogrammingmodelgivenbyExpressions (1)–(12) isbasedontheapproach proposedbyDhouibetal. [16]. MaxZ= n ∑ j=1 Uj (1) Subject to: Cjk−Cik+B(1−xij)≥ pjk, i=0,. . . ,n, j=1,. . . ,n, i = j, k=1,. . . ,m (2) Cjk−Cj(k−1)≥ pjk, j=1,. . . ,n, k=1,. . . ,m (3) Cjm−B(1−Uj)≤ dj, j=1,. . . ,n (4) Cjm+B(1−Uj)≥ dj, j=1,. . . ,n (5) ∑nj=1x0j=1, (6) x0j+∑ni=1,i =j xij=1, j=1,. . . ,n (7) ∑nj=1,j =i xij≤1, i=0,. . . ,n (8) Cj0=0, j=0,. . . ,n (9) Cjk∈ +, j=0,. . . ,n, k=0,. . . ,m (10) Uj∈{0,1}, j=1,. . . ,n (11) xij∈{0,1}, i=0,. . . ,n, j=1,. . . ,n (12) TheoptimizationcriterionexpressedinEquation(1) is tomaximize thenumberof just-in-time jobs. Expressions inEquation (2) ensure the consistencyof the completion timesof jobs, that is, if job Ji immediatelyprecedes job Jj (i.e.,xij=1), thedifferencebetweentheircompletiontimesoneach machinemustbeat leastequal to theprocessingtimeof job Jjonthemachineconsidered;otherwise (if xij=0), if there isnorelationshipbetweenthecompletiontimesof thispairof jobs, thentheconstraints inEquation(2)areredundant.Constraints inEquation(3) require that thekthoperationof job Jjbe completedafter the (k−1)thoperationplus theprocessingtime(pjk).Generally, thevalueofB isan upperboundto themakespan. Theexpressions inEquations (4) and (5) jointly establish that thevariableUj equals 1 if job Jj finishes on timeor 0otherwise. When job Jj doesnotfinishon time, i.e.,Uj =0, these two sets of constraintsbecomeredundant. Theconstraints inEquation(6)ensure thatonlyone job isassignedto thefirstposition in thesequence (notconsideringthedummyjob J0). Theexpressions inEquation(7) 60