摘 要
許多產品的製造多採用混合式流程方式生產，將不同的處理階層加以串聯並於每一階層配置多台加工機台，以達到提昇處理效率減少總完工時間的目的。另外，於處理完一個工作後常常有一段設置時間，例如作模具調整等，再進行處理下一個工作，而在許多產品生產時，這種設置時間常會與工作的順序有關，使生產排程更具複雜性。由於混合式流程的可行解太過龐大，在工作數量較大時，即使以電腦亦無法於合理時間內求得最短總完工時間的正確解，而必須採用啓發式演算法以尋優過程逐步評估出排程之較佳解。本研究之目的即針對與工作順序有關之混合式流程生產型態，以修正之蟻群演算法評估不同混合式流程生產型態的排程，目標是使總完工時間最小。分析之生產型態包括4種工作數、3種工作階層數，每一階層有2種不同的平行等效機台的安排方式，以及4種平均設置與處理時間的比例，共計有96種組合型態。另外，設計了5種第一個工作及接續工作的選擇方式，以探討其對排程結果的影響。經由480組案例各運算10次，並統計出平均與最佳總完工時間、對應之迭代次數與電腦運算時間。研究結果建議了有效的排程方法，並驗證此排程方法可經由接續工作選擇以吸收設置時間使總完工時間縮短的效果，同時也分析了各生產型態參數變化時對混合式流程生產總完工時間的影響，並將各案例分析所得的總完工時間等結果列於附錄中供有興趣者參考。
關鍵字:混合式流程生產,設置時間和工作順序有關,蟻群演算法

Abstract
Many products are fabricated with hybrid flowshop, which has a number of stages in series and several parallel machines in each stage, in order to improve the efficiency and reduce the total completion time. On the other head, when a job is completed, a setup time such as mold adjustment is required before processing the next job. The setup time is often dependent on the job sequence and make the scheduling more complicated. Because the feasible solutions of hybrid flowshop are very large when the number of jobs are increased, the minimum completion time can not be reached within a reasonable time. We must use heuristic algorithm to figure out this question step by step to have a better solution. The purpose of this research is to deal with scheduling problem of hybrid flow shop with sequence dependent setup times. The modified ant colony optimization(ACO) evaluation procedure is developed and the target is to minimize the makespan. The production pattern analyzed include four kinds of job numbers, three kinds of stage numbers, two kinds of equivalent parallel machines in each stage and four kinds of setup times, summed up to 96 categories. Also we designed five kinds of methods to select the first job and the job sequence to discuss their effectiveness on the scheduling. Via 480 cases and compute ten times for each case to get the average and best makespan, corresponding iteration number and computing time. The result of this research suggest the effective scheduling method, and verify that this method can reduce the makespan through better selection of the job sequence. Also the parameter importance on the makespan are evaluated. The related results of makespan for all 480 cases are listed in the appendix for reference.
Key words:Hybrid Flowshop,Sequence-Dependent Setup Times,Ant Colony System

