在這篇論文中，我們研究三個具有多重屬性整備時間的排程問題。此三個排程問題皆是由實務的三座聚氯乙烯 (Polyvinyl Chloride; PVC) 生產工廠之現行排程方法發展而來。首先，第一個排程問題是產生自聚氯乙烯膠布 (PVC sheet) 工廠。在PVC膠布工廠的排程問題中，每個工件皆具有某些數量的屬性，且每種屬性具有一個或多個不同程度的規格。因為任兩個相鄰工件之間，一定至少有一個不同程度的規格必須在機器上做調整，因此當一個工件必須轉換到下一個工件時，整備時間必定會發生。此排程問題的目標函數是在單機上決定一個加工次序，以使得總整備時間極小化。由於此問題為旅行銷售員問題的一個特例，我們必須根據所提出的幾個定理來發展一個建構式的啟發式演算法，以針對此排程問題求解。我們以一個現存的建構式啟發演算法、一個禁忌搜尋演算法 (Tabu search) 以及一個動態規劃分別與我們發展的啟發式演算法做比較，以便驗證此啟發式演算法的效率與效果。實驗結果證明，我們發展的建構式啟發演算法明顯優於現行PVC膠布工廠使用的排程方法，且改善的幅度非常明顯。
第二個排程問題是產生自聚氯乙烯膠皮 (PVC leather) 工廠。此問題與PVC膠布工廠一樣具有多重屬性整備時間的特性，且經常存在兩部相同平行機的加工環境於PVC膠皮工廠中。因此，我們研究的排程問題可歸類為具有多重屬性整備時間的兩部相同平行機問題，且此問題中的整備時間與第一個問題的整備時間同為順序相依。目標函數則是在兩部相同平行機上決定一個排程，使得最大完工時間極小化。首先我們針對此排程問題提出一個建構式的啟發式演算法，簡稱為COIT演算法，並與工廠現行排程方法做比較，以評估此演算法的績效。為了進一步改善此啟發式演算法所求得的解，我們另外提出一個通用啟發式演算法，稱為變動鄰域搜尋 (VNS) 演算法，並且與一個混整數規劃模型做比較。實驗結果證明，我們提出的啟發式演算法明顯優於現行PVC膠皮工廠所使用的排程方法，可得到大幅度的改善。另外，我們提出的VNS演算法，其績效也證實能有效改善啟發式演算法所求得的解。
最後一個研究的排程問題是產生自聚氯乙烯管件 (PVC pipe) 工廠，此排程問題同樣具有多重屬性整備時間的特性。PVC管件有兩個主要的屬性:口徑與顏色。每一個屬性具有一個相對應的屬性整備時間，且通常具有數個不同程度的規格。不同的PVC管件產品根據不同的大、中及小口徑安排到各自的專用機器上生產。大口徑及中口徑的專用機器可生產其他口徑的產品，但小口徑的專用機器只能生產小口徑及中口徑的產品。各專用機器若生產不同口徑的管件產品，其處理時間必定會增加。此非等效平行機之排程問題的目標是使得總流程時間為最短。我們針對此問題提出三個建構式啟發式演算法，並且與工廠現行的排程方法做比較。所提出之建構式啟發式演算法的效果與效率已經過實驗的驗證。實驗結果證明，提出的三個啟發式演算法明顯優於工廠現行的排程方法，具有大幅度的改善效果，並且能在合理時間內針對大型題目求解。

