本研究主要探討半導體及電子製造產業中常見的多機台流線式製程（Flow Shop with Multiple Processors；FSMP），求解工件到達時間不同與機台限制之二階段成批排程以最小化總完工時間。其中第一階段為序列加工（Serial）而第二階段為成批加工（Batch）的平行機台。針對此一困難的排程問題，我們首先建構一混整數規劃模型，再依據機台所能加工的工件數提出減少模型變數之技巧，以在較短時間內求解原模型無法處理之較大規模排程問題。根據測試得知，此技巧仍難以即時處理現實之大規模排程，因此我們依照工件的處理特性來調整工件成批加工順序，提出以傳統的FIFO派工法則為基礎的BFIFO派工法則；然而，該派工法則雖可快速排程，其排程品質卻可能因機台限制而變差。於是，我們再以該排程結果為基礎，提出數種機制以改善排程品質，其中包括先以BFIFO法則決定成批工件，再以混整數規劃模型規劃各成批工件的機台及其順序；或是將所得之排程進行各階段機台內及機台間之工件或批量的安插與互換，以在時限內收歛得更佳之排程，此即Translocation、Interchange及Transposition改善機制（簡稱TIT改善機制）。在數值測試方面，我們嘗試將本研究提出之數學規劃法、BFIFO派工法則以及相關的數種改善求解機制與Yang et al.（2004）所提出的禁忌搜尋法來進行效能與效率的比較以及敏感度分析，以驗證各解法之求解品質與效率。實驗結果顯示，本研究所提的BFIFO派工法則結合TIT改善機制大都能在較短的時間得到較佳的排程結果，因此本研究建議相關產業可嘗試使用此求解機制來解決其即時性排程需求。

This paper investigates a difficult scheduling problem on a specialized two-stage hybrid flow shop with multiple processors (FSMP) that often appears in semiconductor manufacturing industry, where the first and second stages process serial and parallel batches, respectively. The objective is to seek job-machine, job-batch, and batch-machine assignments such that makespan is minimized, while considering parallel batch, release time, and machine eligibility constraints. We first propose a mixed integer programming (MIP) formulation for this problem, then give a heuristic to estimate the upper bound on the number of jobs processed by a machine to reduce the size of original MIP. In order to handle real-world large-scale scheduling problems, we propose an efficient dispatching rule called BFIFO that assigns jobs or batches to machines based on first-in-first-out principle. To further improve the quality of the calculated schedule, we propose and test several re-optimization techniques using MIP and local search heuristics involving translocation, interchange and transposition (TIT) between assigned jobs. We compare our algorithms with the tabu search method by Yang et al.(2004). Computational experiments indicate our proposed re-optimization techniques are very efficient and effective. In particular, our method can produce good solutions for scheduling up to 160 jobs on 40 machines in both stages within 10 minutes.

