Page - 41 - in Algorithms for Scheduling Problems

algorithms Article SchedulingaSingleMachinewithPrimaryand SecondaryObjectives Nodari Vakhania ID CentrodeInvestigaciónenCiencias,UniversidadAutonomadelEstadodeMorelos,62210Cuernavaca,Mexico; nodari@uaem.mx Received: 27February2018;Accepted: 31May2018;Published: 5 June2018 Abstract:Westudyaschedulingprobleminwhich jobswithrelease timesandduedatesare tobe processedonasinglemachine.With theprimaryobjective tominimize themaximumjob lateness, theproblemisstronglyNP-hard.Wedescribeageneralalgorithmicschemetominimizethemaximum joblateness,withthesecondaryobjectivetominimizethemaximumjobcompletiontime.Theproblem of finding thePareto-optimal set of feasible solutionswith these twoobjective criteria is strongly NP-hard.WegivethedominancepropertiesandconditionswhenthePareto-optimalsetcanbeformed inpolynomial time.Theseproperties, togetherwithourgeneral framework,providethetheoretical background,so that thebasic frameworkcanbeexpandedto(exponential-time) implicit enumeration algorithmsandpolynomial-timeapproximationalgorithms(generatingtheParetosub-optimalfrontier withafairbalancebetweenthetwoobjectives). Someavailable in the literatureexperimental results confirmthepracticalefficiencyof theproposedframework. Keywords: scheduling singlemachine; release time; lateness; makespan; bi-criteria scheduling; Pareto-optimalsolution 1. Introduction Westudyaschedulingprobleminwhich jobswithreleasetimesandduedatesaretobeprocessed byasinglemachine. Theproblemcanbedescribedas follows. Therearen jobs j (j= 1,...,n)and a singlemachineavailable fromTime0. Every job jbecomesavailable at its release time rj, needs continuousprocessing time pj on themachineand is also characterizedby theduedate dj,which is the desirable timemoment for the completion of that job. These are are non-negative integral numbers.AfeasiblescheduleSassigns toeach job j thestartingtime tj(S), suchthat tj(S)≥ rj and tj(S)≥ tk(S)+pk, for any job k includedearlier inS; thefirst inequality says that a job cannotbe startedbefore its release time,andthesecondonereflects therestrictionthat themachinecanhandle atmostone jobata time. If job jcompletesbehinditsduedate, i.e., cj= tj(S)+pj> dj, then ithasa positive latenessLj= cj−dj, otherwise its lateness isnon-positive.Ourprimaryobjective is tofind a feasible schedule inwhich themaximumjob lateness is theminimalpossible amongall feasible schedules.However,wealsoconsiderasecondaryobjective tominimize themaximumjobcompletion timeor themakespan. TheproblemsinvolvingbothaboveobjectivecriteriaarestronglyNP-hard,and thetwoobjectives are, ingeneral, contradictory; i.e., bothof themcannotsimultaneouslybereached. Then,onemaylook forasubsetof feasiblesolutions thataresomehowacceptablewithrespect tobothobjectivecriteria. APareto-optimal frontier is constitutedbyasubsetofall feasible solutions thatarenotdominated bysomeother feasiblesolution, in thesense thatnoothersolutioncansurpass the formeronewith respect tobothobjectivevalues. FindingPareto-optimal frontieroftenremainsNP-hard,as it is inour case. Inparticular, for theproblemsoffindingamongall feasiblescheduleswithagivenmaximumjob latenessonewith theminimummakespan,andviceversa,amongall feasiblescheduleswithagiven makespan,findingonewith theminimummaximumjob lateness is stronglyNP-hard(seeSection2). Algorithms 2018,11, 80;doi:10.3390/a11060080 www.mdpi.com/journal/algorithms41