Abstract
Batch scheduling problems deal with jobs to be processed in batches in many industrial production systems. They are hard to solve. This work proposes a novel bi-objective batch scheduling problem with the constraints of release time and sequence-dependent setup time. As an important characteristic of the concerned problem, the number of late jobs within a batch varies with its start time. A mixed-integer linear program is proposed to describe this problem. Two objectives, i.e., minimizing the total number of late jobs and setup time, are considered. Two memetic algorithms by integrating a non-dominated sorting genetic algorithm II (NSGA-II) and 2-opt local search are designed to solve the concerned problem. They adopt different crossover operators, i.e., partially mapped one and precedence preserved one. By comparing the results of the proposed algorithms with their peers on extensive experiments, we conclude that the proposed algorithms get much better Pareto fronts than their peers at the expense of more execution time. Yet, their speeds are fast enough to solve the problems with industrial scales and thus prove the readiness to put them in industrial use.
Original language | English (US) |
---|---|
Title of host publication | 2020 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2020 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 2119-2124 |
Number of pages | 6 |
Volume | 2020-October |
ISBN (Electronic) | 9781728185262 |
DOIs | |
State | Published - Oct 11 2020 |
Event | 2020 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2020 - Toronto, Canada Duration: Oct 11 2020 → Oct 14 2020 |
Conference
Conference | 2020 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2020 |
---|---|
Country/Territory | Canada |
City | Toronto |
Period | 10/11/20 → 10/14/20 |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Human-Computer Interaction
- Computer Science Applications
- Electrical and Electronic Engineering
Keywords
- Batch scheduling
- genetic algorithm
- intelligent optimization
- local search
- memetic algorithm
- sequence-dependent setup time