TY - JOUR
T1 - Multi-objective ACO algorithms to minimise the makespan and the total rejection cost on BPMs with arbitrary job weights
AU - Jia, Zhao hong
AU - Pei, Ming li
AU - Leung, Joseph Y.T.
N1 - Funding Information:
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].
PY - 2017/12/10
Y1 - 2017/12/10
N2 - 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.
AB - 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.
KW - Multi-objective optimisation
KW - ant colony optimisation
KW - batch-processing machines
KW - makespan
KW - rejection cost
UR - http://www.scopus.com/inward/record.url?scp=85031491877&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85031491877&partnerID=8YFLogxK
U2 - 10.1080/00207721.2017.1387314
DO - 10.1080/00207721.2017.1387314
M3 - Article
AN - SCOPUS:85031491877
SN - 0020-7721
VL - 48
SP - 3542
EP - 3557
JO - International Journal of Systems Science
JF - International Journal of Systems Science
IS - 16
ER -