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.