Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-01-14T04:38:38.313Z Has data issue: false hasContentIssue false
  • English
  • Français

Stochastic flowshop no-wait scheduling

Published online by Cambridge University Press:  14 July 2016

E. Frostig  and
I. Adiri
E. Frostig*
Affiliation:
Technion — Israel Institute of Technology
I. Adiri*
Affiliation:
Technion — Israel Institute of Technology
*
∗Postal address: Faculty of Industrial Engineering and Management, Technion City, Haifa 32000, Israel.
∗Postal address: Faculty of Industrial Engineering and Management, Technion City, Haifa 32000, Israel.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper deals with special cases of stochastic flowshop, no-wait, scheduling. n jobs have to be processed by m machines . The processing time of job Ji on machine Mj is an independent random variable Ti. It is possible to sequence the jobs so that , . At time 0 the realizations of the random variables Ti, (i are known. For m (m ≧ 2) machines it is proved that a special SEPT–LEPT sequence minimizes the expected schedule length; for two (m = 2) machines it is proved that the SEPT sequence minimizes the expected sum of completion times.

Keywords

STOCHASTIC SCHEDULING
Type
Short Communications
Information
Journal of Applied Probability , Volume 22 , Issue 1 , March 1985 , pp. 240 - 246
Copyright
Copyright © Applied Probability Trust 1985 

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] Gilmore, P. C. and Gomory, R. E. (1964) Sequencing a one-state variable machine: a solvable case of the travelling salesman problem. Operat. Res. 12, 655–679.Google Scholar
[2] Papadimitriou, C. H. and Kanellakis, P. C. (1980) Flowshop scheduling with limited temporary storage. J. ACM 27, 533–549.Google Scholar
[3] Pinedo, M. (1982) Minimizing the expected makespan in stochastic flowshops. Operat. Res. 30, 148–162.CrossRefGoogle Scholar
[4] Pinedo, M. and Schrage, L. (1981) Stochastic shop scheduling: survey. PDRC Report Series No. 81–12, Industrial Eng., Georgia Institute of Technology.Google Scholar
[5] Prabhu, N. U. (1980) Stochastic Storage Process: Queues, Insurance Risk, and Dams. Springer-Verlag, New York.Google Scholar
[6] Reddi, S. S. and Ramamoorthy, C. V. (1972) On the flowshop sequencing problem with no-wait in process. Operat. Res. Quart. 23, 323–331.Google Scholar
[7] Röck, H. (1982) Flowshop scheduling with no-wait in process on three machines. Technische Universität Berlin, Operations Research, Bericht Nr. 82–7.Google Scholar
[8] Röck, H. (1983) Some new results on no-wait flowshop scheduling. Technishe Universität Berlin, Operations Research, Bericht Nr. 83–09.Google Scholar
[9] Sahni, S. and Cho, Y. (1977) Complexity of scheduling shops with no-wait in process. Technical Report 77–20, Computer Science Department, University of Minnesota, Minneapolis.Google Scholar