系统管理学报

系统管理学报 ›› 2020, Vol. 29 ›› Issue (5): 874-881.DOI: 10.3969/j.issn.1005-2542.2020.05.005

• 运筹学与工业工程 • 上一篇    下一篇

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

谢杏子1，王秀利2   

  1. 1.南华大学 经济管理与法学学院，湖南 衡阳 421001； 2.南京理工大学 经济管理学院，南京210094

  • 出版日期:2020-09-29 发布日期:2020-10-23
  • 作者简介:谢杏子（1990-），女，讲师。研究方向为调度理论与优化、供应链管理。
  • 基金资助:
    国家自然科学基金面上项目（71871118），南华大学社科基金重点培育项目（2018XZX18）

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

XIE Xingzi, WANG Xiuli   

  1. 1. School of Economic Management and Law, Nanhua University, Hengyang 421001, Hunan, China; 2. School of Economic and Management, Nanjing University of Science and Technology, Nanjing 210094, China
  • Online:2020-09-29 Published:2020-10-23

PDF

摘要：

针对不同类型订单加工切换时机器需要准备时间的实际生产情况，研究了单机订单接受与加工调度优化决策问题，旨在最大化企业净收益。鉴于研究问题的强NP难属性，设计了基于拉格朗日松弛理论的启发式算法。首先，该算法通过加入相邻订单相异性约束以提高松弛解质量；其次，应用动态规划递推公式求解拉格朗日松弛问题；最后，利用问题的优化性质并基于贪婪规则构造原问题可行解。不同规模问题的实验结果表明，该算法能在合理计算时间内得到满意的近优解。

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

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.

Key words: order acceptance, scheduling, Lagrangian relaxation, setup times

中图分类号: