本論文旨在討論單階段與多階段之平行機排程問題。在單階段部分，將針對兩種批次環境做探討，依序為批次到達與批次到期；在多階段部分，我們將混合型流程生產問題的每個階段均視為一個平行機來作探討。
本論文首先探討在平行機台上之批次到達問題。一般文獻中，工件常被假設是單獨到達或是分開到達，但實務上工件經常是批次性到達，因此探討批次到達問題是較貼近實際情況的。針對此問題，本論文發展一個數學模式及一個演算法，並提出兩個下限值的計算方式來評估演算法的精確度；此外，除了與下限值做比較外也與目錄法做比較。實驗結果顯示，此演算法求出之解與下限值平均誤差在1.58%內，且比目錄法更有效率地解決此問題。
接著，本論文探討在平行機上之批次到期問題，批次到期是指工件經常被群組成數個批次，而同批次內的所有工件的到期日是相同的，亦即每個批次都有一個共同到期日。此問題在實務上經常發生，目前卻沒有有效的解決方法，因此本論文發展出兩個演算法來求解批次到期問題之總延遲時間。與現有可應用於此問題的方法比較結果顯示，本論文提出之演算法可以得到較好的解。
最後，本論文探討在多階段的平行機台上之最大完工時間最小化問題。我們提出一個全新的演算法來求解此高複雜度之問題，以免疫球蛋白為基礎的人工免疫系統方法來得出最佳排程，此方法依據新的再結合與體細胞超突變的方法來改善現有的人工免疫系統，因此更貼近人類實際的免疫系統。經實驗證明，本論文提出之新型人工免疫系統方法，較現有之人工免疫系統方法與其它非人工免疫系統方法更有效率地求解混合型流程生產問題。

This dissertation studies the single- and multi-stages parallel machine problems. For the single-stage parallel machine problem, this dissertation will consider two topics, batch arrival and batch due date. For the multi-stage parallel machine problem, a hybrid flow shop problem will be considered where each stage has identical parallel machines.
First, most studies in the scheduling literature assume that jobs arrive at time zero, while some studies assume that jobs arrive individually at non-zero times. However, both assumptions may not be valid in practice because jobs usually arrive in batches. In this topic, a scheduling model for an identical parallel machine problem with batch arrivals is formulated. Because of the NP-hardness of the problem, a heuristic based on a simplified version of lexicographical search is proposed. To verify the heuristic, two lower bounding schemes are developed, where one lower bound is tight, and the list scheduling heuristic is compared. Extensive computational experiments demonstrate that the proposed heuristic is quite efficient in obtaining near optimal solution with an average error of less than 1.58%. The percentage improvement (from the lower bound) of the heuristic solution on the solution by the list scheduling is as large as 31.68.
Secondly, this dissertation considers a scheduling problem where jobs are grouped into several batches. Jobs can be sent to the next operation only when all the jobs in the same batch have finished their processing, i.e., jobs in a batch have a common due date. This batch due date problem is quite common in practice, but there is no efficient heuristic to solve the problem. This dissertation addresses an identical parallel machine problem with batch due date to minimize the total tardiness. Since the problem is NP-hard, two heuristics are proposed to find the near optimal solution. Computational results comparing the effectiveness and efficiency of the two proposed heuristics with an existing heuristic are reported and discussed.
Finally, this dissertation considers the n-job, k-stage problem in a hybrid flow shop with the objective of minimizing the maximum completion time, or makespan, where the problem is NP-hard. An immunoglobulin-based artificial immune system algorithm, called IAIS, is developed to search for the best sequence. IAIS which is better fit the natural immune system improves the existing AIS by developing new somatic recombination and hypermutation methods. To verify IAIS, comparisons with the existing immune-based algorithms and other non-immune-based algorithms are made. Computational results show that IAIS is very competitive for the hybrid flow shop scheduling problem.

