论文部分内容阅读
针对带多处理器任务的混合流水车间调度问题,以总加权完成时间为目标函数,考虑加工阶段间运输时间和工件动态到达的生产特征,提出了一种基于代理次梯度法的改进拉格朗日松弛算法.算法采用每次迭代只最优求解几个拉格朗日子问题的异步迭代策略,利用代理次梯度获得合适的乘子更新方向.分别应用所提出的改进算法和常规的基于次梯度法的拉格朗日松弛算法对多达150个工件的问题进行仿真测试,结果表明,所提出的改进算法比常规拉格朗日松弛算法表现出更好的求解能力,尤其是求解大规模问题.“,”Multiprocessor task scheduling in hybrid flowshops is studied with the objective of minimizing the sum of weighted completion time of all jobs.In the hybrid flowshop,the production characteristics of transportation time and job dynamic arrival are considered.An improved Lagrangian relaxation algorithm combined with a surrogate subgradient method is then presented to solve the above problem where the asynchronous iterative strategy is applied.In this way,only several subproblems are minimized at each iteration so that an adaptive multiplier update direction is obtained using the surrogate subgradient.Numerical experiments are performed on randomly generated test problems with up to 150 jobs and the results indicate that the designed method can obtain better feasible solutions within a shorter computation time especially for large-scale problems,compared with regular Lagrangian relaxation.