none

　This study considers a class of the two-stage scheduling problem in which the first stage is job production and the second stage is job delivery. The focus is on the study of the integration of production scheduling with delivery of finished products to customers. In our study, we considering a two-machine flow-shop problem in which the processing time are the same for each machine and the finished jobs are delivered to one or two customers’ area. We propose two heuristic algorithms which incorporate the first fit decreasing (FFD) algorithm to classify jobs into batches for these problems, respectively. The worst-case performances of these two heuristics are investigated and randomly generated problems are solved by the heuristics for numerical test.

　The upper bound of one customer area problem is less than 2 and that of two customer areas problem is less than . For the numerical test, the average performances of the two heuristics are not more than 1.7 of optimal solution.

References

1.Allaheverdi, A. (2000). "Minimizing mean flowtime in a two-machine flowshop
with sequence-independent setup times." Computers & Operations Research 27:
111-127.

2.Chang, Y.-C. and C.-Y. Lee (2004). "Machine scheduling with job delivery
coordination." European Journal of Operational Research 158: 470-487.

3.Coffman, J. E. G., M. R. Garey, and D. S. Johnson (1978). "An application of
bin-packing to multiprocessor scheduling." SIAM Journal on Computing 7: 1-17.

4.Du, J. and J. Y.-T. Leung (1993). "Minimizing mean flow time in two-machine
open shops and flow shops." Journal of Algorithms 14: 24-44.

5.Garey, M. R. and D. S. Johnson (1979). Computers and Intractability: A Guide
to the Theory of NP-Completeness, Freeman, San Francisco.

6.Gemmill, D. D. and J. W. Stevens (1997). "Scheduling a two-machine flowshop
with travel times to minimize maximum lateness." International Journal of
Production Research 35: 1-15.

7.Hall, L. A. and D. B. Shmoys (1992). "Jackson's rule for single-machine
scheduling: making a good heuristic better." Mathematics of Operations
Research 17: 22-35.

8.Ho, J. C. and Y. L. Chang (1995). "Minimizing the number of tardy jobs for m
parallel machines." European Journal of Operational Research 84: 343-355.

9.Hurink, J. and S. Knust (2001). "Makespan minimization for flow-shop
problems with transportation times and a single robot." Discrete Applied
Mathematics 112: 199-216.

10.Johnson, S. M. (1954). "Optimal two- and three-stage production schedules
with setup times included." Naval Research Logistics Quarterly 1: 61-68.

11.Kamburowski, J. (2000). "On three-machine flow shops with random job
processing times." European Journal of Operational Research 125: 440-449.

12.Kise, H. (1991). "On an automated two-machine flowshop scheduling problem
with infinite buffer." Journal of the Operations Research Society of Japan
34: 354-361.

13.Lee, C.-Y. and Z.-L. Chen (2001). "Machine scheduling with transportation
considerations." Journal of Scheduling 4: 3-24.

14.Li, W. and J. Cao (1995). "Stochastic scheduling on a single machine
subject to multiple breakdowns according to different probabilties."
Operations Research Letters 18: 81-91.

15.Liao, C.-J., D.-L. Shyur and C.-H Lin (2005). "Makespan minimization for
two parallel machines with an availability constraint." European Journal of
Operational Research 160: 445-456.

16.Liaw, C.-F. (1999). "A branch-and-bound algorithm for the single machine
earliness and tardiness scheduling problem." Computers & Operations
Research 26: 679-693.

17.Maggu, P. L. and G. Das (1980). "On 2 sequencing problem with
transportation tines of jobs." Pure and Applied Mathematika Science 12: 1-6.

18.Panwalkar, S. S. (1991). "Scheduling of a two-machine flowshop with travel
time between machines." Journal of Operational Research Society 42: 609-613.

19.Pranzo, M. (2004). "Batch scheduling in a two-machine flow shop with
limited buffer and sequence independent setup times and removal times."
European Journal of Operational Research 153: 581-592.

20.Simchi-Levi, D. (1994). "New worse-case result for the bin-packing
problem." Naval Research Logistics 41: 579-585.

21.Strusevich, V. A. and L. A. Hall (1997). "An open shop scheduling problem
with a non-bottleneck machine." Operations Research Letters 21: 11-18.

22.Sule, D. R. (1996). Industrial Scheduling, PWS-ITP, Boston.