Batching and Scheduling Jobs on Batch and Discrete Processors

Javad H. Ahmadi, Reza H. Ahmadi, Sriram Dasu and Christopher S. Tang
Additional contact information
Javad H. Ahmadi: IBM Corporation, Austin, Texas
Reza H. Ahmadi: University of California, Los Angeles, California
Sriram Dasu: University of California, Los Angeles, California
Christopher S. Tang: University of California, Los Angeles, California

Operations Research, 1992, vol. 40, issue 4, 750-763

Abstract: We consider a situation in which the manufacturing system is equipped with batch and discrete processors. Each batch processor can process a batch (limited number) of jobs simultaneously. Once the process begins, no job can be released from the batch processor until the entire batch is processed. In this paper, we analyze a class of two-machine batching and scheduling problems in which the batch processor plays an important role. Specifically, we consider two performance measures: the makespan and the sum of job completion times. We analyze the complexity of this class of problems, present polynomial procedures for some problems, propose a heuristic, and establish an upper bound on the worst case performance ratio of the heuristic for the NP-complete problem. In addition, we extend our analysis to the case of multiple families and to the case of three-machine batching.

Keywords: manufacturing: automated systems; production/scheduling: algorithms and heuristics (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (31)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.4.750 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:4:p:750-763

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().