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

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

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

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.