期刊
COMPUTERS & INDUSTRIAL ENGINEERING
卷 152, 期 -, 页码 -出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2020.106984
关键词
Dynamic scheduling; Single machine; Sequence-dependent setup times; Makespan
资金
- FEDER funds [BU071G19, COV2000375, BU056P20]
- Spanish Ministry of Economy and Competitiveness [ECO2016-76567-C4-2-R, PID2019-104263RB-C44]
- Regional Government of Castilla y Leon
- Tecnologico de Monterrey
This paper investigates the makespan minimization in a dynamic single-machine scheduling problem with sequence-dependent setup times, and proposes two rescheduling strategies with corresponding algorithms. Experimental results show that these algorithms are fast and provide 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据