The Total Tardiness Scheduling And The Discretely Controllable Scheduling

Due to its profound significance in both real background and practical future, scheduling theory has been an important part of combinatorial optimization. With the development of modern industry, many classical scheduling models have been breach, and many relatively new scheduling models appear, and the models of the scheduling with discretely controllable(compressible) processing times or release times develop rapidly, which are attracting more and more attention recently. In classical scheduling models, the total tardiness scheduling with precedence constraints is NP-hard. In this dissertation, many new results of the five models of the scheduling with discretely compressible processing times and release times and the total tardiness scheduling on complexities and algorithms are presented.I The discretely controllable scheduling1. We consider the single machine scheduling problem with discretely compressible processing times, and the objective is to minimize makespan under the limited total compressible cost(with the constraint of total compression cost). Jobs may have different release times. We design for the first time pseudo-polynomial time algorithm by approach of dynamic programming and FPTAS.2. We consider the scheduling problem with discretely compressible processing times, and the objective is to minimize makespan under the limited total compressible cost (with the constraint of total compression cost). For the identical-parallel-machine version with simultaneous release times, we design for the first time pseudo-polynomial time algorithm by approach of dynamic programming and FPTAS.3. We consider the scheduling problem with discretely compressible release times, and the objective is to minimize the sum of makespan plus total compression cost. We show it is strongly NP-hard, and we design an optimal algorithm to choose release times after a given arbitrary schedule, furthermore, we conclude that there always exsits the approximation algorithm with worst-case ratio 2 which is the best possible.II The total tardiness scheduling1. The total tardiness scheduling with precedence constraint is NP-hard, while there have been many approximation algorithms for total tardiness scheduling without precedence constraints, including the backward-shift algorithm, no papers have dealt with ones for the total tardiness scheduling with precedence constraints up to now. In this paper, an approximation algorithm with polynomial complexity is presented by transplanting the backward-shift algorithm to the case with precedence constraints, which can get its approximation solution quickly.2. Emmons conditions being the foundation for solving the total tardiness scheduling, an improved one and the prescheduled algorithm are proposed by Tao Lin and Tang Guochun. In this paper a simplified proof on the improved Emmons conditions and a perfect prescheduled algorithm are presented.