Abiri, M.B., Zandieh, M., Tabriz, A. A., 2009. A tabu search approach to hybrid flow shop scheduling with sequence-dependent setup time. Journal of Applied Sciences 9, 1740-1745.
Alaykyran, K., Engin, O., Doyen, A., 2007. Using ant colony optimization to solve hybrid flow shop scheduling problems. International Journal of Advanced Manufacturing Technology 35, 541-550.
Alidaee, B., Rosa, D., 1997. Scheduling parallel machines to minimize total weighted and unweighted tardiness. Computers & Operations Research 24, 775-788.
Arthanari, T.S., Ramamurthy, K.S., 1971. An extension of two machines sequencing problem. Opsearch 8, 10-22.
Bagheri, A., Zandieh, M., Mahdavi, I., Yazdani, M., 2010. An artificial immune algorithm for the flexible job–shop scheduling problem. Future Generation Computer System 26, 533-541.
Baker, K.R., Bertrand, J.W.M., 1982. A dynamic priority rule for scheduling against due-dates. Journal of Operations Management 3, 37-42.
Besbes, W., Loukil, T., Teghem, J., 2006. Using genetic algorithm in the multiprocessor flow shop to minimize the makespan. Proceedings of the International Conference on Service Systems and Service Management, 1228-1233, France.
Bish, E.K., Chen, F., Leong, T., Li, C., Ng, W.C., Simchi-Levi, D., 2001. Analysis of a new scheduling and location problem. Naval Research Logistics 46, 363-385.
Biskup, D., Herrmann, J., Gupta, J.N.D., 2008. Scheduling identical parallel machines to minimize total tardiness. International Journal of Production Economics 115, 134-142.
Brah, S.A., Hunsucker, J.L., 1991. Branch and bound algorithm for the flow shop with multiple processors. European Journal of Operational Research 51, 88-99.
Carlier, J., Neron, E., 2000. An exact method for solving the multiprocessor flowshop. R.A.I.R.O- Operations Research 34, 1-25.
Cheng, T.C.E., Sin, C.C.S., 1990. A state-of-the-art review of parallel-machine scheduling research. European Journal of Operational Research 47, 271-292.
Chung, T.P., Liao, C.J., Su, L.H., 2010. Scheduling on identical machines with batch arrivals. International Journal of Production Economics 123, 179-186.
Coffman, E.G.Jr., Garey, M.R., Johnson, D.S., 1978. An application of Bin-Packing to multiprocessor scheduling. SIAM Journal on Computing 7, 1-17.
Conway, R.W., Maxwell, W.L., Miller, L.W., 1967. Theory of Scheduling. Addison-Wesley, Reading, MA.
Daganzo, C.F., 1989. The crane scheduling problem. Transportation Research Part B 23, 159-175.
Debels, D., Reyck, B. D., Leus, R., Vanhoucke, M., 2006. A hybrid scatter search/ electromagnetism meta-heuristic for project scheduling. European Journal of Operational Research 169, 633-638.
Dell’Amico, M., Martello, S., 1995. Optimal scheduling of tasks on identical parallel processors. INFORMS Journal on Computing 7, 191-200.
Dogramaci, A., Surkis, J., 1979. Evaluation of a heuristic for scheduling independent jobs on parallel identical processors. Management Science 25, 1208-1216.
Emmons, H., 1969. One machine sequencing to minimize certain functions of job tardiness. Operations Research 17, 701-715.
Engin, O., Doyen, A., 2004. A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Generation Computer System 20, 1083-1095.
Foster, F.G., 1961. Queues with batch arrivals I. Acta Mathematica Hungarica 12, 1-10.
Garey, M.R., Johnson, D.S., 1979. Computers and intractability: a guide to the theory of NP-completeness, Freeman and Company, NY.
Gordon, V., Proth, J.M., Chu, C., 2002. A survey of the state-of-art of common due date assignment and scheduling research. European Journal of Operational Research 139, 1-25.
Graham, R.L., 1966. Bounds for certain multiprocessing anomalies. The Bell System Technical Journal XLV, 1563-1581.
Gupta, J.N.D., 1988. Two-stage, hybrid flowshop scheduling problem. Journal of the Operational Research Society 39, 359-364.
Gupta, J.N.D., Tunc, E.A., 1991. Schedules for a two stage hybrid flowshop with parallel machines at the second stage. International Journal of Production Research 29, 1489-1502.
Gupta, J.N.D., Tunc, E.A., 1994. Scheduling a two-stage hybrid flowshop with separable setup and removal times. European Journal of Operational Research 77, 415-428.
Gupta, J.N.D., Hariri, A.M.A., 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.
Haouari, M., Gharbi, A. and Jemmali, M., 2006. Tight bounds for the identical parallel machine scheduling problem. International Transactions in Operational Research 13, 529-548.
Heydari, M., Fakhrzad, M.B., 2008. A heuristic algorithm for hybrid flow shop production scheduling to minimize the sum of the earliness and tardiness costs. Journal of the Chinese Institute of Industrial Engineers 25, 105-115.
Ho, J.C., Chang, Y.L., 1991. Heuristics for minimizing mean tardiness for m parallel machines. Naval Research Logistics 38, 367-381.
Hu, X.F., Bao, J.S., Jin, Y., 2010. Minimising makespan on parallel machines with precedence constraints and machine eligibility restrictions. International Journal of Production Research 48, 1639-1651
Hurink, J., Knust, S., 2001. List scheduling in a parallel machine environment with precedence constraints and setup times. Operations Research Letters 29, 231-239.
Janiak, A., Kozan, E., Lichtenstein, M., Oğuz, C., 2007. Metaheuristic approaches to hybrid flow shop scheduling problem with a cost-related criterion. International Journal of Production Economics 105, 407-424.
Khalouli, S., Ghedjati, F., Hamzaoui, A., 2009. An integrated ant colony optimization algorithm for the hybrid flow shop scheduling problem. Computers & Industrial Engineering International Conference, 554-559, France.
Koulamas, C., Kyparisis, G.J., 2004. Makespan minimization on uniform parallel machines with release times. European Journal of Operational Research 157, 262-266.
Koulamas, C., 1997. Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem. Naval Research Logistics 44, 109-125.
Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P., 1977. Complexity of machine scheduling problems. Annals of Discrete Mathematics 1, 343-362.
Li, R., Huang, H.C., 2004. On-line scheduling for jobs with arbitrary release times. Computing 73, 79-97.
Lin, C.H., Liao, C.J., 2008. Makespan minimization for multiple uniform machines. Computers & Industrial Engineering 54, 983-992.
Lin, H.T., Liao, C.J., 2003. A case study in a two-stage hybrid flow shop with setup time and dedicated machines. International Journal of Production Economics 86, 133-143.
Mokotoff, E., 2001. Parallel machine scheduling problems: A survey. Asia-Pacific Journal of Operational Research 18, 193-243.
Mokotoff, E., 2004. An exact algorithm for the identical parallel machine scheduling problem. European Journal of Operational Research 152, 758-769.
Mourisli, O., Pochet, Y., 2000. A branch-and-bound algorithm for the hybrid flow shop. International Journal of Production Economics 64, 113-125.
Naseri, M.R.A., Nia, M.A.B., 2009. Hybrid flow shop scheduling with parallel batching. International Journal of Production Economics 117, 185-196.
Nawaz, M., Enscore, E.E., Ham, I., 1983. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11, 91-95.
Neron, E., Baptise, P., Gupta, J.N.D., 2001. Solving hybrid flow shop problem using energetic reasoning and global operations. Omega 29, 501-511.
Niu, Q., Zhou, T., Ma, S., 2009. A quantum-inspired immune algorithm for hybrid flow shop with makespan criterion. Journal of Universal Computer Science 15, 765-785.
Oğuz, C., Ercan, M. F., 2005. A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Journal of Scheduling 8, 323-351.
Panwalkar, S.S., Smith, M.L., Koulamas, C., 1993. A heuristic for the single machine tardiness problem. European Journal of Operational Research 70, 304-310.
Parham, P., 2005. The Immune System, Second Edition. Garland Science Publishing, NY.
Peterkofsky, R.L., Daganzo, C.F., 1990. A branch and bound solution method for the crane scheduling problem. Transportation Research Part B 24, 159-172.
Pinedo, M., 2002. Scheduling: Theory, Algorithms, and Systems, Second Edition, New Jersey, Prentice-Hall.
Prakash, A., Khilwani, N., Tiwari, M. K., Cohen, Y., 2008. Modified immune algorithm for job selection and operation allocation problem in flexible manufacturing systems. Advances in Engineering Software 39, 219-232.
Riane, F., Artibs, A., Elmaghraby, S.E., 1998. A hybrid three stage flow shop problem: Efficient heuristics to minimize makespan. European Journal of Operational Research 109, 321-329.
Ribas, I., Leisten, R., Framinan, J. M., 2010. Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Computers and Operations Research 37, 1439-1454.
Ruiz, R., 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.
Tamir, A., 1979. Scheduling jobs to two machines subject to batch arrival ordering. Naval Research Logistics 26, 521-525.
Tanaka, S., Araki, M., 2008. A branch-and-bound algorithm with lagrangian relaxation to minimize total tardiness on identical parallel machines. International Journal of Production Economics 113, 446-458.
Tavakkoli-Moghaddam, R., Rahimi-Vahed, A., Mirzaei, A. H., 2007. A hybrid multi-objective immune algorithm for a flow shop scheduling problem with biobjectives: Weighted mean completion time and weighted mean tardiness. Information Sciences 177, 5072-5090.
Wilkerson, L.J., Irwin, J.D., 1971. An improved algorithm for scheduling independent tasks. AIIE Transactions 3, 239-245.
Wolfner, G. Telek, M., 2000. Numerical analysis of queues with batch arrival. Performance Evaluation 41, 179-194.
Yalaoui, F., Chu, C., 2002. Parallel machine scheduling to minimize tardiness. International Journal of Production Economics 76, 265-279.
Zandieh, M., Fatemi Ghomi, S. M. T., Moattar Husseini, S. M., 2006. An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times. Applied Mathematics and Computation 180, 111-127.