[1] 郭宜雍，民94，以模擬為基礎之啟發式演算法求解平行機台排程問題，國立成功大學製造工程研究所，博士論文。
[2] Al-Anzi, F.S. and Allahverdi, A., 2009, Heuristics for a two-stage assembly flowshop with bicriteria of maximum lateness and makespan, Computers and Operations Research, 36, 2682-2689.
[3] Allaoui, H. and Artiba, A., 2006, Scheduling two-stage hybrid flow shop with availability constraints, Computers and Operations Research, 33, 1399-1419.
[4] Armentano, V.A. and Ronconi, D.P., 1999, Tabu search for total tardiness minimization in flowshop scheduling problems, Computers and Operations Research, 26, 219-235.
[5] Bellanger, A. and Oulamara, A., 2009, Scheduling hybrid flowshop with parallel batching machines and compatibilities, Computers and Operations Research, 36, 1982-1992.
[6] Ben-Daya, M. and Al-Fawzan, M., 1998, A tabu search approach for the flowshop scheduling problem, European Journal of Production Research, 35, 2857-2870.
[7] Botta-Genoulaz, V., 2000, Hybrid flowshop scheduling with precedence constrains and time lags to minimize maximum lateness, International Journal of Production Economics, 64, 101-111.
[8] Centeno, G. and Armacost, R.L., 1997, Parallel machine scheduling with release time and machine eligibility restrictions, 21st International Conference on Computers and Industrial Engineering, 33, 273-276.
[9] Centeno, G. and Armacost, R.L., 2004, Minimizing makespan on parallel machines with release time and machine eiligibility restrictions, International Journal of Production Research, 42, 1243-1256.
[10] Chen, B. and Vestjens, A.P.A., 1997, Scheduling on identical machines: How good is LPT in an on-line setting?, Operation Research Letters, 21, 165-169.
[11] Dobson, G. and Nambimadom, R.S., 2001, The batch loading and scheduling problem, Operations Research, 49, 52-65.
[12] Garey, M.R. and Johnson, D.S., 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, New York.
[13] Glover, F., 1989, Tabu Search – Part I, ORSA Journal on Computing, 1, 190-206.
[14] Glover, F., 1990, Tabu Search – Part II, ORSA Journal on Computing, 2, 4-32.
[15] Glover, F. and Kochenberger, G.A., 2003, Handbook of Metaheuristics, Kluwer Acadnic Publishers, London.
[16] Grangeon, N., Tanguy, A., and Tchernev, N., 1999, Generic simulation model for hybrid flow-shop, Computers and Industrial Engineering, 37, 207-210.
[17] Gupta, J.N.D., 1988, Two stage, hybrid flowshop scheduling problem, Journal of Operations Research Society, 39, 359-364.
[18] Gupta, J.N.D., Hariri, A.M.A., and Potts, C.N., 1997, Scheduling a two-stage hybrid flow shop with parallel machines at the first stage, Annals of Operations Research, 69, 171-191.
[19] Gupta, J.N.D., Kruger, K., Lauff, V., Werner, F., and Sotskov, Y.N., 2002, Heuristics for hybrid flow shops with controllable processing times and assignable due dates, Computers and Operations Research, 29, 1417-1439.
[20] Gupta, J.N.D. and Ruiz-Torres, A.J., 2005, Generating efficient schedules for identical parallel machines involving flow-time and tardy jobs, European Journal of Operation Research, 167, 679-695.
[21] Haouari, M. and M’Hallah, R., 1997, Heuristic algorithms for the two-stage hybrid flow shop problem. Operations Reseatch. 69, 171-191.
[22] Hoogeveen, J.A., Lenstra, J.K., and Veltman, B., 1996, Preemption scheduling in a two-stage multiprocessor flowshop is NP-hard, European Journal of Operational Research, 89, 172-175.
[23] Horowitz, E. and Sahni, S., 1976, Exact and approximate algorithm for scheduling nonidentical processors, Journal of the Association for Computing Machinery, 23, 317-327.
[24] Hung, Y.F., 1998, Scheduling of mask shop E-beam writers, IEEE Transactions on Semiconductor Manufacturing, 11, 165-172.
[25] Hunsucker, J.L. and Shah, J.R., 1994, Comparative performance analysis of priority rules in a constrained flow shop with multiple processors environment, European Journal of Operational Research, 72, 102-114.
[26] Jayamohan, M.S. and Rajendram, C., 2000, A comparative analysis of two different approaches to scheduling in flexible flow shop, Production Planning and Control, 11, 572-580.
[27] Jin, Z., Yang, Z., and Ito, T., 2006, Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem, International Journal of Production Economics, 100, 322-334.
[28] Johnson, S.M., 1954, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68.
[29] Kashan, A.H., Karimi, B., and Jenabi, M., 2008, A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes, Computers and Operations Research, 35, 1084-1098.
[30] Kelton, W.D., Sadowski, R.P., and Sturrock, D.T., 2007, Simulation with Arena, 4th edition, McGraw-Hill, New York.
[31] Kim, T.D., Kim, J.U., Lim, S.K., and Jun, H.B., 1998, Due-date based scheduling and control policies in a multiproduct semiconductor wafer fabrication facility, IEEE Transactions on Semiconductor Manufacturing, 11, 155-164.
[32] Kuo, Y., Yang, T., Peters, B.A., and Chang, I., 2007, Simulation metamodel development using uniform design and neural networks for automated material handling systems in semiconductor wafer fabrication, Simulation Modelling Practice and Theory, 15, 1002-1015.
[33] Lee, C.-Y. and Vairaktarakis, G.L., 1994, Minimizing makespan in hybrid flowshops, Operations Research Letters, 16, 149-158.
[34] Lin, S.W. and Ying, K.C., 2009, Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems, International Journal of Production Research, 5, 1411-1424.
[35] Malve, S. and Uzsoy R., 2007, A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families, Computer and Operations Research, 34, 3016-3028.
[36] Mathirajan, M., Sivakumar, A.I., and Chandru, V., 2002, Scheduling algorithms for heterogeneous batch processors with incompatible job-families, Proceeding of the International Conference on Responsive Manufacturing, Gaziantep, Turky, 769-774.
[37] Melouk, S., Damodaran, P., and Chang, P.Y., 2004, Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing, International Journal of Production Economics, 87, 141-147.
[38] Min, H.S. and Yih, Y., 2003, Development of a real-time multi-objective scheduler for a semiconductor fabrication system, International Journal of Production Research, 41, 2345-2364.
[39] Monch, L., Balasubramanian, H., Fowler, J.W., and Pfund, M.E., 2005, Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times, Computers and Operations Research, 32, 2731-2750.
[40] Mosheiov, G. and Oron, D., 2004, A note on the SPT heuristic for solving scheduling problem with generalized due dates, Computers and Operations Research, 31, 645-655.
[41] Osman, I.H., Metastratesy Simulated Annealing and Tabu Search Algorithms for Combinatorial Optimization Problems, United Kingdom：Philosophy of the University of London.
[42] Oulamara, A., 2007, Makespan minimization in a no-wait flow shop problem with two batching machines, Computers and Operations Research, 34, 1033-1050.
[43] Oulamara, A., Finke, G., and, Kamgaing Kuiten, A., 2009, Flowshop scheduling problem with batching machine and task compatibilities, Computers and Operations Research, 36, 391-401.
[44] Petroni, A. and Rizzi, A., 2002, A fuzzy logic based methodology to rank shop floor dispatch rules, International Journal of Production Ecnomics, 76, 99-108.
[45] Pinedo, M., 1995, Scheduling－Theory, algorithms, and systems, Prentice-Hall, Englewood Cliffs, New Jersey.
[46] Santos, D.L., Hunsucker, J.L., and Deal, D.E., 1995, Global lower bounds for flow shop with multiple processors, European Journal of Operational Research, 80, 112-120.
[47] Santos, D.L., Hunsucker, J.L., and Deal, D.E., 1996, An evaluation of sequencing heuristics in flow shops with multiple processors, Computers and Industrial Engineering, 30, 681-692.
[48] Soewandi, H., and Elmaghraby, S.E., 2001, Sequencing three-stage flexible flowshops with identical machines to minimize makespan, IIE Transactions, 33, 985-993.
[49] Uzsoy, R., 1995, Scheduling batch processing machine with incompatible job-families, International Journal of Production Research, 33, 2685-2708.
[50] Uzsoy, R., Church, L.K., and Ovacik, I.M., 1992, Dispatching rules for semiconductor testing operations: a computational study, IEEE/CHMT International Electronic Manufacturing Technology Symposium, 272-276.
[51] Van der Velde, S.L., 1993, Duality based algorithm for scheduling unrelated parallel machines, ORSA Journal on Computing, 5, 192-205.
[52] Wardono, B. and Fathi, Y., 2004, A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities, European Journal of Operational Research, 155, 380-401.
[53] Yang, T., Kuo, Y., and Chang, I., 2004, Tabu-search simulation optimization approach for flow-shop scheduling with multiple processors — a case study, International Journal of Production Research, 42, 4015-4030.
[54] Yang, T., Rajasekharan, M. and Peters, B.A., 1999, Semiconductor fabrication facility design using a hybrid search methodology, Computers and Industrial Engineering, 36, 565-583.