Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-27T08:36:54.745Z Has data issue: false hasContentIssue false
  • English
  • Français

A STOCHASTIC BATCHING AND SCHEDULING PROBLEM

Published online by Cambridge University Press:  11 January 2002

Ger Koole  and
Rhonda Righter
Ger Koole
Affiliation:
Division of Mathematics and Computer Science, Vrije Universiteit, Amsterdam, The Netherlands E-mail: [email protected]
Rhonda Righter
Affiliation:
Department of Operations and Management Information Systems, Santa Clara University, Santa Clara, CA 95053 E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a batch scheduling problem in which the processing time of a batch of jobs equals the maximum of the processing times of all jobs in the batch. This is the case, for example, for burn-in operations in semiconductor manufacturing and other testing operations. Processing times are assumed to be random, and we consider minimizing the makespan and the flow time. The problem is much more difficult than the corresponding deterministic problem, and the optimal policy may have many counterintuitive properties. We prove various structural properties of the optimal policy and use these to develop a polynomial-time algorithm to compute the optimal policy.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 15 , Issue 4 , October 2001 , pp. 465 - 479
Copyright
© 2001 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)