AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (2.4 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

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

Department of Automation, Tsinghua University, Beijing 100084, China
Show Author Information

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

distributed hybrid flow shopmultiprocessor tasksenergy-aware schedulingmulti-objective optimizationdecompositiondynamic adjustment strategy

References

[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.
Google Scholar
[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.
Google Scholar
[3]
L. Hidri, Note on the hybrid flowshop scheduling problem with multiprocessor tasks, Int. J. Prod. Econ., vol. 182, pp. 531–534, 2016.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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., .
Crossref Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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, .
Crossref Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
Tsinghua Science and Technology
Volume 26 Issue 5,
October 2021
Pages 646-663
DOI: 10.26599/TST.2021.9010007
Cite this article:
Jiang E, Wang L, Wang J. Decomposition-Based Multi-Objective Optimization for Energy-Aware Distributed Hybrid Flow Shop Scheduling with Multiprocessor Tasks. Tsinghua Science and Technology, 2021, 26(5): 646-663. https://doi.org/10.26599/TST.2021.9010007

1073

Views

86

Downloads

84

Crossref

74

Web of Science

85

Scopus

4

CSCD

Altmetrics
Received: 28 December 2020
Accepted: 26 January 2021
Published: 20 April 2021
© The author(s) 2021

© 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