Fast and efficient algorithms to handle the dynamism in a single machine scheduling problem with sequence-dependent setup times. (February 2021)

• Record Type: Journal Article
• Authors: Angel-Bello, Francisco; Vallikavungal, Jobish; Alvarez, Ada
• Is Part Of: Computers & industrial engineering. Volume 152(2021)
• Publication Date: 2021-02
• Subjects: Dynamic scheduling -- Single machine -- Sequence-dependent setup times -- Makespan; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106984
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: 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. Abstract: 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.