在傳統的排程研究中，製造者只考慮工件在生產階段的處理順序。然而，隨著競爭環境的變遷，以往的企業個體競爭方式逐漸轉變為供應鏈體系間的整體對抗型態。供應鏈中各成員間的協調與整合遂成為企業獲取競爭優勢的要件之一。本研究旨在探討在雙機流程式工廠環境下的整合性生產排程問題，即每項產品在加工完成後（生產階段）皆須送達顧客（配送階段）。我們討論兩種不同的目標準則：總完工時間及最大完工時間。在總完工時間極小化的問題中，我們證明此排程問題，不論在工件大小相同（且等於車子容量）或是允許不同的假設下，其時間複雜度均屬於指數複雜度（NP-hard）。對於最大完工時間極小化的問題，我們亦證明其時間複雜度屬於指數複雜度，並提出最佳排程的重要性質，據以發展啟發式演算法。此外，針對所發展的啟發式演算法完成其最差績效效果（worst-case performance）的分析。

In a rapid changing environment, the way of competition among enterprises has a tendency towards competing between supply chain systems instead of competing between individual companies. Traditional scheduling models which only address the sequence of jobs to be processed at the production stage under some criteria are no longer suitable and should be extended to cope with the distribution stage after production. Emphasizing on the coordination and the integration among various members of a supply chain has become one of the vital strategies for the modern manufacturers to gain competitive advantages.
This research focuses mainly on a class of two-machine flowshop scheduling problems with type-2 transportation, in which jobs need to be delivered to customers by vehicles after the completion of their respective production. Specifically, we consider two performance measures: the sum of job completion times and the makespan. For the sum of job completion times objective, we prove that this class of problems is strongly NP-hard whether the job sizes are assumed to be equal, in this situation the capacity of a vehicle is limited to just one job, or not. For the makespan objective, we only address the problem with different job sizes. We provide a proof of NP-hardness, develop a heuristic by incorporating properties inherited in the optimal schedule, and establish an upper bound on the worst-case performance ratio for the proposed heuristic method.

1. Ahmadi, J.H., Ahmadi, R.H., Dasu S., Tang C.S., Batching and scheduling jobs on batch and discrete processors, Operations Research 39 (1992) 750-763.
2. Chang, Y.C., Lee, Y.L., Machine scheduling with job delivery coordination, European Journal of Operational Research 158 (2004) 470-487.
3. Cheng, T.C.E., Gordon, B.S., Kovalyov, M.Y., Single machine scheduling with batch deliveries, European Journal of Operational Research 94 (1996) 277-283.
4. Conway, R.W., Maxwell, W.L., Miller, L.W., Theory of Scheduling. Addision-Wesley, Reading, Massachusetts, 1967.
5. Garey, M.R., Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.
6. Garey, M.R., Johnson, D.S., Sethi, R., The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research 1 (1976) 117-129.
7. Ganesharajah, T., Hall, N.G., Sriskandarajah, C., Design and operational issues in AGV-served manufacturing systems, Annals of Operations Research 76 (1998) 109-154.
8. Germmill, D.D., Stevens, J.W., Scheduling a two-machine flowshop with travel times to minimize maximum lateness, International Journal of Production Research 35 (1997) 1-15.
9. Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5 (1979) 287-326.
10. Hall, L.A., Shmoys, B., Jackson’s rule for single-machine scheduling: Making a good heuristic better, Mathematics of Operations Research 17 (1992) 22-35.
11. Hall, N.G., Potts, C.N., Supply chain scheduling: Batching and delivery, Operations Research 51 (2003) 566-584.
12. Hoogeveen, J.A., Kawaguchi, T., Minimizing total completion time in a two-machine flowshop: analysis of special cases, Mathematics of Operations Research 24 (1999) 887-910.
13. Ignall, E., Schrage, L., Application of the branch and bound technique to some flowshop scheduling problems, Operations Research 13 (1965) 400-412.
14. Johnson, S.M., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quartly 1 (1954) 61-68.
15. Kise H., On an automated two-machine flowshop scheduling problem with infinite buffer, Journal of the Operations Research Society of Japan 34 (1991) 354-361.
16. Lee, C.Y., Chen, Z.L. Machine scheduling with transportation considerations, Journal of Scheduling 4 (2001) 3-24.
17. Li, C.L., Vairaktarakis G., Lee C.Y., Machine scheduling with deliveries to multiple customer locations, European Journal of Operational Research 164 (2005) 39-51.
18. Maggu, P.L., Das, G., On 2 × n sequencing problem with transportation times of job, Pure and Applied Mathematika Science 12 (1980) 1-6.
19. Maggu P.L., Das G., Kumar R., On equivalent job-for-job block in 2 × n sequencing problem with transportation times, Journal of the Operations Research Society of Japan 24 (1981) 136-146.
20. Panwalkar, S.S., Scheduling of a two-machine flowshop with travel time between machines, Journal of the Operational Research Society 42 (1991) 609-613.
21. Pinedo M., Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, Englewoods Cliffs, NJ, 1995.
22. Potts, C.N., Analysis of a heuristic for one machine sequencing with release dates and delivery times, Operations Research 28 (1980) 1436-1441.
23. Potts, C.N., Kovalyov, M.Y., Scheduling with batching: A review, European Journal of Operational Research 120 (2000) 228-249.
24. Potts, C.N., Van Wassenhove, L.N., Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity, Journal of the Operational Research Society 43 (1992) 395-406.
25. Rajendran, C., Ziegler, H., An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs, European Journal of Operational Research 103 (1997) 129-138.
26. Simchi-Levi, D., New worst case results for the bin-packing problem, Naval Research Logistics 41 (1994) 579-585.
27. Soukhal, A., Oulamara, A., Martineau P., Complexity of flow shop scheduling problems with transportation constraints, European Journal of Operational Research 161 (2005) 32-41.
28. Stern, H.I., Vitner, G., Scheduling parts in a combined production -transportation work cell, Journal of the Operational Research Society 41 (1990) 625-632.
29. Webster, S., Baker, K.R., Scheduling groups of jobs on a single machine, Operations Research 43 (1995) 692-703.
30. Woeginger, G.J., Heuristics for parallel machine scheduling with delivery times, Acta Informatica 31 (1994) 503-512.