Keywords Automated guided vehicle · Lot streaming · Scheduling · Sequencing · Transfer batches
1 Introduction
Most classical shop scheduling models disregard the fact that products are often produced in lots, each lot (process batch) consisting of identical parts (items) to be produced. The size of a job lot (i.e., the number of items it consists of) typically ranges from a few items to several hundred. In any case, job lots are assumed to be indivisible single entities, although an entire job lot consists of many identical items. That is, partial transfer of completed items in a lot between machines on the processing routing of the job lot is impossible. But it is quite unreasonable to wait for the
2 Problem description
and Alfredson [6] examined two- and three-machine flowshops assuming there is no limit on the number of transfer batches so that it is optimal to use unit sized transfer batches. They showed that the two-machine problem with unit sized transfer batches is easily solved by a slight modification of Johnson’s well known algorithm, and also proved that pre-emption of job lots is not necessary in the optimal solution. That is, a job is split into unit sized transfer batches that are processed consecutively (not intermingled with the transfer batches of other job lots). Cetinkaya and Kayaligil [7] and Baker [8] extended this study to obtain a unified solution procedure, which handles separable and inseparable setups, respectively. Cetinkaya [9] and Vickson [10] independently showed that the scheduling problem with either equal or unequal transfer batches decomposes into an easily identifiable sequence of single job problems, even with setup times and transfer times. Sriskandarajah and Wagneur [11] studied the lot streaming and scheduling multiple products in two-machine, no-wait flowshops. Kim et al. [12] proposed a scheduling rule for a two-stage flowshop with identical parallel machines at each stage. On the other hand, studies on job lot scheduling with transfer batches for different shop structures are very limited. Examples of these studies include Dauzere-Peres and Lasserre [13] and Sen and Benli [14], which examine the job shops and open shops, respectively.
On the other hand, flowshop scheduling problems with transfer batches have been examined by various researchers. Vickson
179
Fig. 1. Processing a without transfer batches and b with transfer batches
There are many ways to split a lot: transfer batches may be equal or unequal, with the number of splits ranging from one to the number of units in the job lot. For instance, consider a job lot consisting of 100 identical items to be processed in a three-stage manufacturing environment in which the flow of its operations is unidirectional from stage 1 through stage 3. Assume that the unit processing time at stages 1, 2, and 3 are 1, 3, 2 min, respectively. If we do not allow transfer batches, the throughput time is (100)(1+3+2) = 600 min (see Fig. 1a). However, if we create two equal sized transfer batches through all stages, the throughput time decreases to 450 min, a reduction of 25% (see Fig. 1b). It is clear that the throughput time decreases as the number of transfer batches increases.
entire lot to finish its processing on the current machine, while downstream machines may be idle. It should be obvious that processing the entire lot as a single object can lead to large workin-process inventories between the machines, and to an increase in the maximum completion time (makespan), which is the total elapsed time to complete the processing of all job lots. However, the splitting of an entire lot into transfer batches to be moved to downstream machines permits the overlapping of different operations on the same product while work proceeds, to complete the lot on the upstream machine.
F.C. Çetinkaya (u) Department of Industrial Engineering, Eastern Mediterranean University, Gazimagusa-T.R.N.C., Mersin Turkey E-mail: ferda.cetinkaya@.tr Tel.: +90-392-6301052 Fax: +90-392-3654029
Int J Adv Manuf Technol (2006) 29: 178–183 DOI 10.1007/s00170-004-2493-9
ORIGINAL ARTICLE
Ferda C. C¸ etinkaya
Unit sized transfer batch scheduling in an automated two-machine flow-line cell with one transport agent
Flowshop problems have been studied extensively and reported in the literature without explicitly considering transfer batches. Johnson [1], in his pioneering work, proposed a polynomial time algorithm for determining the optimal makespan when several jobs are processed on a two-machine (two-stage) flowshop with unlimited buffer. With three or more machines, the problem has been proven to be NP-hard (Garey et al. [2]). Besides the extension of this problem to the m-stage flowshop problem, optimal solutions to some variations of the basic two-stage problem have been suggested. Mitten [3] considered arbitrary time lags, and optimal scheduling with setup times separated from processing was developed by Yoshida and Hitomi [4]. Separation of the setup, processing and removal times for each job on each machine was considereceived: 26 July 2004 / Accepted: 22 November 2004 / Published online: 16 November 2005 © Springer-Verlag London Limited 2005