单机订单接受与加工调度问题的拉格朗日松弛算法  

Lagrangian Relaxation Algorithm for Order Acceptance and Scheduling in a Single Machine Environment

作　　者：谢杏子 王秀利[2] XIE Xingzi;WANG Xiuli(School of Economics Management and Law,University of South China,Hengyang 421001,Hunan,China;School of Economics and Management,Nanjing University of Science and Technology,Nanjing 210094,China)

机构地区：[1]南华大学经济管理与法学学院,湖南衡阳421001 [2]南京理工大学经济管理学院,南京210094

出　　处：《系统管理学报》2020年第5期874-881,共8页Journal of Systems & Management

基　　金：国家自然科学基金面上项目(71871118);南华大学社科基金重点培育项目(2018XZX18)。

摘　　要：针对不同类型订单加工切换时机器需要准备时间的实际生产情况,研究了单机订单接受与加工调度优化决策问题,旨在最大化企业净收益。鉴于研究问题的强NP难属性,设计了基于拉格朗日松弛理论的启发式算法。首先,该算法通过加入相邻订单相异性约束以提高松弛解质量;其次,应用动态规划递推公式求解拉格朗日松弛问题;最后,利用问题的优化性质并基于贪婪规则构造原问题可行解。不同规模问题的实验结果表明,该算法能在合理计算时间内得到满意的近优解。This paper studies the single machine order acceptance and scheduling problem under the practical production situation that a setup time is incurred whenever there is a switch from the processing of an order in one class to one in another class.The objective is to maximize the total net revenue of the enterprise.Since this problem is NP-hard,a Lagrangian-based heuristic algorithm is developed in which the constraints on occurrences of successive orders are embedded to improve the relaxation solutions.The relaxation problem is solved by a dynamic programming with dynamic programming recursive formulas.After that,by utilizing the optimal properties and greedy rule,a feasible solution is obtained.The experimental results show that for problems of different scales,the proposed algorithm can obtain satisfactory near-optimal solutions within a reasonable time.

关 键 词：订单接受 调度 拉格朗日松弛 准备时间 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]