| Parallel machine and flow-shop scheduling problems are one kind of multiprocessor scheduling problems；its research has important significance in both theory and applicationThis paper considers four scheduling problems,and discusses theircomplexity and heuristic algorithms First,the complexity of a two—machine parallel scheduling problem wim a single server is studiedSetup times are considered first if a job must be loaded on a machine Weassume mat all setup times have to be done by a single server,which canhandle at most one job at a time The objective is to determine a feasibleschedule,which minimizes the makespan It was proposed that all releasetimes existed and all processing times were constant,the problem wasstill NP—hard in the strong sense Second,the complexity of atwo—machine flow-shop scheduling problem is studied The objective is todetermine a feasible schedule,which minimizes the maximal makespanBetween the completion of an operation and the beginning of the nextoperation of the same job,there is a time lag,which we refer to it as thetransportation delays All transportation delays have to be done by asingle robot．which can perform at most one transportation at a time Thisproblem for special case isNP—hard in the strong sense Third．thecomplexity of a two—machine flow-shop scheduling problem is studiedThe objective is to determine a feasible schedule,which minimizes theweighted sum of completion times This problem for special case is NP—hard in the strong sense For a new heuristic algorithm．theworst—case performance is3/2,and the bound is tight The last,thecomplexity of a two—machine flow-shop scheduling problem wim releasetimes is studied The objective is to determine a feasible schedule,whichminimizes the weighted sum of completion times Release dates,,maybe given for the jobs This problem for special case isNPhard in thestrong sense For a new heuristic algorithm,the worst—case performance is3/2,andtheboundistight...
|
PDF Full Text Request