在一個快速變遷的現代社會，企業競爭有轉向供應鏈整合的趨勢；過去，生產排程研究只定位在衡量生產階段各種指標，此已無法滿足實際情況，應擴展延伸至生產之後的運送階段；同時對於現今製造業而言，為獲取更大競爭利益，加強供應鏈間團隊整合與協調，已成為重要策略。本論文即在探討兩個以最大完工時間極小化為目標，考量工件運送情況下兩個相同平行機生產排程之指數複雜度（NP-hard）問題。
第一個問題，主要在考量每個工件尺寸大小不同，工件必須在兩個相同平行機中任一部機器完成加工，之後再輸送至單一消費者。這問題最早是由Chang 和 Lee（2004）所提出，Chang等學者提出最差/最佳解比值為2之法則。Zhong（2007）等學者進一步研究改善，提出最差/最佳解比值為5/3之法則。本研究提出一個新法則，除兩個特例其最差/最佳解比值為8/5外，其餘均為63/40。
第二個問題，本論文研究兩階段生產排程指數複雜度（NP-hard）問題，即工件必須在兩個相同平行機中任一部機器完成加工，之後再輸送至單一消費者，且其中一台機器存在ㄧ段因維修而無法運作之時間。這問題最早是由Wang 和 Cheng（2007）所提出，並研究提出最差/最佳解比值為5/3之法則。本研究提出一個新法則，其最差/最佳解比值為3/2。

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 paper studies two NP-hard problem of the two-stage scheduling in which jobs are processed by two identical parallel machines and delivered to a customer with the objective of minimizing the makespan
First, this study focuses mainly on a class of two identical parallel machines problem, in which jobs need to be delivered to single customer by a vehicle after their production stages and jobs size are different. The problem was first proposed by Chang and Lee（2004）. Chang et al. presented a polynomial time algorithm with a worst-case ratio of 2. Zhong et al. [53] presented an improvement algorithm for the problem and reduced the worst-case ratio to 5/3. The purpose of this paper is to propose a new algorithm which leads to a best possible solution with a worst-case ratio of 63/40, except for the two particular cases where CMH3/C*  8/5.
Second, this paper studies the NP-hard problem of the two-stage scheduling in which jobs are processed by two identical parallel machines and delivered to a customer. We consider one of machines that exists an unavailable interval due to preventive maintenance. The problem was first proposed by Wang and Cheng（2007） and they proposed an algorithm H2 with a worst-case ratio of 5/3. We propose a new algorithm which leads to a best possible solution with a worst-case ratio of 3/2.

