Seite - 61 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 establish that job Jj (j = 0) either occupies thefirst position (after J0) or is necessarilyprecededby another job. The constraints in Equation (8) ensure that one job, atmost, immediately precedes another. Theexpressions inEquation(9)definethatall the jobsarereadytobe initiatedonmachine M1, that is thecompletion timeforall jobs in thedummymachine (k=0) iszero,andsoensure the consistencyoftherestrictionsinEquation(3). TheexpressionsinEquations(10)–(12)definethedomain of thevariables. Themodel’s size inrelationto itsnumbersofvariablesandconstraintsarepresented inTable1. Forexample,an instancewithn=5 jobsandm=3machineshas69variablesand91constraintsand anotheronewithn=10 jobsandm=5machineshas236variablesand268constraints. Table1.Model’s size inrelationtonumbersofvariablesandconstraints. Variables Binary n2 +2n Integer n2 +m+n+1 Total n(2n+3)+m+1 Constraints (2) n2m+nm (3) nm (4) n (5) n (6) 1 (7) n (8) n+1 (9) n+1 Total n(n+2m+6)+m+3 4.ConstructiveHeuristics Toefficiently solve theproblemdescribed inSection3, tenconstructiveheuristicmethodsare proposed based on an investigation of the problem structure and inspired by relevant classical algorithms, suchas theNEHheuristic [17],Hodgson’salgorithm[18]andwell-knownpriorityrules, such as the EDDwhich is the ascending order of duedates, and theminimumslack time (MST) whichsequences jobsaccording to thesmallestamountof slack (dj−∑mk=1pjk). It isknownthat, in asingle-machineproblem, theEDDandMSTrulesminimize themaximumtardinessandearliness, respectively [19]. All theheuristics requirea timingadjustmentprocedure thatconsistsof checkingthebest instant tostart theoperations foragivensequence tocompleteagreaternumberof jobsontime. Thesimple shiftingofanearly jobwithaslacktimetomatchitsconclusiontoitsduedatecouldresult inanoverall improvement inthesolution.Apseudo-codeof thetimingadjustmentprocedure isgiveninAlgorithm 1.Note thatashift isappliedonly in the lastoperationofa job(Step3 inAlgorithm1)becausekeeping eachpreviousoperationstartingat itsearliestpossible instantcanbeanadvantage in thisproblemas it enables jobs that couldbe latebecauseof theirfirstoperations tobeanticipated. Inaddition, this shift ismaintainedwhen there is an improvement in the solution (or at least a tie); otherwise, the replacement is reversedtoanticipateoperationswhichcontribute toeliminatingpossible tardiness in subsequent jobs. Timingadjustmentprocedure Step1. For thegivensequence, consideringstartingeachoperationasearlyaspossible, compute the numberof just-in-time jobs (nJIT) andconsider Jinitial = J[1],where J[j] is the job inposition jof thesequence. Step2. From Jinitial, identify thefirst early job in the sequence (JE) andgo toStep3. If thereareno early jobs (from Jinitial), STOP. Step3. Movethe lastoperationof job JE toeliminateearlinessandmake itsconclusioncoincidewith itsduedate. Properlyreschedule the lastoperationsof the jobsafter JE. 61