Heuristic Scheduling of Batch Production Processes Based on Petri Nets and Iterated Greedy Algorithms

Ziyan Zhao, Shixin Liu, Meng Chu Zhou, Dan You, Xiwang Guo

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
JournalIEEE Transactions on Automation Science and Engineering
DOIs
StateAccepted/In press - 2020

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Keywords

  • Batch production process
  • Greedy algorithms
  • iterated greedy algorithm (IGA)
  • Job shop scheduling
  • Petri net (PN)
  • Petri nets
  • Single machine scheduling
  • Task analysis
  • variable neighborhood descent (VND).

Fingerprint

Dive into the research topics of 'Heuristic Scheduling of Batch Production Processes Based on Petri Nets and Iterated Greedy Algorithms'. Together they form a unique fingerprint.

Cite this