带包容性处理集限制的作业接受与两台并行机调度问题的拉格朗日松弛算法  

A Lagrangian Relaxation Heuristic for Order Acceptance and Scheduling on Two Parallel Machines with Inclusive Processing Set Restrictions

作　　者：朱倩倩 王秀利[1] ZHU Qianqian;WANG Xiuli(School of Economics and Management,Nanjing University of Science and Technology,Nanjing,Jiangsu 210094,China)

机构地区：[1]南京理工大学经济管理学院,江苏南京210094

出　　处：《工业工程与管理》2023年第4期28-37,共10页Industrial Engineering and Management

基　　金：国家自然科学基金资助项目(71871118)。

摘　　要：在资源主体加工能力有限和客户作业需要承诺交货期限的双重约束下,本文研究具有包容性处理集限制的作业接受与并行机调度问题,其目标是最大化资源主体收益。研究问题中,资源主体拥有两台加工速度相同,但功能不同的机器,其中一台机器的可处理作业集合是另一台机器可处理作业集合的子集或超集。针对该NP难问题,基于拉格朗日松弛技巧设计了一种高效的启发式算法。广泛的数值实验结果显示,拉格朗日松弛启发式算法结果与最优解平均相差不超过7.5%,该算法能够在合理的时间内获取大规模问题的优化解。The order acceptance and scheduling problem in a two-parallel machines environment with inclusive processing set restrictions were studied.In this problem,the manufacturer possessed two parallel machines,which had the same processing speed,but differed from each other in their functionality.Each customer order was compatible with only a subset of those machines.The problem was NP-hard,so a heuristic based on the Lagrangian relaxation technique was developed.The performance of the heuristic via computational experiments was evaluated.The computational results show that the heuristic based on the Lagrangian relaxation technique is efficient and effective in approximately solving large-sized instances of the problem.The results of the heuristic differ from the optimal solutions by an average of 7.5%.

关 键 词：并行机调度 作业接受 包容性处理集 拉格朗日松弛算法 

分 类 号：F273[经济管理—企业管理]