本研究主要是探討紡織工業中的織布工段。在生產系統中，每個工件皆具有某些數量的屬性，且每種屬性具有一個或多個不同程度的規格。因為任兩個相鄰工件之間，一定至少有一個不同程度的規格必須在機器上做調整，因此當一個工件必須轉換到下一個工件時，整備時間必定會發生。因此發展出多重屬性整備時間之非等效平行機排程問題，此排程問題是在將工件分配到不同機台上，以使得總完工時間極小化。本篇論文發展一個結構式演算法去獲得初始解及同時提出基因演算法並加入新的交配方式和三個鄰域搜尋，以期望能夠改善初始解並得到一個較佳可行解。最後，我們將所提出的演算法做測試，實驗結果顯示，我們在本篇論文所提出的方法對於求解這類型的問題是比原有的方法更有效率的。

This thesis focuses on the knitting process in textile industry. In such a production system, each job has a number of attributes and each attribute has one or more levels. Because there is at least one different level of attribute between two adjacent jobs, it is necessary to make a setup adjustment whenever there is a switch to a different job. Therefore, this thesis develops a scheduling approach for multi-attribute setup times on unrelated parallel machines. The objective of the problem is to assign jobs to different machines so as to minimize the makespan. This thesis proposes a constructive heuristic to obtain a good solution. To further improve the solution, the thesis proposes a meta-heuristic that uses genetic algorithms (GA) with new crossover operator and three local searches. By examining problem instances, the method proposed in this thesis outperforms the current scheduling method in solving the problem.

Al-Salem, A. Scheduling to minimize makespan on unrelated Parallel machines with sequence dependent setup times. Engineering Journal of the University of Qatar, 17, 177–187 (2004).
Armentano, V., Felizardo, M. Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach. European Journal of Operational Research, 183, 100–114 (2007).
Allahverdi, A., Ng, C. T., Cheng, T. C. E., and Kovalyov, M. Y. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187, 985–1032 (2008).
Arnaout, J. P., Rabadi, G., and Musa, R. 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–70 (2010).
Chen, J. F. Unrelated parallel machine scheduling with secondary resource constraints. The International Journal of Advanced Manufacturing Technology, 26, 285–292 (2005).
Chen, J. F. Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups. The International Journal of Advanced Manufacturing Technology, 29, 557–563 (2006).
Chen, J. F., Wu, T. H. Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints. OMEGA, The International Journal of Management Science, 34, 81–89 (2006).
Chen, W. J. Scheduling with dependent setups and maintenance in a textile company. Computers & Industrial Engineering, 57, 867–873 (2009).
Chuang, M. C., Liao, C. J., and Chao, C. W. Parallel machine scheduling with preference of machines. International Journal of Production Research, 48, 4139–4152 (2010).
Detti, P., Meloni, C., and Pranzo, M. Minimizing and balancing setups in a serial production system. International Journal of Production Research, 45, 5769–5788 (2007).
Fleszar, K., Charalambous, C., and Hindi, KS. A variable neighborhood descent heuristic for the problem of makespan minimisation on unrelated parallel machines with setup times. Journal of Intelligent Manufacturing, 23, 1949-1958 (2012).
Holland, J.H. Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor (1975).
Helal, M., Rabadi, G., and Al-Salem, A. A Tabu Search Algorithm to Minimize the Makespan for the Unrelated Parallel Machines Scheduling Problem with Setup Times. International Journal of Operations Research, 3, 182-192 (2006).
Kurz, M., Askin, R. Heuristic scheduling of parallel machines with sequence dependent
set-up times. International Journal of Production Research, 39, 3747-3769 (2001)
Kim, D. W., Kim, K. H., Jang, W., and Chen, F. F. Unrelated parallel machine scheduling with setup times using simulated annealing. Robotics and Computer Integrated Manufacturing, 18, 223–231 (2002).
Logendran, R., McDonell, B., and Smucker, B. Scheduling unrelated parallel machines with sequence-dependent setups. Computers & Operations Research, 34, 3420-3438 (2007).
Liao, C.J., Huang, G. Y. Makespan minimization for unrelated parallel machine problem with sequence dependent setup times. Unpublished master’s thesis, National Taiwan University of Science and Technology, Taiwan.
Liao, C. J., Tsai, Y. L., Chao, C. W. An ant colony optimization algorithm for setup coordination in a two-stage production system. Applied Soft Computing, 11, 4521-4529 (2011).
Lee, C. H., Liao, C. J., and Chao, C. W. Scheduling with multi-attribute setup times. Computers & Industrial Engineering, 63, 494–502 (2012).
Peyro, L. F., Ruiz R. Iterated greedy local search methods for unrelated parallel machine scheduling. European Journal of Operational Research, 207, 55-69 (2010).
Rabadi, G., Moraga, R. J., and Al-Salem, A. Heuristics for the unrelated parallel machine scheduling problem with setup times. Journal of Intelligent Manufacturing, 17, 85–97 (2006)
Rocha de Paula, M., Gomez Ravetti, M., Robson Mateus, G., and Pardalos, P. M. Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighbourhood search. IMA, Journal of Management Mathematics, 18, 101–115 (2007).
Ruiz, R., Allahverdi, A. No-wait flowshop with separate setup times to minimize maximum lateness. International Journal of Advanced Manufacturing Technology, 35, 551–565 (2007).
Tang, C. S. Scheduling batches on parallel machines with major and minor set-ups. European Journal of Operational Research, 46, 28–37 (1990).
Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., lzadi, M., and Sassani, F. Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations Research, 36, 3224-3230 (2009).
Vallada, E., Ruiz, R. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, 211, 612-622 (2011).