CAJ | 학술논문

为满足实际生产环境对工件加工顺序和工件到达时间的要求，提出了具有新特征的单机总加权拖期调度问题，其特点体现在：工件有动态到达时间，且由工件优先级关系构成的优先级图为非连接图且存在环的情况，对该问题建立数学规划模型，在扩展Tang和Xuan等的基础上，提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中，提出双向动态规划算法求解拉格朗日松弛问题，使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况，采用次梯度算法更新拉格朗日乘子，基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示，所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解，为更复杂的调度问题的求解提供了思路。
위만족실제생산배경대공건가공순서화공건도체시간적요구，제출료구유신특정적단궤총가권타기조도문제，기특점체현재：공건유동태도체시간，차유공건우선급관계구성적우선급도위비련접도차존재배적정황，대해문제건립수학규화모형，재확전Tang화Xuan등적기출상，제출료결합쌍향동태규화적랍격랑일송이산법구해해문제。재해산법적설계중，제출쌍향동태규화산법구해랍격랑일송이문제，사득타가처리우선급도중일개공건가능유다개긴전혹긴후공건적정황，채용차제도산법경신랍격랑일승자，기우랍격랑일송이문제적해설계계발식산법구조가행해。실험측시결과현시，소설계적랍격랑일송이산법능구재교단적운행시간내득도령인만의적근우해，위경복잡적조도문제적구해제공료사로。
In order to satisfy the demands for job processing order and arrival time in practical production environ -ment, 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 pro-gramming is designed to deal with the case that a job may have multiple predecessors or successors .A subgradi-ent 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 .