Rescheduling problems typically arise from production facilities that have to deal with incoming new orders for which it is not optimal to be simply scheduled at the end of an existing schedule of old jobs. A rescheduling of all jobs, old and new, is therefore allowed without disrupting too much the existing schedule. This kind of approach enables flexibility in the system while not disturbing too much the commitments with the customers. In this paper, we provide structural properties and a Branch & Memorize algorithm to solve a rescheduling problem on a single machine, where no idle times are allowed. To the authors knowledge, this is the first exact algorithm that solves a rescheduling problem with a constraint on the total absolute time-based disruption over all old jobs. The algorithm uses a fast heuristic to compute an initial upper bound and then exploits memorization techniques to cut dominated schedules. This solution method is shown to outperform an Integer Programming formulation solved by CPLEX and it is able to solve within 900 CPU seconds all instances with 10, 20, 30 jobs and most of those with 40 jobs.
Single machine rescheduling for new orders with maximum lateness minimization / Rener, Elena; Salassa, Fabio; T’Kindt, Vincent. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 144:(2022). [10.1016/j.cor.2022.105815]
Single machine rescheduling for new orders with maximum lateness minimization
Rener, Elena;Salassa, Fabio;
2022
Abstract
Rescheduling problems typically arise from production facilities that have to deal with incoming new orders for which it is not optimal to be simply scheduled at the end of an existing schedule of old jobs. A rescheduling of all jobs, old and new, is therefore allowed without disrupting too much the existing schedule. This kind of approach enables flexibility in the system while not disturbing too much the commitments with the customers. In this paper, we provide structural properties and a Branch & Memorize algorithm to solve a rescheduling problem on a single machine, where no idle times are allowed. To the authors knowledge, this is the first exact algorithm that solves a rescheduling problem with a constraint on the total absolute time-based disruption over all old jobs. The algorithm uses a fast heuristic to compute an initial upper bound and then exploits memorization techniques to cut dominated schedules. This solution method is shown to outperform an Integer Programming formulation solved by CPLEX and it is able to solve within 900 CPU seconds all instances with 10, 20, 30 jobs and most of those with 40 jobs.File | Dimensione | Formato | |
---|---|---|---|
1-s2.0-S0305054822000995-main.pdf
non disponibili
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Non Pubblico - Accesso privato/ristretto
Dimensione
655.76 kB
Formato
Adobe PDF
|
655.76 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2962104