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

Civil Engineering

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