Integrated scheduling on a batch machine to minimize production, inventory and distribution costs

Ba Yi Cheng, Joseph Y.T. Leung, Kai Li

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

We consider the problem of scheduling a set of jobs on a single batch-processing machine. Each job has a size and a processing time. The jobs are batched together and scheduled on the batch-processing machine, provided that the total size does not exceed the machine capacity. The processing time of the batch is the longest processing time among all the jobs in the batch. There is a single vehicle to deliver the final products to the customer. If the vehicle has not returned, completed batches will be put into the inventory. In this paper, we consider the problem of minimizing the production, delivery and inventory costs. We show that if the jobs have the same size, there is an O(nlog n)-time algorithm to find an optimal solution. If the jobs have the same processing time, there is a fast approximation algorithm with an absolute worst-case ratio less than 1.783 and an asymptotic worst-case ratio equal to 11/9. When the jobs have arbitrary sizes and arbitrary processing times, there is a fast approximation algorithm with absolute and asymptotic worst-case ratios less than or equal to 2, respectively.

Original languageEnglish (US)
Pages (from-to)104-112
Number of pages9
JournalEuropean Journal of Operational Research
Volume258
Issue number1
DOIs
StatePublished - Apr 1 2017

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Approximation algorithms
  • Batch-processing machines
  • Distribution
  • Inventory
  • Production

Fingerprint

Dive into the research topics of 'Integrated scheduling on a batch machine to minimize production, inventory and distribution costs'. Together they form a unique fingerprint.

Cite this