Skip to main content
SpringerLink
Log in

The equal allocation policy in open shop batch scheduling

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

We study the optimality of the very practical policy of equal allocation of jobs to batches in batch scheduling problems on an m-machine open shop. The objective is minimum makespan. We assume unit processing time jobs, machine-dependent setup times and batch availability. We show that equal allocation is optimal for a two-machine and a three-machine open shop. Although, this policy is not necessarily optimal for larger size open shops, it is shown numerically to produce very close-to-optimal schedules.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5

Similar content being viewed by others

References

  • Allahverdi A, Ng CT, Cheng TCE and Kovalyov MY (2008). A survey of scheduling problems with setup times or costs. Eur J Opl Res 187: 985–1032.

    Article  Google Scholar 

  • Averbakh I, Berman O and Chernykh I (2005). A 6/5 approximation algorithm for the two machine routing open-shop problem on a two-node network. Eur J Opl Res 166: 3–24.

    Article  Google Scholar 

  • Blazewicz J and Kovalyov MY (2002). The complexity of two group scheduling problems. J Sched 5: 477–485.

    Article  Google Scholar 

  • Bukchin J, Tzur M and Jaffe M (2002). Lot splitting to minimize average flow-time in a two-machine flow-shop. IIE Trans 34: 953–970.

    Google Scholar 

  • Chen J and Steiner G (1996). Lot streaming with detached setups in three-machine flow shops. Eur J Opl Res 96: 591–611.

    Article  Google Scholar 

  • Chen J and Steiner G (1998). Approximation methods for discrete lot streaming in flow shops. Opns Res Lett 21: 139–145.

    Article  Google Scholar 

  • Glass CA, Shafransky YM and Strusevich VA (2000). Scheduling for parallel dedicated machines with single server. Nav Res Log 47: 304.

    Article  Google Scholar 

  • Glass CA, Potts CN and Strusevich VA (2001). Scheduling batches with sequential job processing for two-machine flow and open-shops. INFORMS J Comput 13: 120–137.

    Article  Google Scholar 

  • Kleinau U (1993). Two-machine shop scheduling problems with batch processing. Math Comput Model 17: 55–66.

    Article  Google Scholar 

  • Mosheiov G and Oron D (2008). Open shop batch scheduling with identical jobs. Eur J Opl Res 187: 1282–1292.

    Article  Google Scholar 

  • Potts CN and Kovalyov MY (2000). Scheduling with batching: A review. Eur J Opl Res 120: 228–249.

    Article  Google Scholar 

  • Strusevich VA (2000). Group technology approach to the open shop scheduling problem with batch setup times. Opns Res Lett 26: 181–192.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Hebrew University, Jerusalem, Israel

    B Mor & G Mosheiov

  2. The University of Sydney, Sydney, Australia

    D Oron

Authors
  1. B Mor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. G Mosheiov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. D Oron
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mor, B., Mosheiov, G. & Oron, D. The equal allocation policy in open shop batch scheduling. J Oper Res Soc 63, 646–652 (2012). https://doi.org/10.1057/jors.2011.64

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2011.64

Keywords

Search

Navigation