Abstract: In order to satisfy the demands for job processing order and arrival time in practical production environment, this paper studies a single machine total weighted tardiness scheduling problem with some novel features. These features are that each job has a release date and the precedence graph formed by job precedence relations is unconnected and consists of undirected loop. A mathematical programming model is then formulated. Further, Lagrangian relaxation combined with hybrid backward and forward dynamic programming is proposed to solve this problem as an extension of Tang and Xuan et al. In this algorithm, hybrid backward and forward dynamic programming is designed to deal with the case that a job may have multiple predecessors or successors. A subgradient algorithm is then used to update Lagrangian multipliers and a heuristic algorithm is presented to construct a feasible schedule based on the solutions of the Lagrangian relaxation problem. Experimental results show that this algorithm can obtain satisfactory solutions within a shorter computation time and it can provide an idea to solve more complicated scheduling problems.

Key words: systems engineering, single machine total weighted tardiness scheduling, lagrangian relaxation, unconnected precedence graph, hybrid backward and forward dynamic programming

摘要： 为满足实际生产环境对工件加工顺序和工件到达时间的要求,提出了具有新特征的单机总加权拖期调度问题,其特点体现在:工件有动态到达时间,且由工件优先级关系构成的优先级图为非连接图且存在环的情况,对该问题建立数学规划模型,在扩展Tang和Xuan等的基础上,提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中,提出双向动态规划算法求解拉格朗日松弛问题,使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况,采用次梯度算法更新拉格朗日乘子,基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示,所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解,为更复杂的调度问题的求解提供了思路。

关键词: 系统工程, 单机总加权拖期调度, 拉格朗日松弛算法, 非连接优先级图, 双向动态规划