An Efficient Multiobjective Backtracking Search Algorithm for Single Machine Scheduling with Controllable Processing Times
Joint Authors
Li, Xinyu
Gao, Liang
Wang, Qi
Liao, Wei
Zhao, Qingyao
Lu, Chao
Source
Mathematical Problems in Engineering
Issue
Vol. 2017, Issue 2017 (31 Dec. 2017), pp.1-24, 24 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2017-03-14
Country of Publication
Egypt
No. of Pages
24
Main Subjects
Abstract EN
The scheduling problem with controllable processing times (CPT) is one of the most important research topics in the scheduling field due to its widespread application.
Because of the complexity of this problem, a majority of research mainly addressed single-objective small scale problems.
However, most practical problems are multiobjective and large scale issues.
Multiobjective metaheuristics are very efficient in solving such problems.
This paper studies a single machine scheduling problem with CPT for minimizing total tardiness and compression cost simultaneously.
We aim to develop a new multiobjective discrete backtracking search algorithm (MODBSA) to solve this problem.
To accommodate the characteristic of the problem, a solution representation is constructed by a permutation vector and an amount vector of compression processing times.
Furthermore, two major improvement strategies named adaptive selection scheme and total cost reduction strategy are developed.
The adaptive selection scheme is used to select a suitable population to enhance the search efficiency of MODBSA, and the total cost reduction strategy is developed to further improve the quality of solutions.
For the assessment of MODBSA, MODBSA is compared with other algorithms including NSGA-II, SPEA2, and PAES.
Experimental results demonstrate that the proposed MODBSA is a promising algorithm for such scheduling problem.
American Psychological Association (APA)
Lu, Chao& Gao, Liang& Li, Xinyu& Wang, Qi& Liao, Wei& Zhao, Qingyao. 2017. An Efficient Multiobjective Backtracking Search Algorithm for Single Machine Scheduling with Controllable Processing Times. Mathematical Problems in Engineering،Vol. 2017, no. 2017, pp.1-24.
https://search.emarefa.net/detail/BIM-1192475
Modern Language Association (MLA)
Lu, Chao…[et al.]. An Efficient Multiobjective Backtracking Search Algorithm for Single Machine Scheduling with Controllable Processing Times. Mathematical Problems in Engineering No. 2017 (2017), pp.1-24.
https://search.emarefa.net/detail/BIM-1192475
American Medical Association (AMA)
Lu, Chao& Gao, Liang& Li, Xinyu& Wang, Qi& Liao, Wei& Zhao, Qingyao. An Efficient Multiobjective Backtracking Search Algorithm for Single Machine Scheduling with Controllable Processing Times. Mathematical Problems in Engineering. 2017. Vol. 2017, no. 2017, pp.1-24.
https://search.emarefa.net/detail/BIM-1192475
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1192475