A tabu-searchalgorithmforschedulingjobswithcontrollableprocessing times onasinglemachinetomeetdue-dates

In manyreal-worldproductionsystems,itisimportanttoschedulejobssuchthattheycouldbe processedandshippedwithnodelay.Inthispaper,weconsidertheproblemofscheduling n jobs with arbitraryreleasedatesandduedatesonasinglemachine,wherejob-processingtimescanbecontrolled by theallocationofacommonresource,andtheoperationismodeledbyanon-linearconvexresource consumptionfunction.Theobjectiveistoobtainanoptimalprocessingpermutationaswellasan optimalresourceallocation,suchthatallthejobscanbefinishednolaterthantheirduedates,andthe total resourceconsumptioncanbeminimized.Theproblemisstrongly NP- hard.Atwo-layer- structuredalgorithmbasedonthetabu-searchispresented.Thecomputationalresult,comparedwith that fromabranchandboundalgorithm,showsthealgorithmiscapableofproducingoptimalornear optimalsolutionforlarge-sizedproblemsinanacceptablecomputationaltime.