TY - JOUR
T1 - Heuristic Scheduling of Batch Production Processes Based on Petri Nets and Iterated Greedy Algorithms
AU - Zhao, Ziyan
AU - Liu, Shixin
AU - Zhou, Mengchu
AU - You, Dan
AU - Guo, Xiwang
N1 - Funding Information:
This work was supported in part by the China Scholarship Council, in part by the National Key Research and Development Program of China under Grant 2017YFB0306400, and in part by the National Natural Science Foundation of China under Grant 62073069.
Publisher Copyright:
© 2004-2012 IEEE.
PY - 2022/1/1
Y1 - 2022/1/1
N2 - Wire rod and bar rolling is an important batch production process in steel production systems. A scheduling problem originated from this process is studied in this work by considering the constraints on sequence-dependent family setup time and release time. For each serial batch to be scheduled, it contains several jobs and the number of late jobs within it varies with its start time. First, we model a rolling process using a Petri net (PN), where a so-called rolling transition describes a rolling operation of a batch. The objective of the concerned problem is to determine a firing sequence of all rolling transitions such that the total number of late jobs is minimal. Next, a mixed-integer linear program is formulated based on the PN model. Due to the NP-hardness of the concerned problem, iterated greedy algorithm (IGA)-based methods by using different neighborhood structures and integrating a variable neighborhood descent method are developed to obtain its near-optimal solutions. To test the accuracy, speed, and stability of the proposed algorithms, we compare their solutions of different-size instances with those of CPLEX (a commercial software) and four heuristic peers. The results indicate that the proposed algorithms outperform their peers and have great potential to be applied to industrial production process scheduling. Note to Practitioners - This work deals with a scheduling problem of a batch production process, i.e., wire rod and bar rolling, which is modeled by a Petri net (PN). Due to the NP-hardness of the concerned problem, four iterated greedy algorithm-based methods are developed to solve it. The proposed methods are validated and tested by comparing their solutions with those of four heuristic peers and the exact ones (when available via CPLEX). Extensive experimental results show that they can fast solve one-week-scale instances with better performance than their peers', thereby proving the readiness to put them in industrial use. When solving a one-month-scale instance, the proposed methods show much better performance than others.
AB - Wire rod and bar rolling is an important batch production process in steel production systems. A scheduling problem originated from this process is studied in this work by considering the constraints on sequence-dependent family setup time and release time. For each serial batch to be scheduled, it contains several jobs and the number of late jobs within it varies with its start time. First, we model a rolling process using a Petri net (PN), where a so-called rolling transition describes a rolling operation of a batch. The objective of the concerned problem is to determine a firing sequence of all rolling transitions such that the total number of late jobs is minimal. Next, a mixed-integer linear program is formulated based on the PN model. Due to the NP-hardness of the concerned problem, iterated greedy algorithm (IGA)-based methods by using different neighborhood structures and integrating a variable neighborhood descent method are developed to obtain its near-optimal solutions. To test the accuracy, speed, and stability of the proposed algorithms, we compare their solutions of different-size instances with those of CPLEX (a commercial software) and four heuristic peers. The results indicate that the proposed algorithms outperform their peers and have great potential to be applied to industrial production process scheduling. Note to Practitioners - This work deals with a scheduling problem of a batch production process, i.e., wire rod and bar rolling, which is modeled by a Petri net (PN). Due to the NP-hardness of the concerned problem, four iterated greedy algorithm-based methods are developed to solve it. The proposed methods are validated and tested by comparing their solutions with those of four heuristic peers and the exact ones (when available via CPLEX). Extensive experimental results show that they can fast solve one-week-scale instances with better performance than their peers', thereby proving the readiness to put them in industrial use. When solving a one-month-scale instance, the proposed methods show much better performance than others.
KW - Batch production process
KW - Petri net (PN)
KW - iterated greedy algorithm (IGA)
KW - variable neighborhood descent (VND)
UR - http://www.scopus.com/inward/record.url?scp=85096142728&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85096142728&partnerID=8YFLogxK
U2 - 10.1109/TASE.2020.3027532
DO - 10.1109/TASE.2020.3027532
M3 - Article
AN - SCOPUS:85096142728
SN - 1545-5955
VL - 19
SP - 251
EP - 261
JO - IEEE Transactions on Automation Science and Engineering
JF - IEEE Transactions on Automation Science and Engineering
IS - 1
ER -