In this dissertation we address three scheduling problems with multi-attribute setup times. All of these scheduling problems are originated from the manufacturing plants of a company producing PVC products. In the first considered scheduling problem from the PVC sheet plant, 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. The objective of the problem is to determine a processing sequence so as to minimize the total setup time on a single machine. Since the problem is a special case of the travelling salesman problem, we have to develop a constructive heuristic based on several theorems for the problem. The heuristic has been evaluated by comparing with an existing constructive heuristic, a tabu search heuristic and a dynamic programming approach, and its efficiency and effectiveness have been demonstrated. The computational results show that the proposed heuristic outperforms the current scheduling method used by the case plant with a significant improvement.
The second scheduling problem is originated from the PVC leather plant which has the same characteristic of multi-attribute setup times as the PVC sheet plant. In the considered PVC leather plant, there usually exist two identical parallel machines environment. Therefore, the studied scheduling problem can be classified as a two identical parallel machine scheduling problem with multi-attribute setup times. The setup times are also sequence-dependent which is similar to those in the PVC sheet plant. The objective is to determine a schedule for two identical parallel machines to minimize the makespan. A constructive heuristic, named COIT, is first proposed for the problem and evaluated by comparing with the current scheduling method used by the case plant. To further improve the solution, a variable neighborhood search (VNS) meta-heuristic is presented and compared with a mixed integer programming model. The computational results show that the COIT heuristic outperforms the current scheduling method with a significant improvement, and the VNS can further improve the solution.
The last scheduling problem is originated from the PVC pipe plant which also has the characteristic of multi-attribute setup times. There are two main attributes of PVC pipes: diameter and color. Each attribute has a corresponding attribute setup time and usually has several different levels. Each extruder produces different PVC pipe products based on the diameters as large, middle and small. The alternatives exist between these extruders, where the large and the middle type extruders can be used to produce the PVC pipes with the other diameters; the small type extruders can be used to produce the PVC pipes with middle diameters but cannot produce those with large diameters. The processing times are longer in all of the alternatives among different types of extruders. The objective is to minimize the total completion time for the unrelated parallel machine problem. Three dedicated machine heuristics are proposed herein for the problem and have been evaluated by comparing with the current scheduling method used in the case plant. The computational results show that the proposed constructive heuristics outperform the current scheduling method with significant improvements and can be used to solve large-size problems in reasonable computational times.

