Stochastic cyclic flow lines: non-blocking, Markovian models
- PDF / 305,524 Bytes
- 12 Pages / 595 x 842 pts (A4) Page_size
- 15 Downloads / 193 Views
#1998 Operational Research Society Ltd. All rights reserved. 0160-5682/98 $12.00 http://www.stockton-press.co.uk/jor
Stochastic cyclic ¯ow lines: non-blocking, Markovian models T-E Lee and J-W Seo Korea Advanced Institute of Science and Technology, Korea In this paper we consider stochastic cyclic ¯ow lines where identical sets of jobs are repeatedly produced in the same loading and processing sequence. Each machine has an input buffer with enough capacity. Processing times are stochastic. We model the shop as a stochastic event graph, a class of Petri nets. We characterise the ergodicity condition and the cycle time. For the case where processing times are exponentially distributed, we present a way of computing queue length distributions. For two-machine cases, by the matrix geometric method, we compute the exact queue length distributions. For general cases, we present two methods for approximately decomposing the line model into twomachine submodels, one based on starvation propagation and the other based on transition enabling probability propagation. We experiment our approximate methods for various stochastic cyclic ¯ow lines and discuss performance characteristics as well as accuracy of the approximate methods. Finally, we discuss the effects of job processing sequences of stochastic cyclic ¯ow lines. Keywords: production; queueing; cyclic scheduling; decomposition
Introduction We consider a cyclic shop where identical sets of items are repeatedly produced on the same machine loading and the same processing sequence. The set is usually taken to be the smallest set that has the same proportion as the production requirement, called a minimal part set (MPS) (see Hitz1). Such a shop is called a cyclic (or periodic) shop and the scheduling method is called cyclic (or periodic) scheduling. As an example, when the production requirement is given as 500 units of part a, 300 units of part b and 200 units of part c, the MPS is fa; a; a; a; a; b; b; b; c; cg. We produce the MPS 100 times in the same processing order. Such a production method is effective when setup times are relatively small. The cyclic production method has been proposed for ¯exible manufacturing systems or ¯exible ¯ow lines (McCormick et al,2 Sethi et al,3 Ahmadi and Wurgaft,4 Lee and Posner5). Cyclic scheduling has several advantages over conventional production methods like batch production or random mix production. The advantages include simpler scheduling, predictive shop behaviour, smooth supply of parts to downstream assembly, less work-in-progress inventory, and higher machine utilisation (see Ahmadi and Wurgaft4, Lee and Posner5). Depending on the shop structure and the job characteristics, cyclic shops are classi®ed into cyclic ¯ow shops where each job
Correspondence: Dr T-E Lee, 373-1 Kusong-Dong, Yusong-Gu, Taejon 305-701 Korea.
visits the machines in the same order and cyclic job shops where each job can have a different machine visit sequence. There have been numerous studies on versions of cyclic scheduling, including Graves et al,6
Data Loading...
