关键词: 单机排序, 总误工, 0-1混合线性规划, 伪多项式时间精确算法, Dantzig-Wolfe分解

Abstract: Scheduling is motivated by questions that arise generally in all situations in which scarce resources have to be allocated to activities over time, such as production planning, balancing processes sent to compute nodes, and telecommunication. One of the most representatives is the machine scheduling. Some simplest and most studied scheduling problems involve due date-based objectives on a single machine. These problems deal with scheduling multiple tasks that compete for service on a single resource, or with a machine to meet some objective concerning due dates of tasks. A frequently encountered due date-based objective is to minimize the total tardiness of all the tasks where total tardiness scheduling models have received considerable and increasing attention from the scheduling community, due to their practical importance and relevance. The total tardiness problem with release times on a single machine is NP-hard in the strong sense. This paper focuses on single machine scheduling problem with release times and total tardiness.
In order to obtain the optimal solution of the considered single machine scheduling with release times and total tardiness, this paper develops approaches of mixed integer programming formulations and optimization algorithms. The mixed integer programming formulations for scheduling problems are often classified based on the choice of the decision variables. The different decision variables used to distinguish different scheduling formulations are: (i) completion time variables, (ii) time index variables, (iii) linear ordering variables, and (iv) assignment and positional date variables. The Formulation (i) often appears in textbooks and other literature that simply formulate/describe the problem and it clearly does not generally perform well in practice. The Formulation (iv) creates a potential to use recent advancements found in the integer programming literature. This paper analyzes the relationships between the sequence position of each task on the single machine and the tardiness of the task. Based on the relationships, this paper formulates a new improved Formulation (iv) for the considered single machine scheduling based on binary variable to decide the sequence processing position of each job on the machine.
This paper explores potential to use recent advancements through analyzing the structure characteristics of the above improved Formulation (iv), and then applies integer optimization theories and methods, such as the Dantzig-Wolfe decomposition, to optimize the formulations. The decomposition-based approaches have great convergence. This paper further proves the strong duality of both of the muster-and sub-models generated by the Dantzig-Wolfe decomposition for the improved Formulation (iv), which means that the linear relaxations of the two models still keep the optimality. Based on the above findings, this paper presents simpler exact pseudo-polynomial time algorithms to compute the optimal solution of the improved Formulation (iv) much more efficiently. Through computational experiments, this paper verifies that the proposed algorithms can be applied to compute the optimal solutions of instances even containing more than 1000 tasks in 2000 seconds. The experiments evaluate the accuracy and much more competitive efficiency of the new algorithms.
The relationships between the sequence position of each mask on the single machine and the tardiness of the mask are the foundations to formulate the improved Formulation (iv) with more potential optimization. Furthermore, for the improved Formulation (iv), the Dantzig-Wolfe decomposition even can be regarded as the appropriative method: it not only achieves the best computational convergence but also keeps the optimality of the primal formulation. Inspired by these conclusions, the above relationships and the methods of formulating the above Formulation (iv) may also create better potentials for optimizing the parallel machine scheduling with release times and total tardiness. The future research of this paper will focus on the parallel machine scheduling.

Key words: single machine scheduling, total tardiness, 0-1 mixed linear programming, exact pseudo-polynomial time algorithm, Dantzig-Wolfe decomposition