REFERENCES
Abdekhodaee, A. H., Wirth, A., and Gan, H. S. Scheduling two parallel machines with a single server: the general case. Computers & Operations Research, 33, 994–1009 (2006)
Abreu, C. F., May J. H., Spangler W. E. and Vargas L. G. Conflict identification and reconciliation in a collaborative manufacturing scheduling task. International Journal of Information Technology and Decision Making, 7, 147–174 (2008)
Agnetis, A., Detti, P., Meloni, C., and Pacciarelli, D. Set-up coordination between two stages of a supply chain. Annals of Operation Research, 107, 15–32 (2001)
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)
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)
Ausiello, G., Escoffier, B., Monnot, J., and Paschos, V. Reoptimization of minimum and maximum traveling salesman's tours. Journal of Discrete Algorithms, 7, 453-463 (2009)
Baker, K. R. Introduction to Sequencing and Scheduling. John Wiley, NY (1974)
Balakrishnan, N., Kanet, J. J., and Sridharan, ‘Sri’ V. Early/tardy scheduling with sequence dependent setups on uniform parallel machines. Computers & Operations Research, 26, 127–141 (1999)
Balasubramanian, H., Fowler, J., Keha, A., and Pfund, M. Scheduling interfering job sets on parallel machines. European Journal of Operational Research, 199, 55–67 (2009)
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)
Bruno, J., Coffman, E.G., and Sethi, R. Scheduling independent tasks to reduce mean finishing time. Communications of the ACM, 17, 382–387 (1974)
Chan, F. T. S., Choy, K. L., and Bibhushan. A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop. Expert Systems with Applications, 38, 8703–8715 (2011)
Chang, P.Y., Damodaran, P., and Melouk, S. Minimizing makespan on parallel batch processing machines. International Journal of Production Research, 42, 4211–4220 (2004)
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, W. J. Scheduling with dependent setups and maintenance in a textile company. Computers & Industrial Engineering, 57, 867–873 (2009)
Chen, Z. L., and Powell, W. B. Solving parallel machine scheduling problems by column generation. INFORMS Journal on Computing, 11, 78–94 (1999)
Christofides, N. Worst-case analysis of a new heuristic for the travelling salesman problem. Management Sciences Research Report No. 388, Carnegie-Mellon University (1976)
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)
Eilon, S., Watson-Gandy, C., & Christofides, N. Distribution management: Mathematical modeling and practical analysis, Griffin, London (1971)
Esckilsen, B. Global PVC markets: threats and opportunities. Plastics, Additives and Compounding, 10, 28–30 (2008)
Gravel, M., Price, W.L. Gagné, C. Scheduling continuous casting of aluminum using a multiple objective ant colony optimization meta-heuristic. European Journal of Operational Research, 143, 218–229 (2002)
Gupta, J. N. D. Optimal schedules for single facility with classes. Computers & Operations Research, 11, 409–413 (1984)
Hansen, P., Mladenović, N., and Pérez, J. A. M. Variable neighbourhood search: methods and applications. Annals of Operations Research, 175, 367–407 (2010)
Huang, S., Cai, L., and Zhang, X. Parallel dedicated machine scheduling problem with sequence-dependent setups and a single server. Computers & Industrial Engineering, 58, 165–174 (2010)
Imran, A., Salhi, S., and Wassan, N. A. A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem. European Journal of Operational Research, 197, 509–518 (2009)
Karp, R. Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane. Mathematics of Operations Research, 2, 209–224 (1977)
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)
Lee, C. H., Liao, C. J., and Chao, C. W. Scheduling with multi-attribute setup times. Computers & Industrial Engineering, 63, 494–502 (2012)
Li, K., and Yang, S. L. Non-identical parallel-machine scheduling research with minimizing total weighted completion times: Models, relaxations and algorithms. Applied Mathematical Modelling, 33, 2145–2158 (2009)
Li, S. A hybrid two-stage flowshop with part family, batch production, major and minor set-ups. European Journal of Operational Research, 102, 142–156 (1997)
Liao, C. J., Chen, C. M., and Lin, C. H. Minimizing makespan for two parallel machines with job limit on each availability interval. Journal of the Operational Research Society, 58, 938–947 (2007)
Liao, C. J., and Liao, L. M. Single facility scheduling with major and minor setups. Computers & Operations Research, 24, 169–178 (1997).
Liao, C. J., Shyu, C. C. and Tseng, C. T. A least flexibility first heuristic to coordinate setups in a two-or three-stage supply chain. International Journal of Production Economics, 117, 127–135 (2009).
Liao, C. J. and Yu, W. C. Sequencing heuristics for dependent setups in a continuous process industry, Omega, 24, 649–659 (1996).
Lopes, M. J. P., and Valério de Carvalho, J. M. A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times. European Journal of Operational Research, 176, 1508–1527 (2007).
Mansouri, S. A. Coordination of set-ups between two stages of a supply chain using multi-objective genetic algorithms. International Journal of Production Research, 43, 3163–3180 (2005).
Mansouri, S. A. A simulated annealing approach to a bi-criteria sequencing problem in a two-stage supply chain. Computers & Industrial Engineering, 50, 105–119 (2006).
McGraw, K. E. and Dessouky, M. M. Sequence-dependent batch chemical scheduling with earliness and tardiness penalties. International Journal of Production Research, 39, 3085–3107 (2001).
Mladenović, N., and Hansen, P. Variable neighborhood search. Computers and Operations Research, 24, 1097–1100 (1997).
Mokotoff, E. Parallel machine scheduling problems: a survey, Asia - Pacific Journal of Operational Research, 18, 193–242 (2001)
Mosheiov, G. Parallel machine scheduling with a learning effect. Journal of the Operational Research Society, 52, 1165–1169 (2001)
Nawaz, M., Enscore Jr., E. E., Ham, I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA, The International Journal of Management Science, 11, 91–95 (1983)
Pinedo, M. Scheduling: Theory, algorithms, and systems, Second edition, Prentice Hall: NJ (2002).
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., Gómez 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).
Rosenkrantz, D. Stearns, R., & Lewis, P. Approximate algorithms for the traveling salesperson problem. Proceedings of the 15th Annual IEEE Symposium on Switching and Automata Theory, pp. 33–42 (1974).
Sun, K., and Li, H. Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines. International Journal of Production Economics, 124, 151–158 (2010).
Tahar, D. N., Yalaoui, F., Chu, C., and Amodeo, L. A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times. International Journal of Production Economics, 99, 63–73 (2006).
Tang, C. S. Scheduling batches on parallel machines with major and minor set-ups. European Journal of Operational Research, 46, 28–37 (1990).
Weng, M. X., Lu, J., and Ren, H. Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective. International Journal of Production Economics, 70, 215–226 (2001).