Tardiness minimisation for a customer order scheduling problem with sum-of-processing-time-based learning effect
研究了多机器环境下考虑学习效应的客户订单调度问题，目标是找到最小化订单总延迟的最优调度方案，提出了分支定界算法和多种启发式、元启发式算法。
During solving scheduling problems in a manufacturing system, the processing time of a job is commonly assumed to be independent of its position in a scheduling sequence. However, this independence assumption may not adequately reflect many real manufacturing situations. In fact, the job processing time usually steadily decreases as the process proceeds when the same task is performed repeatedly and the efficiency is, therefore, gradually increased. Inspired by these observations, this study addressed a customer order scheduling problem with sum-of-processing-time-based learning effect on multiple machines. The objective was to search an optimal schedule to minimise total tardiness of the orders. A branch-and-bound algorithm incorporating several dominance rules and a lower bound was first proposed for searching the optimal schedule. Four heuristics and three metaheuristics were then developed for searching near-optimal schedules. Extensive computational experiments were finally tested to evaluate the performances of all the proposed algorithms.