The New Scheduling Problem On Two Parallel Machines

In recent years,scheduling problem has increasingly become one of the most con?cerned problems in the field of combinatorial optimization,and scheduling problem has been widely used in engineering management,logistics management,service industry and other fields of production and life.Generally,the goal of scheduling problem is to find an appropriate scheduling scheme,so that the maximum completion time of the machine is as small as possible.According to the practical problems,the researchers put forward the scheduling problem with penalty cost and the scheduling problem with hierarchical constraints.The scheduling problem with penalty cost is different from the original scheduling problem in that all tasks are not required to be machined entirely,if a task is accepted,it is scheduled to be machined on the machine,and if rejected,the penalty cost is paid.The goal of scheduling problem with penalty cost is to find an appropriate scheduling scheme,so that the sum of the maximum completion time of the machine and penalty cost of all rejected tasks is as small as possible.On the basis of studying the scheduling problem with penalty cost.We present the multidimensional scheduling problem with penalty cost on two parallel machines and design a 3-approximation algorithm.MWhen the dimension of task d is a fixed constant,a complete polynomial time approximation scheme with running time of O(n2d+1(1/ε)2d)is designed.According to the random rounding method,a 2.54-approximation algorithm is designed.When the information of multidimensional tasks is unknown,an online algorithm with a competition ratio of 2.618d is designed.The difference between the scheduling problem with hierarchical constraints and the original scheduling problem is that all tasks and machines have a hierarchy,and each machine can only process tasks of no less than its level.The goal of scheduling problem with hierarchical constraints is to find an appropriate scheduling scheme so that the maximum completion time of the machine is as small as possible.On the basis of studying the scheduling problem with hierarchical constraints.We study the prob-lem of scheduling for bag-of-tasks on two parallel machines under a grade-of-service provision,where the objective is to minimize the makespan.We design a semi-online algorithm with a competitive ratio of 3/2 when the optimal value is known;We design a semi-online algorithm with a competitive ratio of((?)+1)/2 when the largest pro-cessing time is known.The last section summarizes all the research results and proposes future research directions.