The just-in-time job-shop scheduling problem with distinct due-dates for operations
- PDF / 581,066 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 82 Downloads / 183 Views
The just-in-time job-shop scheduling problem with distinct due-dates for operations Mohammad Mahdi Ahmadian1 · Amir Salehipour1 Received: 14 November 2018 / Revised: 19 August 2020 / Accepted: 22 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In the just-in-time job-shop scheduling (JIT–JSS) problem every operation has a distinct due-date, and earliness and tardiness penalties. Any deviation from the due-date incurs penalties. The objective of JIT–JSS is to obtain a schedule, i.e., the completion time for performing the operations, with the smallest total (weighted) earliness and tardiness penalties. This paper presents a matheuristic algorithm for the JIT–JSS problem, which operates by decomposing the problem into smaller sub-problems, optimizing the sub-problems and delivering the optimal schedule for the problem. By solving a set of 72 benchmark instances ranging from 10 to 20 jobs and 20 to 200 operations we show that the proposed algorithm outperforms the state-of-the-art methods and the solver CPLEX, and obtains new best solutions for nearly 56% of the instances, including for 79% of the large instances with 20 jobs. Keywords Just-in-time scheduling · Earliness and tardiness · Matheuristic · Heuristic · Variable neighborhood search · Relax-and-solve
1 Introduction The job-shop problem is a classic and a well-known scheduling problem, in which every job consists of a set of operations that needs to be processed in a specific order by a set of machines such that a performance criterion is optimized. Due to its complexity (Garey et al. 1976) and numerous applications (French 1982) the problem has been extensively studied. Nonetheless, only few papers investigate the performance criterion of minimizing the (weighted) earliness and tardiness. Such a criterion is related to the just-in-time (JIT) policy because minimizing the earliness impacts, e.g.,
B
Amir Salehipour [email protected] Mohammad Mahdi Ahmadian [email protected]
1
School of Mathematical and Physical Sciences, University of Technology Sydney, Sydney, Australia
123
M. M. Ahmadian, A. Salehipour
the warehousing and inventory costs, and minimizing the tardiness leads to shorter delivery times, and therefore, to a higher level of customer satisfaction. The JIT job-shop scheduling problem is a variant of the classical job-shop scheduling, in which every job (operation) has a due-date and earliness and tardiness penalty coefficients, and any deviation from the due-date incurs penalties. More precisely, completing a job (an operation) before its due-date leads to earliness penalties and completing it after the due-date results in tardiness penalties. The objective function minimizes the total penalties of earliness and tardiness. Typically, two types of due-dates have been considered in the literature, namely the job-level and the operation-level. While the former includes a due-date for every job (and therefore all operations of the job share the same due-date), the latt
Data Loading...
