This paper considers single-machine scheduling problems in which a given solution, i.e., an ordered set of jobs, has to be improved as much as possible by re-sequencing the jobs. The need for rescheduling may arise in different contexts, e.g., due to changes in the job data or because of the local objective in a stage of a supply chain that is not aligned with the given sequence. A common production setting entails the movement of jobs (or parts) on a conveyor. This is reflected in our model by facilitating the re-sequencing of jobs via a buffer of limited capacity accessible by a LIFO policy. We consider the classical objective functions of total weighted completion time, maximum lateness and (weighted) number of late jobs and study their complexity. For three of these problems, we present strictly polynomial-time dynamic programming algorithms, while for the case of minimizing the weighted number of late jobs NP-hardness is proven and a pseudo-polynomial algorithm is given.

Nicosia, G., Pacifici, A., Pferschy, U., Resch, J., Righini, G. (2021). Optimally rescheduling jobs with a Last-In-First-Out buffer. JOURNAL OF SCHEDULING, 24(6), 663-680 [10.1007/s10951-021-00707-5].

Optimally rescheduling jobs with a Last-In-First-Out buffer

Pacifici A.
Membro del Collaboration Group
;
2021

Abstract

This paper considers single-machine scheduling problems in which a given solution, i.e., an ordered set of jobs, has to be improved as much as possible by re-sequencing the jobs. The need for rescheduling may arise in different contexts, e.g., due to changes in the job data or because of the local objective in a stage of a supply chain that is not aligned with the given sequence. A common production setting entails the movement of jobs (or parts) on a conveyor. This is reflected in our model by facilitating the re-sequencing of jobs via a buffer of limited capacity accessible by a LIFO policy. We consider the classical objective functions of total weighted completion time, maximum lateness and (weighted) number of late jobs and study their complexity. For three of these problems, we present strictly polynomial-time dynamic programming algorithms, while for the case of minimizing the weighted number of late jobs NP-hardness is proven and a pseudo-polynomial algorithm is given.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore MAT/09
English
Complexity
Dynamic programming algorithms
Rescheduling
Scheduling
Sequence coordination
Supply chain sustainability
Nicosia, G., Pacifici, A., Pferschy, U., Resch, J., Righini, G. (2021). Optimally rescheduling jobs with a Last-In-First-Out buffer. JOURNAL OF SCHEDULING, 24(6), 663-680 [10.1007/s10951-021-00707-5].
Nicosia, G; Pacifici, A; Pferschy, U; Resch, J; Righini, G
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
JOSH-D-20-00102_R2 copy.pdf

solo utenti autorizzati

Descrizione: pdf preprint
Tipologia: Documento in Pre-print
Licenza: Copyright dell'editore
Dimensione 1.69 MB
Formato Adobe PDF
1.69 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2108/304211
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact