Journal Home > Volume 26 , Issue 5

This paper addresses the Energy-Aware Distributed Hybrid Flow Shop Scheduling Problem with Multiprocessor Tasks (EADHFSPMT) by considering two objectives simultaneously, i.e., makespan and total energy consumption. It consists of three sub-problems, i.e., job assignment between factories, job sequence in each factory, and machine allocation for each job. We present a mixed inter linear programming model and propose a Novel Multi-Objective Evolutionary Algorithm based on Decomposition (NMOEA/D). We specially design a decoding scheme according to the characteristics of the EADHFSPMT. To initialize a population with certain diversity, four different rules are utilized. Moreover, a cooperative search is designed to produce new solutions based on different types of relationship between any solution and its neighbors. To enhance the quality of solutions, two local intensification operators are implemented according to the problem characteristics. In addition, a dynamic adjustment strategy for weight vectors is designed to balance the diversity and convergence, which can adaptively modify weight vectors according to the distribution of the non-dominated front. Extensive computational experiments are carried out by using a number of benchmark instances, which demonstrate the effectiveness of the above special designs. The statistical comparisons to the existing algorithms also verify the superior performances of the NMOEA/D.


menu
Abstract
Full text
Outline
About this article

Decomposition-Based Multi-Objective Optimization for Energy-Aware Distributed Hybrid Flow Shop Scheduling with Multiprocessor Tasks

Show Author's information Enda JiangLing Wang( )Jingjing Wang
Department of Automation, Tsinghua University, Beijing 100084, China

Abstract

This paper addresses the Energy-Aware Distributed Hybrid Flow Shop Scheduling Problem with Multiprocessor Tasks (EADHFSPMT) by considering two objectives simultaneously, i.e., makespan and total energy consumption. It consists of three sub-problems, i.e., job assignment between factories, job sequence in each factory, and machine allocation for each job. We present a mixed inter linear programming model and propose a Novel Multi-Objective Evolutionary Algorithm based on Decomposition (NMOEA/D). We specially design a decoding scheme according to the characteristics of the EADHFSPMT. To initialize a population with certain diversity, four different rules are utilized. Moreover, a cooperative search is designed to produce new solutions based on different types of relationship between any solution and its neighbors. To enhance the quality of solutions, two local intensification operators are implemented according to the problem characteristics. In addition, a dynamic adjustment strategy for weight vectors is designed to balance the diversity and convergence, which can adaptively modify weight vectors according to the distribution of the non-dominated front. Extensive computational experiments are carried out by using a number of benchmark instances, which demonstrate the effectiveness of the above special designs. The statistical comparisons to the existing algorithms also verify the superior performances of the NMOEA/D.

Keywords: multi-objective optimization, decomposition, distributed hybrid flow shop, multiprocessor tasks, energy-aware scheduling, dynamic adjustment strategy

References(32)

[1]
K. C. Ying and S. W. Lin, Minimizing makespan for the distributed hybrid flowshop scheduling problem with multiprocessor tasks, Expert Syst. Appl., vol. 92, pp. 132–141, 2018.
[2]
L. Hidri and A. Gharbi, New efficient lower bound for the hybrid flow shop scheduling problem with multiprocessor tasks, IEEE Access, vol. 5, pp. 6121–6133, 2017.
[3]
L. Hidri, Note on the hybrid flowshop scheduling problem with multiprocessor tasks, Int. J. Prod. Econ., vol. 182, pp. 531–534, 2016.
[4]
M. Kurdi, Ant colony system with a novel Non-DaemonActions procedure for multiprocessor task scheduling in multistage hybrid flow shop, Swarm Evol. Comput., vol. 44, pp. 987–1002, 2019.
[5]
H. R. Gholami, E. Mehdizadeh, and B. Naderi, Mathematical models and an elephant herding optimization for multiprocessor-task flexible flow shop scheduling problems in the manufacturing resource planning (MRPII) system, Sci. Iran., vol. 27, no. 3, pp. 1562–1571, 2020.
[6]
H. Gholami and M. T. Rezvan, A memetic algorithm for multistage hybrid flow shop scheduling problem with multiprocessor tasks to minimize makespan, Int. J. Ind. Eng. Manage. Sci., vol. 7, no. 1, pp. 181–200, 2020.
[7]
R. Ruiz, Q. K. Pan, and B. Naderi, Iterated greedy methods for the distributed permutation flowshop scheduling problem, Omega, vol. 83, pp. 213–222, 2019.
[8]
Q. K. Pan, L. Gao, L. Wang, J. Liang, and X. Y. Li, Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem, Expert Syst. Appl., vol. 124, pp. 309–324, 2019.
[9]
Z. Shao, W. Shao, and D. Pi, Effective heuristics and metaheuristics for the distributed fuzzy blocking flow-shop scheduling problem, Swarm Evol. Comput., vol. 59, p. 100747, 2020.
[10]
J. J. Wang and L. Wang, A bi-population cooperative memetic algorithm for distributed hybrid flow-shop scheduling, IEEE Trans. Emerg. Top. Comput. Intell., .
[11]
I. Chaouch, O. B. Driss, and K. Ghedira, A modified ant colony optimization algorithm for the distributed job shop scheduling problem, Procedia Comput. Sci., vol. 112, pp. 296–305, 2017.
[12]
I. Chaouch, O. B. Driss, and K. Ghedira, A novel dynamic assignment rule for the distributed job shop scheduling problem using a hybrid ant-based algorithm, Appl. Intell., vol. 49, no. 5, pp. 1903–1924, 2019.
[13]
C. Y. Hsu, B. R. Kao, and K. R. Lai, Agent-based fuzzy constraint-directed negotiation mechanism for distributed job shop scheduling, Eng. Appl. Artif. Intel., vol. 53, pp. 140–154, 2016.
[14]
L. Meng, C. Zhang, Y. Ren, B. Zhang, and C. Lv, Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem, Comput. Ind. Eng., vol. 142, p. 106347, 2020.
[15]
J. Cai, R. Zhou, and D. Lei, Dynamic shuffled frog-leaping algorithm for distributed hybrid flow shop scheduling with multiprocessor tasks, Eng. Appl. Artif. Intel., vol. 90, p. 103540, 2020.
[16]
X. Wu and A. Che, Energy-efficient no-wait permutation flow shop scheduling by adaptive multi-objective variable neighborhood search, Omega, vol. 94, p. 102117, 2020.
[17]
Z. Liu, J. Yan, Q. Cheng, C. Yang, S. Sun, and D. Xue, The mixed production mode considering continuous and intermittent processing for an energy-efficient hybrid flow shop scheduling, J. Clean. Prod., vol. 246, p. 119071, 2020.
[18]
J. J. Wang and L. Wang, A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop, IEEE Trans. Syst., Man, Cybern.: Syst., vol. 50, no. 5, pp. 1805–1819, 2020.
[19]
Y. Li, W. Huang, R. Wu, and K. Guo, An improved artificial bee colony algorithm for solving multi-objective low-carbon flexible job shop scheduling problem, Appl. Soft Comput., vol. 95, p. 106544, 2020.
[20]
E. D. Jiang and L. Wang, Multi-objective optimization based on decomposition for flexible job shop scheduling under time-of-use electricity prices, Knowl.-Based Syst., vol. 204, p. 106177, 2020.
[21]
E. D. Jiang, L. Wang, and Z. Peng, Solving energy-efficient distributed job shop scheduling via multi-objective evolutionary algorithm with decomposition, Swarm Evol. Comput., vol. 58, p. 100745, 2020.
[22]
Z. X. Pan, D. Lei, and L. Wang, A knowledge-based two-population optimization algorithm for distributed energy-efficient parallel machines scheduling, IEEE Trans Cybern, .
[23]
K. Gao, Y. Huang, A. Sadollah, and L. Wang, A review of energy-efficient scheduling in intelligent production systems, Complex Intell. Syst., vol. 6, pp. 237–249, 2020.
[24]
H. Zhang, J. Xie, J. Ge, J. Shi, and Z. Zhang, Hybrid particle swarm optimization algorithm based on entropy theory for solving DAR scheduling problem, Tsinghua Sci. Technol., vol. 24, no. 3, pp. 282–290, 2019.
[25]
L. Zhang, N. R. Alharbe, G. Luo, Z. Yao, and Y. Li, A hybrid forecasting framework based on support vector regression with a modified genetic algorithm and a random forest for traffic flow prediction, Tsinghua Sci. Technol., vol. 23, no. 4, pp. 479–492, 2018.
[26]
Y. Zhang, G. Cui, Y. Wang, X. Guo, and S. Zhao, An optimization algorithm for service composition based on an improved FOA, Tsinghua Sci. Technol., vol. 20, no. 1, pp. 90–99, 2015.
[27]
Q. Zhang and H. Li, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Trans Evol. Comput., vol. 11, no. 6, pp. 712–731, 2007.
[28]
E. D. Jiang and L. Wang, An improved multi-objective evolutionary algorithm based on decomposition for energy-efficient permutation flow shop scheduling problem with sequence-dependent setup time, Int. J. Prod. Res., vol. 57, no. 6, pp. 1756–1771, 2019.
[29]
F. Zhao, Z. Chen, J. Wang, and C. Zhang, An improved MOEA/D for multiobjective job shop scheduling problem. Int. J. Comput. Integ. M., vol. 30, no. 6, pp. 616–640, 2017.
[30]
A. Trivedi, D. Srinivasan, K. Sanyal, and A. Ghosh, A survey of multiobjective evolutionary algorithms based on decomposition, IEEE Trans Evol. Comput., vol. 21, no. 3, pp. 440–462, 2016.
[31]
R. Zhang and R. Chiong, Solving the energy-efficient job shop scheduling problem: A multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption, J. Clean. Prod., vol. 112, pp. 3361–3375, 2016.
[32]
G. Lebbar, I. El Abbassi, A. El Barkany, A. Jabri, and M. Darcherif, Solving the multi objective flow shop scheduling problems using an improved NSGA-II, Int. J. Oper. Quant. M., vol. 24, no. 3, pp. 211–230, 2018.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 28 December 2020
Accepted: 26 January 2021
Published: 20 April 2021
Issue date: October 2021

Copyright

© The author(s) 2021

Acknowledgements

This research was supported by the National Natural Science Fund for Distinguished Young Scholars of China (No. 61525304) and the National Natural Science Foundation of China (No. 61873328).

Rights and permissions

© The author(s) 2021. The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return