Tardiness minimisation for a customer order scheduling problem with sum-of-processing-time-based learning effect. Issue 3 (4th March 2019)

• Record Type: Journal Article
• Authors: Wu, Chin-Chia; Lin, Win-Chin; Zhang, Xingong; Chung, I-Hong; Yang, Tzu-Hsuan; Lai, Kunjung
• Is Part Of: Journal of the Operational Research Society. Volume 70:Issue 3(2019)
• Page Start: 487
• Page End: 501
• Publication Date: 2019-03-04
• Subjects: Order scheduling -- metaheuristic -- tardiness -- sum-of-processing-time-based learning; Operations research -- Periodicals; 658.4034
• DOI: 10.1080/01605682.2018.1447249
• Languages: English
• ISSNs: 0160-5682

Abstract

Abstract: 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.