Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-27T08:48:46.420Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimizing the Makespan and Flowtime in Two-Machine Stochastic Open Shops

Published online by Cambridge University Press:  27 July 2009

Tian-Shyug Lee  and
Georgia-Ann Klutke
Tian-Shyug Lee
Affiliation:
Department of Business Administration, College of Management, Fu-Jen Catholic University, Taipei, Taiwan, ROC
Georgia-Ann Klutke
Affiliation:
Department of Industrial Engineering, Texas A&M University, College Station, Texas 77841-3131
Get access Rights & Permissions [Opens in a new window]

Extract

In this paper, we present some new results on the makespan and flowtime in a two-parallel machine open shop. A set of n jobs is to be processed on two machines, the order of processing being immaterial. For the case where the machines are identical, and the jobs are nonoverlapping ordered, we show that the sequences that stochastically minimize the makespan are longest processing time first-shortest processing time first (LPT-SPT). Within this class of sequences, we show that the SPT sequence stochastically minimizes the flowtime.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 10 , Issue 4 , October 1996 , pp. 557 - 567
Copyright
Copyright © Cambridge University Press 1996

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.)

References

1.Dempster, M.A.H., Lenstra, J.K., & Rinnooy Kan, A.H.G. (1982). Deterministic and stochastic scheduling. Boston: D. Reidel.CrossRefGoogle Scholar
2.Dror, M. (1992). Openshop scheduling with machine dependent processing times. Discrete Applied Mathematics 39: 197–205.CrossRefGoogle Scholar
3.Foley, R.D. & Suresh, S. (1984). Stochastically minimizing the makespan in flow shops. Naval Research Logistics Quarterly 31: 551–558.CrossRefGoogle Scholar
4.Frostig, E. (1991). On the optimality of static policy in stochastic open shop. Operations Research Letters 10: 509–512.CrossRefGoogle Scholar
5.Gonzalez, T. & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery 23: 665–679.CrossRefGoogle Scholar
6.Johnson, S.M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1: 61–68.CrossRefGoogle Scholar
7.Kijima, M. (1989). Stochastic minimization of the makespan in flow shops with identical machines and buffers of arbitrary size. Operations Research 37: 924–928.Google Scholar
8.Ku, P.-S. & Niu, S.-C. (1986). On Johnson's two-machine flow shop with random processing times. Operations Research 34: 130–136.CrossRefGoogle Scholar
9.Lee, T.-S. (1993). Stochastic open shop scheduling. Ph.D. thesis. Graduate Program in Operations Research, Department of Mechanical Engineering, The University of Texas at Austin.Google Scholar
10.Pinedo, M. (1981). A note on two-machine job shops with exponential processing times. Naval Research Logistics Quarterly 28: 693–696.CrossRefGoogle Scholar
11.Pinedo, M. (1982). Minimizing the expected makespan in stochastic flow shops. Operations Research 30: 148–162.CrossRefGoogle Scholar
12.Pinedo, M. & Ross, S. (1982). Minimizing the expected makespan in stochastic open shops. Advances in Applied Probability 14: 898–911.CrossRefGoogle Scholar
13.Stoyan, D. (1983). Comparison methods for queues and other stochastic models. New York: Wiley.Google Scholar
14.Suresh, S. (1986). Stochastic flow shop scheduling. Ph.D. thesis, Department of Industrial Engineering and Operations Research, Virginia Polytechnic Institute and State University.Google Scholar