Single machine batch scheduling with jointly compressible setup and processing times

Chi To Ng, Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

26 Citations (Scopus)

Abstract

A single machine batch scheduling problem is addressed. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time common for all batches. Two external resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource and the job processing times are jointly compressible by another resource, i.e., the amount of resource consumption for setup time compression is the same for all setups and the amount of resource consumption for job processing time compression is the same for all jobs. Polynomial time algorithms are presented to find an optimal batch sequence and optimal amounts of resource consumption such that either total job completion time is minimized, subject to an upper bound on total weighted resource consumption, or total weighted resource consumption is minimized, subject to an upper bound on total job completion time. The algorithms are based on results from linear programming and from batch scheduling with fixed setup and processing times.
Original languageEnglish
Pages (from-to)211-219
Number of pages9
JournalEuropean Journal of Operational Research
Volume153
Issue number1
DOIs
Publication statusPublished - 16 Feb 2004

Keywords

  • Batching
  • Compressible setup and processing times
  • Scheduling
  • Single machine

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this