| 单机订单接受与加工调度问题的拉格朗日松弛算法 |
| |
| 引用本文： | 谢杏子,王秀利. 单机订单接受与加工调度问题的拉格朗日松弛算法[J]. 系统管理学报, 2020, 29(5): 874-881. DOI: 10.3969/j.issn.1005-2542.2020.05.005 |
| |
| 作者姓名： | 谢杏子 王秀利 |
| |
| 作者单位： | 1.南华大学 经济管理与法学学院，湖南 衡阳 421001； 2.南京理工大学 经济管理学院，南京210094 |
| |
| 基金项目： | 国家自然科学基金面上项目（71871118），南华大学社科基金重点培育项目（2018XZX18） |
| |
| 摘 要： | 针对不同类型订单加工切换时机器需要准备时间的实际生产情况，研究了单机订单接受与加工调度优化决策问题，旨在最大化企业净收益。鉴于研究问题的强NP难属性，设计了基于拉格朗日松弛理论的启发式算法。首先，该算法通过加入相邻订单相异性约束以提高松弛解质量；其次，应用动态规划递推公式求解拉格朗日松弛问题；最后，利用问题的优化性质并基于贪婪规则构造原问题可行解。不同规模问题的实验结果表明，该算法能在合理计算时间内得到满意的近优解。
|
| 关 键 词： | 订单接受 调度 拉格朗日松弛 准备时间 |
Lagrangian Relaxation Algorithm for OrderAcceptance and Scheduling in a Single Machine Environment |
| |
| XIE Xingzi,WANG Xiuli. Lagrangian Relaxation Algorithm for OrderAcceptance and Scheduling in a Single Machine Environment[J]. Systems Engineering Theory·Methodology·Applications, 2020, 29(5): 874-881. DOI: 10.3969/j.issn.1005-2542.2020.05.005 |
| |
| Authors: | XIE Xingzi WANG Xiuli |
| |
| Affiliation: | 1. Schoolof Economic Management and Law, Nanhua University, Hengyang 421001, Hunan, China;2. School of Economic and Management, Nanjing Universityof Science and Technology, Nanjing 210094, China |
| |
| Abstract: | 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. |
| |
| Keywords: | order acceptance scheduling Lagrangian relaxation setup times |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《系统管理学报》浏览原始摘要信息 |
|
点击此处可从《系统管理学报》下载全文 |
