一种求解制造／再制造混合系统车间调度的启发式算法

针对传统方法在求解制造／再制造混合系统车间调度时存在的问题，根据制造／再制造混合系统车间调度的特点，提出了最早交货期一最长加工时间（earliest deliverydate-longest processing time fist，EDD-LPT）的启发式算法。首先，将全部工件按照交货期的时间非减排列，对于交货期相同的工件，则按照再制造修复时间非增排列。然后，依次将工件安排在修复费用最小的设备上。对于再制造修复费用和延迟交货费用之和大于新品制造费用的工件，则采用新品制造替换。最后，给出了EDD-LPT启发式算法的最坏误差界。实例研究表明，EDD-LPT启发式算法较传统方法在计算时长方面具有更好的性能。

A heuristic approach for solving scheduling problems in hybrid manufacturing/remanufacturing system

Given the existent problem of scheduling in hybrid manufacturing/remanufacturing system, a heuristic approach, i. e. , the earliest delivery date-longest processing time fist （EDD-LPT）, is proposed on the basis of the features of the hybrid manufac- turing/remanufacturing system. In first instance, all the workpieces are arranged in a non-decreasing order for the delivery time. For the workpieces with the same delivery, they will be arrayed in a non-increasing order in accordance with remanufacturing time. Then, the workpieces are arranged in equipment with the smallest repair costs successively. While the workpieces, whose sum of remanufacturing costs and delayed delivery costs are more than the costs for manufacturing new parts, are replaced by new parts. Finally, the worst error bounds of the EDD-LPT heuristic algorithm are given. Case study shows that the EDD-LPT heu- ristic algorithm outperforms than conventional methods in the time length of calculation.