Seite - 59 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 Several two-machineweightedproblems,aflowshop, jobshopandopenshop,areconsidered by[10]. Theyproposepseudo-polynomialtimealgorithmsandawayofconvertingthemtopolynomial timeapproachschemes. Shabtay[11]examinedfourdifferentscenarios foraweightedproblem:firstly, twomachinesandidenticalweights for jobs; secondly,aproportionalflowshop,which theprocessing timesonallmachinesare thesame; thirdly,asetof identical jobs tobeproducedfordifferentclients (theprocessing timesareequalbutduedatesdifferent foreachclient); and, lastly, theno-waitflow shopwithnowaiting timesbetween theoperations of a job. Adynamicprogrammingalgorithm and, for a two-machineproblem, an algorithmof less complexity than thatwereproposedby [9]. Aproportionalflowshopproblemwasaddressedby[12]whoconsideredoptionsofwithandwithout ano-wait restriction,andproposeddynamicprogrammingalgorithms. Giventhedifficultyofdirectlysolvingthisclassofproblems, someauthorspreferredtoconvert themintoother typesofoptimizationproblems, suchas thepartitionproblem[9]andthemodelingof acyclicdirectedgraphs [11].Abi-criteriaproblemofmaximizingtheweightednumberof just-in-time jobsandminimizingthe total resourceconsumptioncost ina two-machineflowshopwasconsidered by[2]. Focusing on maximizing the number of just-in-time jobs, only one work [2] presented computationalexperiments.Gerstletal. [12]onlymentionedthatamodelis implemented.Unlikemost studies in theshopschedulingareaemployingexperimental researchmethodologies,allotherpapers examinedusedtheoreticaldemonstrationsandproperties toattest to thevalidityof theirproposed methods,aswellasanalysesofalgorithmiccomplexity,butdidnotpresentcomputational results. Yin et al. [13] considered the two-machineflowshopproblemwith twoagents, eachof them having itsownjobset toprocess. Theagentsneedtomaximize individually theweightednumberof just-in-time jobsof their respectiveset. Theauthorsprovidedtwopseudo-polynomial-timealgorithms andtheir conversion into two-dimensional fullypolynomial-timeapproximationschemes (FPTAS) for theproblem. In general, the research studies about themaximization of the number of just-in-time jobs encountered in the literature are limited to a two-machine flow shop problem. No constructive heuristicwas foundforam-machineflowshoporcomputationalexperiments,whichare important to evaluate theeffectivenessof themethodintermsofsolutionqualityandcomputationalefficiency.One of themaincontributionsof this research is thepresentationofefficientandeffectivesolutionmethods formaximizingthenumberof just-in-time jobswhicharedemonstratedtobeapplicable topractical multiple-machineflowshopproblems. Preliminaryresultsof this researcharepresented in [14,15]. 3.AMixedIntegerLinearProgrammingModel Theflowshop schedulingproblemcanbe generically formulated as follows. Consider a set ofn independent jobs (J= {J1, J2, ..., Jn}), all ofwhichhave the sameweight orpriority, cannot be interrupted,are releasedforprocessingatzero time,have tobeexecuted inmmachines (M={M1,M2, ...,Mm}) andarephysicallyarrangedto followidenticalunidirectional linearflows(i.e., all the jobs areprocessed throughthemachinesat thesamesequence). Each job (Jj) requiresaprocessing time (pjk) ineachmachine (Mk) andhave itsduedaterepresentedbydj, bothconsideredknownandfixed. Thesolutionconsistsoffindingaschedule thatmaximizes thenumberof jobsfinishedatexactly their respectiveduedates. To formulateamathematicalmodel torepresent theproblem,consider the followingparameters, indicesandvariables. 59