Multi-objective ACO algorithms to minimise the makespan and the total rejection cost on BPMs with arbitrary job weights

ABSTRACT

In this paper, we investigate the batch-scheduling problem with rejection on parallel machines with non-identical job sizes and arbitrary job-rejected weights. If a job is rejected, the corresponding penalty has to be paid. Our objective is to minimise the makespan of the processed jobs and the total rejection cost of the rejected jobs. Based on the selected multi-objective optimisation approaches, two problems, P1 and P2, are considered. In P1, the two objectives are linearly combined into one single objective. In P2, the two objectives are simultaneously minimised and the Pareto non-dominated solution set is to be found. Based on the ant colony optimisation (ACO), two algorithms, called LACO and PACO, are proposed to address the two problems, respectively. Two different objective-oriented pheromone matrices and heuristic information are designed. Additionally, a local optimisation algorithm is adopted to improve the solution quality. Finally, simulated experiments are conducted, and the comparative results verify the effectiveness and efficiency of the proposed algorithms, especially on large-scale instances.

KEYWORDS:

• Multi-objective optimisation
• ant colony optimisation
• batch-processing machines
• makespan
• rejection cost

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The work is supported by the National Natural Science Foundation [grant number 71601001], [grant number 71671168]; the Humanity and Social Science Youth Foundation of Ministry of Education of China [grant number 15YJC630041]; the Natural Science Foundation of Anhui Province [grant number 1608085MG154]; the Natural Science Foundation of Anhui Provincial Education Department [grant number KJ2015A062].

Notes on contributors

Zhao-hong Jia

Zhao-hong Jia is an associate professor at Anhui University. She received her M.S. degree in Computer Science in 2003 from Anhui University and her Ph.D. degree in Management Science and Technology in 2008 from University of Science and Technology of China, respectively. Her research interests include intelligent computation and its applications, scheduling and operations management.

Ming-li Pei

Ming-li Pei is pursuing her Master degree in Computer Science at Anhui University. Her research interests include intelligent optimization, and evolutionary computation.

Joseph Y.-T. Leung

Joseph Y.-T. Leung received his B.A. in Mathematics in 1972 from Southern Illinois University and his Ph.D. in Computer Science in 1977 from the Pennsylvania State University. Since graduation, he has been on the faculty of Virginia Tech, Northwestern University, University of Texas at Dallas, University of Nebraska and New Jersey Institute of Technology. Currently, he is a distinguished professor of Computer Science in New Jersey Institute of Technology. His research interests include scheduling theory, computational complexity, approximation algorithms and meta-heuristics.