Research On Some Inverse Scheduling Problems

In this thesis, we study some inverse problems of scheduling. Firstly, we study two inverse scheduling problems on identical parallel machines:the inverse scheduling problem of the total weighted completion time problem with unit processing time on identical parallel machines;the inverse scheduling problem of the total completion time objective on identical parallel machines. Then we study the inverse scheduling problem with maximum tardiness objective on single machines.The thesis consists of five parts. In Chapter1, we introduce some concepts and results used in following chapters about combinatorial optimization;scheduling problems; inverse scheduling problems and research background of the inverse scheduling problems; the quadratic programming problem and Karush-Kuhn-Tucker conditions to solve some nonlinear programming problems; three types of norms l1,l2and l∞.In Chapter2, we study the inverse problem Pm|pj=1, INV|∑jn=1wjCj of the total weighted completion time problem with unit processing time on identical parallel machines Pm|pj=1|∑jn=1wjCj for three types of norms l1,l2and l∞. In this inverse scheduling problem, the weight w=(w1, W2,..., wn)T are minimally adjusted so that a given target job sequence becomes an optimal schedule for different norms under the constraints that the resulting objective value based on the adjusted weights is no more than the original objective value. We have produced their mathematical programming formulations under different norms. We can solve these formulations effectively and obtain the optimal solution to this inverse scheduling problem.In Chapter3, we firstly study the necessary and sufficient conditions for optimality of the total completion time objective on parallel machines Pm||∑jn=1Cj.Next, we study the inverse scheduling problem Pm|INV|∑jn=1Cj of the total completion time objective on parallel machines in which the processing times p=(p1,P2,...,Pn)T are minimally adjusted, so that the given schedule σ is satisfying the necessary and sufficient conditions for optimality of the scheduling problem Pm||∑jn=1Cj and becomes optimal with respect to p=(p1,p2,...,pn)T.We have presented the necessary and sufficient conditions for optimality of the total completion time objective on parallel machines. We have obtained the mathematical programming formulations for this inverse scheduling problem with different norms and provided efficient solution algorithms.In Chapter4, we firstly study the necessary and sufficient conditions for optimality of the forward scheduling problem1|Tmax. Next, we research the inverse scheduling problem of the maximum tardiness objective on single machine. In this inverse scheduling problem, the typical processing times and due dates are given together with a target job schedule π or a target value T*of the objective function Tmax. Schedule7r may not be optimal for the given values of processing times and due dates. The objective is to modify the typical processing times and due dates within certain limits to be as close to the typical ones as possible so that the target job sequence becomes optimal or so that the maximum tardiness Tmax is no more than a target value T*. We have presented the necessary and sufficient conditions for optimality of the maximum tardiness problem on single machines, also have given the mathematical formulations of the inverse scheduling and method of solving this inverse scheduling problem. For some special cases of the inverse scheduling problems, we have obtained the formulations for the optimal solutions.At last, we make a summary of our thesis, and discuss what we can do in the future.