Single machine batch scheduling with resource dependent setup and processing times

Edwin Tai Chiu Cheng, Adam Janiak, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

48 Citations (Scopus)


Jobs are processed by a single machine in batches. 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. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource, which may be different from that for the jobs. Polynomial time algorithms are presented to find an optimal batch sequence and resource values such that either the total weighted resource consumption is minimized, subject to meeting job deadlines, or the maximum job lateness is minimized, subject to an upper bound on the total weighted resource consumption. The algorithms are based on linear programming formulations of the corresponding problems.
Original languageEnglish
Pages (from-to)177-183
Number of pages7
JournalEuropean Journal of Operational Research
Issue number1
Publication statusPublished - 16 Nov 2001


  • Batching
  • Linear programming
  • Polynomial algorithm
  • Resource allocation
  • Scheduling

ASJC Scopus subject areas

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

Cite this