本論文考量協調兩階段生產系統之時間成本問題。此問題是由一個廚房家具工廠其製造系統之實際應用延伸而來。工廠包含兩連續加工階段，即切割與塗漆作業。在不同階段中，所有屬性皆相同之物品組成一批量。同一階段內，當一組新批量的屬性類別和前一批量的屬性類別不同時，即產生整備成本，此成本與批量先後次序相關。本論文之目標為決定所有批量之順序，以最小化總整備時間成本。
本論文中，我們首度提出一派工法則 (Least Flexibility with Setups ; LFS)，此派工法則可相當有效率地產生比基因演算法 (Genetic Algorithm；GA)更好的解。此派工法則被應用於形成一個初解，並結合一個啟發自螞蟻群體合作行為之新興共通啟發式演算法 (Ant Colony Optimization；ACO)以更進一步改善此解，並在極短的運算時間下，得到顯著優於其他之共通啟發式演算法，實驗結果顯示我們提出之蟻群最佳化演算法有很好的求解效果。

This thesis is concerned with the coordination of setup times in a two-stage production system. The problem is derived from a furniture plant, where there are two consecutive departments including cutting and painting departments. In different departments, items are grouped according to different attributes. A sequence-dependent setup time is required in a stage when the new batch has a different level of attribute from the previous one. The objective is to minimize the total setup time. In this thesis, we first propose a simple dispatching rule called the Least Flexibility with Setups (LFS) rule. The LFS rule can yield a solution better than an existing genetic algorithm while using much less computation time. Using the LFS rule as both the initial solution method and the heuristic desirability, an ACO algorithm is developed to further improve the solution. Computational experiments show that the proposed ACO algorithm is quite effective in finding the near-optimal solution.

Agnetis, A., Detti, P., Meloni, C., and Pacciarelli, D., 2001. Set-up coordination between two stages of a supply chain. Annals of Operation Research 107, 15-32.
Bullnheimer, B., Hartl, R. F., and Strauss C., 1999. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research 89, 319-328.
Bauer, A., Bullnheimer, B, Hartl, R. F., and Strauss, C., 1999. An ant colony optimization approach for the single machine total tardiness problem. Proceedings of the 1999 Congress on Evolutionary Computation. New York: IEEE Press; 1445-1450.
Blum, C., and Sample, M., 2004. An ant colony optimization algorithm for shop scheduling problems. Journal of Mathematical Modelling algorithms 3, 285-308.
Bautista, J. and Pereira, J., 2007. Ant algorithms for a time and space constrained assembly line balancing problem. European Journal of operational Research 177, 2016-2032.
Corry, P. and Kozan, E., 2004. Ant colony optimization for machine layout problems. Computational Optimization and Applications 28, 287-310.
Cheng, T. C. E., Lazarev, A. A., and Gafarov, E. R. 2007. A hybrid algorithm for the single-machine total tardiness problem. Computers & Operations Research.
Detti, P., Meloni, C., and Pranzo, M., 2007a. Minimizing and balancing setups in a serial production system. International Journal of Production Research 45, 5769-5788.
Dorigo, M., and Gambardella, L.M., 1997. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation1 1, 53-66.
Dorigo, M., and Caro, G. D., 1999. The Ant Colony Optimization meta-heuristic. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, 11-32.
Den Besten, M., Stützle, T., and Dorigo, M., 2000. Ant colony optimization for the total weighted tardiness problem. Internatiional Conference Parallel problem Solving from Nature, Proceeding PPSN VI, 6th, 611-620.
Dorigo, M., Maniezzo, V., and Colorni A., 1996. Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on System, 26, 29-41.
Gambardella, L. M, Taillard, E. D., and Dorigo, M., 1999. Ant colonies for the quadratic assignment problem. Journal of Operational Research Society 50, 167-176.
Gajpal, Y., Rajendran, C., and Ziegler, H., 2006. An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs. Int J Adv. Manuf Technol 30, 416-424.
Gambardella, L. M., Taillard, É.D., and Agazzi, G., 1999. A multiple ant colony system for vehicle routing problems with time windows. New Ideas in Optimization, 63-76.
Gagné, C., Price, W. L., and Gravel, M., 2002. Comparing an ACO algorithm with other heuristic for the single machine scheduling problem with sequence-dependent setup times. Journal of the Operational Research Society 53, 895-906.
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.
Gagné, C., Gravel, M., and Price, W. L., 2006. Solving real car sequencing problems with ant colony optimization. European Journal of Operational Research 174, 1427-1448.
Hamed, Q. S., Babak, A., and Amirhosein, M. K., 2008. Website structure improvement: Quadratic assignment problem approach and ant colony meta-heuristic technique. Applied Mathematics and Computation 195, 285-298.
Holthaus, O., and Rajendran, C., 2005. A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs. Journal of the Operation Research Society 56, 947-953.
Liao, C. J., and Chen, C. C., 2006. A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date, Computers & Industrial Engineering.52, 404-413.
Liao, C. J., and Juan, H. C., 2005. An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups. Computers and Operations Research 34, 1899-1901.
Lawler, E. L., Lenstra, J. k., Rinnooy Kan, A. H.G., and Shmoys, D. B., 1985. The graveling saleman problem. Wiley.
Meloni, C., 2001. An Evolutionary algorithm for the sequence coordination in furniture production. Lecture Notes of Computer Science 2264, 91-106.
Mansouri, S.A., 2005. Coordination of set-ups between two stages of a supply chain using multi-objective genetic algorithms. International Journal of Production Research 43, 3163-3180.
Mansouri, S.A., 2006. A simulated annealing approach to a bi-criteria sequencing problem in a two-stage supply chain. Computers & Industrial Engineering 50, 105-119.
Merkle, D., Middendorf, M., and Schmeck, H., 2002. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation 6, 333-346.
Naimi, H. M., and Taherinead, N., 2007. New robust and efficient ant colony algorithms: Using new interpretation of local updating process. Expert Systems with Applications.
Naso, D., Turchiano, B., and Meloni, C., 2006. Single and multi-objective evolutionary algorithms for the coordination of serial manufacturing operations. Journal of Intelligent Manufacturing 17, 251-270.
Nilsson, C., 2003. Heuristics for the traveling salesman problem. Tech. Repot, Linkoping University, Sweden. http://www.ida.liu.se/TDDB19/reports_2003.
Rajendran, C., and Ziegler, H., 2005. Two ant-colony algorithms for minimizing total flowtime in permutation flowshops. Computers and Industrial Engineering 48, 789-797.
Stützle T, Hoos HH. Max-min ant system. 2000. Future Generation computer system, 16, 889-914.
Stützle, T. and Hoos, H. H., 1997. The MAX-MIN ant system and local search for the traveling salesman problem. IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference.
Stützle, T. and Hoos, H. H., 1998. The MAX-MIN ant system and local search for combinatorial optimization problems. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization.
Silva, C. A., Runkler, T. A., Sousa, J. M., and palm, R., 2002. Ant colonies as logistic process optimizers. Ant algorithms-proceedings of ANTS 2002-Third international workshop. Lecture Notes in Computer Science 2463, 76-87.
T’kindt, V., Monmarché, N., Tercinet, F., and Laügt, D., 2002. An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. European Journal of Operational Research 42, 250-257.
Ying, G. C., and Liao, C. J., 2004. Ant colony system for permutation flow-shop sequencing. Computers and Operations Research 30, 791-901.
Yu, B., Yang, Z. Z., and Yao, B., 2008. An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research