An Efficient Multiobjective Backtracking Search Algorithm for Single Machine Scheduling with Controllable Processing Times

Chao Lu, Liang Gao, Xinyu Li, Qi Wang, Wei Liao and Qingyao Zhao

Mathematical Problems in Engineering, 2017, vol. 2017, 1-24

Abstract:

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.

Date: 2017
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2017/8696985.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2017/8696985.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:8696985

DOI: 10.1155/2017/8696985

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().