參考文獻
中文部分
王立志。 (2011)。記憶體模組產業供應鏈生產規劃模式之研究。行政院國家科學委員會補助專題研究計畫成果報告。
英文部分
Ahmadizar, F. A new ant colony algorithm for makespan minimization in permutation
flow shops. (2012). Computers and Industrial Engineering, 63, 355–361.
Allahverdi, A., Ng, C.T., Cheng, T.C.E., and Kovalyov, M.Y. (2008). A survey of
scheduling problems with setup times or costs. European Journal of Operational
Research, 187, 985–1032.
Alaykyran, K., Engin, O., and Alper, D. (2007). Using ant colony system optimization
to solve hybrid flow shop scheduling problems. International Journal of
Advanced Manufacturing Technology, 35, 541-550.
Arnaout, J.P., Rabadi, G., and Musa, R. (2010). A two–stage ant colony optimization
algorithm to minimize the makespan on unrelated parallel machines with
sequence–dependent setup times. Journal of Intelligent Manufacturing, 21,
693–701.
Behnamian, J., Fatemi Ghomi, S. M. T., and Zandieh, M. (2010). Development of a
hybrid metaheuristic to minimize earliness and tardiness in a hybrid flowshop
with sequence–dependent setup times. International Journal of Production
Research, 48, 1415–1438.
Chen, F. and Lee, C. Y. (2009). Minimizing the makespan in a two–machine
crossing–docking flow shop problem. European Journal of Operation Research,
16, 59–72.
Dorigo, M., Dicaro, G., and Gambardella, L.M. (1999). Ant algorithms for discrete
optimization. Arti Life 5:137-172.
Figielska, E. (2008). A new heuristic for scheduling the two-stage flowshop with
additional resources. Computers and Industrial Engineering, 54, 750–763.
Gajpal, Y., Rajendran, C., and Ziegler, H. (2006). An ant colony algorithm for
scheduling in flowshops with sequence-dependent setup times of jobs.
International Journal of Advanced Manufacturing Technology, 30, 416–424.
Gajpal, Y. and Rajendran, C. (2006). An ant–colony optimization algorithm for
minimizing the completion–time variance of jobs in flowshops. International
Journal of Production Economics, 101, 259–272.
Garey, M.R. and Johnson, D. S., Computers and Intractability. (1979). W. H. Freeman
and Co., San Francisco.
Gupta, J.N.D. (1988). Two-stage hybrid flow shop scheduling problem. J Oper Res
Soc. 39(4):359-364.
Johnson, S.M.(1954). Optimal two and three stage production schedules with setup
times include. Naval Research Logistics Quarterly 1, 61-67.
Jungwattanakit, J., Reodeeha, M., Chaovalitwongse, P., and Werner, F. (2008).
Algorithms for flexible flow shop problems with unrelated parallel machines,
setup times, and dual criteria. International Journal of Advanced Manufacturing Technology, 37, 354–370.
Karimi, N., Zandieh, M., and Karmooz, H.R. (2010). Bi objective groupscheduling
hybrid flexible flowshop: A multi–phase approach. Expert System with
Applications, 37, 4024–4032.
Keskinturk, T., Yildirim, M.B., and Barut, M. (2012). An ant colony optimization
algorithm for load balancing in parallel machines with sequence–dependent
setup times. Computers & Operations Research. 39, 1225–1235.
Khalouli, S., Ghedjati, F., and Hamzaoui, A. (2010). A meta–heuristic approach to
solve a jit scheduling problem in hybrid flow shop. Engineering Applications of
Artificial Intelligence, 23, 765–771.
Kurz, M.E. and Askin., R.G. (2003). Comparing scheduling rules for flexible flow
lines. International Journal of Production Economics, 85, 371–388.
Kurz, M.E. and Askin., A.G. (2004). Scheduling flexible flow lines with
sequence–dependent setup times. European Journal of Operational Research,
159,66–82.
Liao, C.J. and Juan, H.C. (2007). An ant colony optimization for single–machine
tardiness scheduling with sequence–dependent setups. Computers and Operations Research, 34, 1899–1909.
Lin, B.M.T., Lu, C.Y., Shyu, S.J., and Tsai, C.Y. (2008). Development of new
features of ant colony optimization for flowshop scheduling. International
Journal of Production Economics, 112, 742–755.
Mirabi, M. (2011). Ant colony optimization technique for the sequence–dependent
flowshop scheduling problem. International Journal of Advanced
Manufacturing Technology. 55, 317–326.
Moghaddam, R. T., Safaeic, N., and Sassanib, F. (2009). A gemetic algorithm for the
flexible flow line scheduling problem with processor blocking. Computers &
Operations Research, 36, 402 – 414.
Naderi, B., Zandieh, H., and Roshanaei, V. (2009). Scheduling hybrid flowshops
with sequence dependent setuptimes to minimize makespan and maximum
tardiness. International Journal of Advanced Manufacturing Technology. 41,
1186–1198.
Naderi, B., Zandieh, H., Khaleghi, G.B.A., and Roshanaei, V. (2009). An
improved simulated annealing for hybrid flowshops with sequence–dependent
setup and transportation times to minimize total completion time and total
tardiness. Expert System with Applications, 36, 9625–9633.
Naderi, B., Zandieh, H., and Shirazi, M.A.H.A. (2009). Modeling and scheduling a
case of flexible flowshops : total weighted tardiness minimization. Computers
and Industrial Engineering, 57, 1258–1267.
Neto, T. R. F. and Folho, G. M.(2011). An ant colony optimization approach to a
permutational flowshop scheuling problem with outsourcing allowed.
Computers and Opeartions Research, 38, 1286–1293.
Pan, Q.Ke, Pan M., Fatih, T., Suganthan,P.N., and Ozge, B. (2012). A variable
iterated greedy algorithm with differential evolution for solving no–idle
Flowshops. Lecture Notes In Computer Science, 7629, 128–135.
Pinedo, M.L. (1995). Scheduling, Theory, Algorithms, and Systems. Prentice- Hall,
Englewood Cliffs, NJ.
Rajendran, C.and Ziegler, H. (2004). Ant–colony algorithms for permutation
flowshop scheduling to minimize makespan/total flowtime of jobs. European
Journal of Operational Research, 155, 426–438.
Rajendran, C. and Ziegler, H. (2005). Two ant–colony algorithms for minimizing total
flowtime in permutation flowshops. Computers and Industrial Engineering, 48,
789–797.
Ruiz, R. and Maroto, C. (2006). A genetic algorithm for hybrid flowshops with
sequence dependent setup times and machine eligibility. European Journal of
Operational Research, 169, 781–800.
Seckiner,U. S. and Kurt, M. (2008). Ant colony optimization for the job rotation
scheduling problem. Applied Mathematics and Computation, 201, 149–160.
Shyu, S.J., Lin, B.M.T., and Yin, P.Y. (2004). Application of ant colony optimization
for no-wait flow shop scheduling problem to minimize the total completion
time. Computers and Industrial Engineering,47, 181–193.
Sortrakul, N., Nachtmann, H.L., and Cassady, C.R. (2005). Genetic algorithms for
integrated preventive maintenance planning and production scheduling for a
single machine. Computers in Industry, 56, 161–168.
Stuetzle T. and Hoos, H.H. (1998). Improvements on the ant system: introducing the
max–min ant system. In: RF Albrecht, GD Smith, NC Steele (Eds) Proceelings
of the 3rd International Conference on Artificial Norwich, UK, April 1997, pp
245-249.
Tavares N.R.F. and Godinho, F.M. (2011). An ant colony optimization approach to a
permutational flow shop scheduling problem with outsourcing allowed.
Computers and Operations Research, 38, 1286–1293.
Tkindt, V., Monmarche, N., Tercinet, F., and Laugt, D. (2002). An ant colony
optimization algorithm to solve a 2–machine bicriteria flowshop scheduling
problem. European Journal of Operational Research, 142, 250–257.
Tseng, C.T. and Liao, C.J. (2008). A particle swarm optimization algorithm for
hybrid flow shop scheduling with multiprocessor tasks. International Journal of
Production Research. 46, 4655-4670.
Tseng, L.Y. and Lin, Y.T. (2010). A genetic local search algorithm for minimizing
total flow time in the permutation flow shop scheduling problem. Int. J.
Production Economics, 127, 121–128.
Wang, X. and Tang, L. (2009). A tabu search heuristic for the hybrid flowshop
scheduling with finite intermediate buffers. Computers and Operations
Research, 36, 907-918.
Yagmahan, B. and Yenisey, M.M. (2008). Ant colony optimization for
multi-objective flowshop scheduling problem. Computers & Industrial
Engineering, 54, 411–420.
Yagmahan, B. and Yenisey, M.M. (2010). A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications, 37, 1361-1368.
Yaurima, V., Burtseva, L., and Tchernykh A. (2009). Hybrid flowshop with unrelated
machines, sequence-dependent setup time, availability constraints and limited
buffers. Computers and industrial engineering, 56, 1452-1463.
Ying, K.C. and Liao, C.J. (2004). An ant colony system for permutation flow-shop
sequencing. Computers & Operations Research, 31, 791–801.
Ying, K.C. and Lin, S.W. (2007). Multi-heuristic desirability ant colony system
heuristic for non-permutation flowshop scheduling problems. International
Journal of Advanced Manufacturing Technology, 33, 793–802
Ying, K.C. and Lin, S.W. (2006). Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach. International Journal of Production Research, 44, 3161–3177.