一类单机排序问题的新伪多项式时间精确算法

Exact Pseudo-polynomial Time Algorithms for a Single Machine Scheduling

本文以最小化所有工件的最大延误时间为目标,研究了带有工件释放时间和交付时间的单机排序问题。该问题是机器排序的经典基础性问题,是NP-hard问题。首先,从该问题的结构特征入手,通过揭示工件单机排序结构(各工件的排序位置)与工件最大延误时间(相比交付时间)之间的关联规律,从工件加工顺序链的视角考虑,建立了新的基于工件分配位置变量的0-1混合线性规划模型。该模型的结构特征具备更好的优化潜力。其次,结合Dantzig-Wolfe分解等整数优化理论和方法,对模型进行优化处理,进而开发出该单机排序问题的伪多项式时间精确算法。最后,通过仿真模拟测试验证算法的有效性。结果表明:该算法在计算该单机排序问题算例(特别是大型算例)的精确解方面具备显著的效率优势,例如,该算法能够在3000秒内计算出包含1200个工件规模的算例的最优解。

A single-machine scheduling problem with released times and due dates was considered.The objective was to decide the job sequence in order to minimize the maximum tardiness among all the jobs.This problem was a classical fundamental issues of machine scheduling.It was known as strong NPhard.Firstly,the relations and rules between the structure of jobs sequencing on single machine(the assignment and positional date of each job)and the maximum tardiness were discovered by analyzing the structure characteristics of the scheduling problem.A new 0-1 mixed linear programming formulations with assignment and positional date variables was formulated based on the above rules and the perspective of job-process-sequence-chain.The formulations could create a potential to use recent advancements found in the integer programming literature.Secondly,an exact pseudo-polynomial time algorithm for the considered single machine scheduling was explored by applying modern integer optimization theories and methods such as the Dantzig-Wolfe decomposition method to optimize the formulations.Finally,the validity of the algorithms was verified by computer experiments.The results show that the proposed algorithms are much more competitive for computing the optimal solutions of medium and large-size instances of the single-machine scheduling problem with release times and due dates.For example,the algorithm is capable of calculating the optimal solution for a problem instance with a scale of 1200workpieces within 3000 seconds.