Minimizing total tardiness for the single-machine identical-jobs order scheduling problem with a learning effect

  • This paper considers a single machine identical-jobs order scheduling problem with a position-dependent learning effect (SIOSLE) to minimize the total tardiness. A learning effect is common in the identical-jobs order manufacturing, such as clothing, bicycles, shoes, and so on, but its impact on the order scheduling problem has not been studied, especially for orders with different numbers of the same type of jobs. A mixed integer programming (MIP) model is first formulated for SIOSLE and serves as a benchmark. A new branch-and-bound algorithm was developed to handle computational complexity based on the Dominance, Split, Elimination, and Decomposition rules revised from the traditional job scheduling problem and new lower and upper bounds. Numerical experiments demonstrate that the proposed branch-andbound algorithm is computationally better than the performance of using Gurobi, a popular commercial solver, to solve the MIP. The experiments for large-sized problems found that the proposed branch-and-bound algorithm can solve instances with up to 120 orders. The algorithm is more efficient for instances with a strong or weak learning effect, with tight or loose due dates, or with heterogeneous due dates. The effectiveness of the Dominance, Split, Elimination, and Decomposition rules varies with parameter settings. In addition, the proposed branch-and-bound algorithm can yield better solutions than traditional meta-heuristic algorithms butmay require longer run time for large instances.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Jinchang Hu, Mingzhou JinORCiD
DOI:https://doi.org/10.1007/s12532-024-00271-x
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2024
Volume:17
Issue:1
Page Number:31
First Page:141
Last Page:171
Mathematical Programming Computation :MPC 2025 - Issue 1
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.