本論文考量族群整備時間之平行機排程問題，並以最小化總加權完工時間為目標。在製造過程中，當不同的批量轉換時，需要族群整備時間。我們發展一個啟發式演算法求解此問題。此演算法可以選取工件至適合的位置，並有效平衡所有機器負荷。換言之，此演算法可以有效地決定哪些批量是必須要被分開的。本計算實驗中包括兩種測試：第一個目標是最小化總加權完工時間；另一個目標是考慮所有工件的權重都相等，使總完工時間最小化。經由實驗結果指出，我們所提出的演算法較現有的演算法使用更少的計算時間，並且達到更佳的成果。

This thesis focuses on a parallel machine scheduling problem with family set-up times and an objective of minimizing total weighted flowtime. The family set-up time is incurred whenever there is a switch of processing from a job in one family to a job in another family. We develop a proposed heuristic which can select jobs into appropriate positions and balance the objectives for all machines. In other words, the proposed heuristic can select which families necessary to be split. There are two tests in our computational experiments: One is minimizing the total weighted completion time, and the other is minimizing the total completion time where all job weights are equal. Computational results show that the proposed heuristic performs well, especially in large problems, and that it outperforms an existing heuristic in terms of quality of solutions.

Azizoglu M., Webster S.T., 2003. Scheduling parallel machines to minimize weighted flowtime with family set-up times. International Journal of Production Research 41, 1199-1215.
Allahverdi A., Ng CT., Cheng TCE., Kovalyov MY., 2008. A survey of scheduling problems with setup times or costs. European Journal of Operational Research 187, 985-1032.
Bruno J., Coffman Jr. E.G., Sethi R., 1974. Scheduling independent tasks to reduce mean finishing time. Communications of the ACM 17, 382-387.
Barnes J.W., Laguna M., 1993. Solving the multiple-machine weighted flow time problem using tabu search. IIE Transactions 25, 121-128.
Conway R.W., Maxwell W.L., Miller L.W., 1967. Theory of Scheduling Addison-Wesley, Reading, MA.
Crauwels HAJ., Potts CN., Van Wassenhove LN., 1997. Local search heuristics for single machine scheduling with batch setup times to minimize total weighted completion time. Annals of Operations Research 70, 261-79.
Chen Z.L., Powell W.B., 2003. Exact algorithms for scheduling multiple families of jobs on parallel machines. Naval Research Logistics 50, 823-840.
Dunstall S., Wirth A., Baker KR., 2000. Lower bounds and algorithms for flowtime minimization on a single machine with set-up times. Journal of Scheduling 3, 51-69.
Dunstall S., Wirth A., 2005a. A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines. European Journal of Operational Research 167, 283-296.
Dunstall S., Wirth A., 2005b. Heuristic methods for the identical parallel machine flowtime problem with set-up times. Computer and Operations Research 32, 2479-2491.
Graves S.C., 1981. A review of production scheduling. Operations Research 29, 646-675.
Gupta J.N.D., 1988. Single facility scheduling with multiple job classes. European Journal of Operational Research 8, 42-45.
Ghosh JB., 1994. Batch scheduling to minimize total completion time. Operations Research Letters 16, 271-5.
Liao, L.M., Liao, C.J. 2002. A tabu search approach for single machine scheduling with major and minor setups. International Journal of Industrial Engineering: Theory Applications and Practice 9, 174-183.
Monma CL., Potts CN., 1989. On the complexity of scheduling with batch setup times. Operations Research 37, 798-804.
Mason AJ., Anderson EJ., 1991. Minimizing flow time on a single machine with job classes and setup times. Naval Research Logistics 38, 333-50.
Potts CN., Kovalyov MY., 2000. Scheduling with batching: A review. European Journal of Operational Research 120, 228-249.
Pinedo, M., 2002. Scheduling: Theory, Algorithms, and Systems, Second Edition, New Jersey, Prentice-Hall.
Rinnooy Kan A.H.G., 1976. Machine Scheduling Problems: Classification Complexity and Computations. Nijhoff, The Hague, Netherlands.
Williams DN., 1993. Machine scheduling problems with setup times. Masters’ Thesis, University of Melbourne, Australia.
Williams DN., Wirth A., 1996. A new heuristic for a single machine scheduling problem with setup times. Journal of the Operational Research Society 47, 175-80.
Webster S.T., 1997. The complexity of scheduling job families around a common due date. Operations Research Letters 20, 65-74.
Webster S.T., Azizoglu M., 2001. Dynamic programming algorithms for scheduling parallel machines with family setup times. Computer and Operations Research 28, 127-137.
Yi Y., Wang D.W., 2001a. Tabu search for scheduling grouped jobs on parallel machines. Journal of Northeastern University 22, 188-191.
Yi Y., Wang D.W., 2001b. Scheduling grouped jobs on parallel machines with setups. Computer Integrated Manufacturing Systems 7, 7-11.