带无向环优先级的单机总加权完成时间调度问题

Single Machine Total Weighted Completion Time Scheduling with Undirected Cycle Precedence

单机调度是生产调度领域的一个经典问题,研究了工件间有加工优先级要求的单机总加权完成时间调度问题,考虑了若将工件优先级关系构成的优先级图视为无向图,包含有环的情况。针对该问题,设计了结合双向动态规划的拉格朗日松弛算法进行求解,使得可以求解一个工件可能有多个紧前或紧后工件的情况。大量实验测试结果表明,该算法能够在较短时间内得到令人满意的近优解。

Single machine scheduling is a classical problem in production scheduling. We study a single machine scheduling problem with processing precedence of jobs where cycles may exist if the precedence relations of jobs are viewed as an undirected graph. The objective is to minimize the total weighted completion time of jobs. Lagrangian relaxation combined with hybrid backward and forward dynamic programming is applied to solve this problem in order to deal with the case with multiple immediate predecessors or successors for a job. Experimental results show that this method can obtain satisfactory solutions within a shorter running time.