[1]Chang, Y.C. and Lee, Y.L. (2004) Machine scheduling with job delivery coordination. European Journal of Operational Research, 158, 470-487.
[2]Chen, J.S. (2010) Integration of job scheduling with delivery vehicles routing. Information Technology Journal, 9(6), 1202-1206.
[3]Chen, Z.L. (2010) Integrated Production and Outbound Distribution Scheduling: Review and Extensions. Operations Research. 58, 130-148.
[4]Chen, Z.L. and Vairaktarakis, G.L. (1994) Integrated scheduling of production and distribution operations. Management Science, 51, 614-628.
[5]Cheng, T.C.E. and Gordon, V.S. (1994) Batch delivery scheduling on a single machine. Journal of the Operational Research Society, 45, 1211-1215.
[6]Cheng, T.C.E., Gordon, V.S. and Kovalyov, M.Y. (1996) Single machine scheduling with batch deliveries. European Journal of OperationalResearch, 94, 277-283.
[7]Cheng, T.C.E. and Kahlbacher, H.G. (1993) Scheduling with delivery and earliness penalties. Asia-Pacific Journal of Operational Research, 10, 145-152.
[8]Chung, D., Lee, K., Shin, K., and Park, J. (2005) A new approach to job shop scheduling problems with due date constraints considering operation subcontracts. International Journal of Production Economics, 98, 238–250
[9]Ganesharajah, T., Hall, N.G. and Sriskandarajah, C. (1998) Design and operational issues in AGV-served manufacturing systems. Annals of Operations Research, 76, 109-154.
[10]Gharbi, A. and Haouari, M. (2002) Minimizing makespan on parallel machines subject to release dates and delivery times. Journal of Scheduling, 5, 329-355.
[11]Garcia, J. M. and Lozano, S. (2005) Production and vehicle scheduling for ready-mix operations. Computers and Industrial Engineering, 46, 803-816.
[12]Gharbi, A. and Haouari, M. (2005) Optimal parallel machines scheduling with availability constraints. Discrete Applied Mathematics, 148, 63–87.
[13]Hall, L.A. and Shmoys, D.B. (1992) Jackson’s rule of single-machine scheduling: Making a good heuristic better. Mathematics of Operations Research, 17, 22-35.
[14]He, Y., Zhong, W. and Gu, H. (2006) Improved algorithms for two single machine scheduling problems. Theoretical Computer Science, 363, 257-265.
[15]Ji, M., He, Y. and Cheng, T. C. E. (2007) Batch delivery scheduling with batch delivery cost on a single machine. European Journal of OperationalResearch, 176, 745-755.
[16]Johnson, SM. (1954) Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61-68.
[17]Kellerer, H. and Pferschy, U. (1998) A new fully polynomial approximation scheme for the knapsack problem. Lecture Notes in Computer Science, 1444, 123-134.
[18]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.
[19]Lawler, E. (1979) Fast approximation algorithms for knapsack problems. Mathematics of Operations Research, 4, 339-356.
[20]Lee, C.Y. (1991) Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathrmatics, 30, 53-61.
[21]Lee, C.Y. (1996) Machines scheduling with an availability constraint. Journal of Global Optimization, 9, 395-416.
[22]Lee, C.Y. and Chen, Z.L. (1999) Two-machines flowshop scheduling with availability constraints. European Journal of Operational Research, 114, 420-429.
[23]Lee, C.Y. and Chen, Z.L. (2001) Machine scheduling with transportation considerations. Journal of Scheduling, 4, 3-24.
[24]Lee, Y.H., Jeong, C.S. and Moon, C. (2002) Advanced planning and scheduling with outsourcing in manufacturing supply chain. Computers and Industrial Engineering, 43, 351–374.
[25]Lee, C.-Y., Lei, L. and Pinedo, M. (1997) Current trends in deterministic scheduling. Annals of Operations Research, 70, 1-41.
[26]Lee, I. S. and Sung, C. S. (2007) Minimizing due date related measures for a single machine scheduling problem with outsourcing allowed. European Journal of Operational Research, 186, 931–952.
[27]Lin, C.H. and Liao, C.J. (2007) Makespan minimization for two parallel machines with an unavailable period on each machine. International Journal of Advanced Manufacturing Technology, 33, 1024–1030
[28]Liao, C.T., Shyur, D.L. and Lin, C.H. (2005) Makespan minimization for two parallel machines with an availability constraint. European Journal of Operational Research, 160, 445-456.
[29]Lu, L., Yuan, J. and Zhang, L. (2008) Single machine scheduling with release dates and job delivery to minimize the makespan. Theoretical Computer Science, 393, 102-108.
[30]Maggu, P.L. and Das, G. (1980) On 2×n sequencing problem with transportation times of jobs. Pure and Applied Mathematika Sciences, 12, 1-6.
[31]Maggu, P.L., Das, G. and Kumar, R. (1981) On equivalent job-for-job block in 2×n sequencing problem with transportation times. Journal of the Operations Research Society of Japan, 24, 136-146.
[32]Mastrolilli, M. (2003) Efficient approximation schemes for scheduling problems with release dates and delivery times. Journal of Scheduling, 6, 521-531.
[33]Mellouli, R., Sadfi, C., Chu, C.B. and Kacem, I. (2009) Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times. European Journal of Operational Research, 197, 1150–1165.
[34]Pan, C.H., Wu, C.L, Huang, H.C. and Su, C.S. (2009) Coordinating Scheduling with Batch Deliveries in a Two-Machine Flow Shop. International Journal of Advanced Manufacturing Technology, 40, 607-616.
[35]Panwalkar, S.S. (1991) Scheduling of a two machine flowshop with travel time between machines. Journal of the Operational Research Society, 42, 609-613.
[36]Pinedo, M. (1995) Scheduling: Theory, Algorithms, and Systems. Prentice-Hall: Englewoods Cliffs, NJ.
[37]Potts, C.N. (1980) Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research, 28, 1436-1441.
[38]Potts, C.N. and Kovalyov, M.Y. (2000) Scheduling with batching: A review. European Journal of Operational Research, 120, 228-249.
[39]Potts, C.N. and Van Wassenhove, L.N. (1992) Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity. Journal of the Operational Research Society, 43, 395-406.
[40]Qi, X. (2011) Outsourcing and production scheduling for a two-stage flow shop. International Journal of Production Economics, 129, 43-50.
[41]Schmidt, G. (1984) Scheduling on semi-identical process. Zeitschrift fur Operational Research, 28, 153-162.
[42]Simchi-Levi, D. (1994) New worst-case results for the bin packing problem. Naval Research Logistics, 41, 579-585.
[43]Soukhal, A., Oulamara, A. and Martineau, P. (2005) Complexity of flow shop scheduling problems with transportation constraints. European Journal of Operational Research, 161, 32-41.
[44]Stevens, J.W. and Gemmill, D.D. (1997) Scheduling a two-machine flowshop with travel times to minimize maximum lateness. International Journal of Production Research, 35, 1-15.
[45]Stern, H.I. and Vitner, G. (1990) Scheduling parts in a combined production-transportation work cell. Journal of the Operational Research Society, 41, 625-632.
[46]Sun Lee, I. and Yoon, S.H. (2010) Coordinated scheduling of production and delivery stages with stage-dependent inventory holding costs. Omega, 38, 509-521.
[47]Woeginger, G.J. (1994) Heuristics for parallel machine scheduling with delivery times. Acta Informatica, 31, 503-512.
[48]Wang, H. and Lee, C.Y. (2005) Production and Transport Logistics Scheduling with Two Transport Mode Choices. Naval Research Logistics, 52, 796-809.
[49]Wang, S. and Yu, J. (2009) An effective heuristic for flexible job-shop scheduling problem with maintenance activities. Computers and Industrial Engineering, 59, 436-447.
[50]Wang, X. and Cheng, T. C. E. (2009) Logistics scheduling to minimize inventory and transport costs. International Journal of Production Economics, 121, 266-273.
[51]Wang, Xiuli. and Cheng, T. C. E. (2007) Machine Scheduling with an Availability Constraint and Job Delivery Coordination. Naval Research Logistics, 54, 11-20.
[52]Yue, M. (1991) A simple proof of the inequality FFD(L)  11OPT(L)/9 + 1 L, for the FFD bin-packing algorithm. Acta Mathematica Applicate Sinica, 7, 321-331.
[53]Zhong, W., Do’sa, G. and Tan, Z. (2007) On the machine scheduling problem with job delivery coordination. European Journal of Operational Research, 182, 1057-1072.