In many production systems, maintenance activities including preventive maintenance, repairs and tool changes are periodically scheduled. The activities can revert the machine from a sub-normal processing rate to a normal one. In this paper, we study a single machine scheduling problem where deteriorating jobs and flexible periodic maintenance are considered. The single machine is operated to process a set of jobs with alternating processing periods and maintenance periods. In a processing period, a subset of jobs is sequentially processed and the completion time of the last job cannot exceed the allowed maximum duration. The actual processing time of each job grows at a linear job-specific deterioration rate and depends on its starting time within the period. Between two processing periods, a maintenance period with a fixed duration exists and the maintenance activities are carried out so that the processing rate of the machine is reverted to the normal rate. The objective is to schedule all the jobs to a set of processing periods and to minimize the makespan of the schedule. We formulate the problem using a set-partitioning model and, for a solution method, we make use of a branch-and-price algorithm. A label-setting algorithm with a dominance rule is designed to solve the pricing problem in column generation. Computational experiments are conducted on a set of randomly generated test instances to evaluate the performance of the proposed method.

Wang, T., Baldacci, R., Lim, A., Hu, Q. (2018). A branch-and-price algorithm for scheduling of deteriorating jobs and flexible periodic maintenance on a single machine. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 271(3), 826-838 [10.1016/j.ejor.2018.05.050].

A branch-and-price algorithm for scheduling of deteriorating jobs and flexible periodic maintenance on a single machine

Baldacci, Roberto;
2018

Abstract

In many production systems, maintenance activities including preventive maintenance, repairs and tool changes are periodically scheduled. The activities can revert the machine from a sub-normal processing rate to a normal one. In this paper, we study a single machine scheduling problem where deteriorating jobs and flexible periodic maintenance are considered. The single machine is operated to process a set of jobs with alternating processing periods and maintenance periods. In a processing period, a subset of jobs is sequentially processed and the completion time of the last job cannot exceed the allowed maximum duration. The actual processing time of each job grows at a linear job-specific deterioration rate and depends on its starting time within the period. Between two processing periods, a maintenance period with a fixed duration exists and the maintenance activities are carried out so that the processing rate of the machine is reverted to the normal rate. The objective is to schedule all the jobs to a set of processing periods and to minimize the makespan of the schedule. We formulate the problem using a set-partitioning model and, for a solution method, we make use of a branch-and-price algorithm. A label-setting algorithm with a dominance rule is designed to solve the pricing problem in column generation. Computational experiments are conducted on a set of randomly generated test instances to evaluate the performance of the proposed method.
2018
Wang, T., Baldacci, R., Lim, A., Hu, Q. (2018). A branch-and-price algorithm for scheduling of deteriorating jobs and flexible periodic maintenance on a single machine. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 271(3), 826-838 [10.1016/j.ejor.2018.05.050].
Wang, Ting; Baldacci, Roberto; Lim, Andrew; Hu, Qian
File in questo prodotto:
Eventuali allegati, non sono esposti

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: https://hdl.handle.net/11585/654311
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 53
  • ???jsp.display-item.citation.isi??? 41
social impact