Solvingastochasticsinglemachineproblemwithinitialidletime and quadraticobjective

Westudyastaticsinglemachineschedulingprobleminwhichprocessingtimesarestochastic,due- dates andpenaltiesfornotcompletingjobsontimearedeterministic,andaninitialfixedidletimeis allowedtobeinsertedbeforetheprocessingofthefirstjobbeginsonthemachine.Theobjectiveisto determine the optimal sequenceandthe optimal initial idletimethatjointlyminimizetheexpected valueofthesumofaquadraticcostfunctionofidletimeandtheweightedsumofaquadraticfunction of joblateness.TheproblemisNP-hardtosolve;however,wedevelopanexactalgorithmbasedona precedence relationstructureamongadjacentjobs.Ourextensivecomputationalresultsshowthatthe algorithm cansolvelargeprobleminstancesquickly.Wealsodemonstratethattheproposedproblemis generalinthesensethatitsspecialcasesreducetonewstochasticmodelswhileitslimitingcases simplify tosomedeterministicmodels.