A New Bi-Objective Batch Scheduling Problem: NSGA-II-and-Local-Search-Based Memetic Algorithms

Zi Yan Zhao, Shi Xin Liu, Meng Chu Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publication2020 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2119-2124
Number of pages6
Volume2020-October
ISBN (Electronic)9781728185262
DOIs
StatePublished - Oct 11 2020
Event2020 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2020 - Toronto, Canada
Duration: Oct 11 2020Oct 14 2020

Conference

Conference2020 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2020
Country/TerritoryCanada
CityToronto
Period10/11/2010/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

Fingerprint

Dive into the research topics of 'A New Bi-Objective Batch Scheduling Problem: NSGA-II-and-Local-Search-Based Memetic Algorithms'. Together they form a unique fingerprint.

Cite this