Treffer: Fast and efficient algorithms to handle the dynamism in a single machine scheduling problem with sequence-dependent setup times.

• This work addresses a dynamic scheduling problem with sequence-dependent setup times. • Two strategies are proposed to handle the problem using a periodic rescheduling approach. • Three algorithm variants are designed, implemented and tested for each strategy. • To assess the solution quality of the best method, a perfect information model is presented. • The experiments show that our best variant is fast and reach high quality solutions. In this paper we study the makespan minimization in a dynamic single-machine scheduling problem with sequence-dependent setup times, where the dynamism is triggered by the arrival of new jobs through the production process, with unknown, in advance, release times. To solve it we use the periodic rescheduling approach, where the production horizon is divided into time intervals and a re-optimization process is launched at the beginning of each interval to obtain an initial schedule which is generally modified due to the arrival of new jobs. We implement two rescheduling strategies. The first one uses all the available jobs at the beginning of each interval to obtain a sequence with minimum makespan. In the second strategy, instead of scheduling all available jobs, we design an iterative insert-improve algorithm that tries to schedule only those jobs that can be completed until the next re-optimization point. Its aim is not to spend time scheduling jobs that could later be rescheduled. To implement these two strategies we design a constructive procedure and three improvement procedures: a composite local search and other two based on the Iterated Greedy metaheuristic. Using these strategies we integrate three algorithms for each strategy. These algorithms are easy to code in a computer language due to the simplicity of the designed components. Moreover, the computational experimentation on instances with different levels of dynamism showed that the proposed algorithms are very fast and provide high quality solutions. [ABSTRACT FROM AUTHOR]

Copyright of Computers & Industrial Engineering is the property of Pergamon Press - An Imprint of Elsevier Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)