A dynamic differential evolution algorithm for the dynamic single-machine scheduling problem with sequence-dependent setup times
Authors:
- 28 May 2019
- journal article
- research article
- Published by Taylor & Francis in Journal of the Operational Research Society
- Vol. 71 (2) , 225-236
Abstract
The paper studies the single-machine scheduling problem with sequence-dependent setup times under dynamic environment. In this problem, jobs arrive over time and all the information on a job is unknown in advance. The objective is to find a feasible schedule such that the maximum lateness is minimised. This problem represents a very important production scheduling problem but remains under-represented in the literature. To solve the problem, we propose a dynamic differential evolution algorithm that considers the new environment and the previous environment simultaneously. The performance of the algorithm is enhanced by two heuristics for generating efficient initial solutions, a local search procedure and a speed-up method. To evaluate its performance, the proposed algorithm is tested on 1000 instances from the literature. The computational results demonstrate that the proposed algorithm is highly effective as compared to the methods known from the literature.Keywords
Funding Information
- National Natural Science Foundation of China (71202151)
- National 863 High-Tech Research and Development Program of China (2013AA040704)
- State Key Laboratory of Synthetical Automation for Process Industries Fundamental Research Funds (2013ZCX02)
This publication has 42 references indexed in Scilit:
- Incorporating learning effect and deterioration for solving a SDST flexible job-shop scheduling problem with a hybrid meta-heuristic approachInternational Journal of Computer Integrated Manufacturing, 2013
- An Adaptive Differential Evolution Algorithm for Global Optimization in Dynamic EnvironmentsIEEE Transactions on Cybernetics, 2013
- A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterionComputers & Operations Research, 2012
- Optimization in dynamic environments: a survey on problems, methods and measuresSoft Computing, 2010
- Differential Evolution: A Survey of the State-of-the-ArtIEEE Transactions on Evolutionary Computation, 2010
- A GRASP based on DE to solve single machine scheduling problem with SDSTComputational Optimization and Applications, 2010
- A survey of scheduling problems with setup times or costsEuropean Journal of Operational Research, 2008
- Scheduling flow shops using differential evolution algorithmEuropean Journal of Operational Research, 2006
- Evolutionary Optimization in Uncertain Environments—A SurveyIEEE Transactions on Evolutionary Computation, 2005
- A review of scheduling research involving setup considerationsOmega, 1999