本論文要探討經常發生於二階段機器組裝廠之批次排程問題。組裝廠的第一階段為一批次機器，在此，固定數量的工件材料與模組備妥後，批次機器以相同的加工時間，成批的將它們組裝為半成品。組裝後的半成品移往第二階段，此階段為一離散機器，以不同的加工時間，逐一的對工件進行機電整合與差異化工程。本文中，我們討論二個案例：(1)一般裝配線的批次排程問題：有一機器組裝廠，所有產品共用一條二階段組裝生產線，於第一階段批次機器開工前，需要一個固定的批次整備時間，以準備該批工件所需的零件，且第一、二階段加工一個新工件或切換不同群組工件時，都需要一個固定的群組整備時間，以準備該群組所需的夾具與工具。此排程問題求解一排程以達最大完工時間，總完工時間與總延遲時間加權和的最小化。(2)裝配島的批次排程問題：有一機器組裝廠，配置多個固定位置的裝配島，於第一階段批次機器開工前，需要一個群組相關的批次整備時間，以檢驗與準備批次生產所需的零件。且當產品完工時，若客戶尚未付清貨款，成品須由裝配島移往暫存區等待出貨，則需發生一個移機時間。此問題是求解一排程以達總完工時間的最小化。
以上二問題已證明為非多項式時間可解的困難問題，因此我們除了發展一個混合整數規劃模型，求解較小型問題的最佳解，另各提出二個啟發式方法，以求解其大型問題的近似最佳解。我們也進行計算實驗，以比較混合整數規劃模型與所提出的啟發式方法的求解績效，實驗結果顯示所建議的啟發式法比現行的排程法具有較佳的品質與績效，且可應用於與本文所討論案例相類似的實務問題。

In this thesis, we consider the batch scheduling problems for two-stage assembly shop, which are frequently encountered in the machinery manufacturing. In the first stage, a fixed number of jobs are assembled on a batch machine with a common processing time. Then the assembled jobs are moved to the second stage to perform system integration with different processing times on a discrete machine. In this thesis, two cases are considered: (1) Batch scheduling for an assembly line, and (2) Batch scheduling for assembly islands. In Case (1), all jobs in a machinery factory share a common assembly line. A constant batch setup time is needed to form a batch at the first stage and fixed family setup times are required on both stages when starting the processing of a new family or switching to a job in a different family. The objective is to find a schedule that minimizes the weighted sum of makespan, total completion time and total tardiness. In Case (2), a machinery factory is equipped with fixed-position assembly islands where each job must remain in an assembly island during its entire processing. A family batch setup time is needed to form a batch at the first stage and a fixed removal time is incurred when a finished job is moved from an assembly island to a temporary storage area if the payment has not been made. The objective is to minimize the total completion time.
Since the two considered problems have been proved to be NP-hard, we develop Mixed Integer Programming (MIP) models to find the optimal solutions for small-size problem and propose some heuristic methods for each large-size problem. We also conduct computational experiments to compare MIP models with the corresponding heuristic methods. The computational results show that the proposed methods (FBFS and P-FBFS) outperform the current scheduling methods and can be applied to resolve real-world problems similar to those in this thesis.

Agnetis, A., Rossi, F., Gristina, G., 1998. An exact algorithm for the batch sequencing problem in a two-machine flow shop with limited buffer. Naval Research Logistics 45, 141-164.
Ahmadi, J.H., Ahmadi, R.H., Dasu, S., Tang, C.S., 1992. Batching and scheduling jobs on batch and discrete processors. Operations Research 39, 750-763.
Al-Anzi, F.S., Allahverdi, A., 2009. Heuristics for a two-stage assembly flow shop with bi-criteria of maximum lateness and makespan. Computers & Operations Research 36, 2682-2689.
Allahverdi, A., Al-Anzi, F.S., 2006a. A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application. Computers & Operations Research 33, 1056-1080.
Allahverdi, A., Al-Anzi, F., 2006b. Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize makespan with setup times. International Journal of Production Research 44, 4713-4735.
Allahverdi, A., Gupta, J.N.D., Aldowaisan, T., 1999. A review of scheduling research involving setup considerations. OMEGA 27, 219-239.
Baker, K.R., 1999. Heuristic procedures for scheduling job families with setups and due dates. Naval Research Logistics, 46, 978-991.
Baker, K.R., Magazine, M.J., 2000. Minimizing maximum lateness with job families. European Journal of Operational Research 127, 126-139.
Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M.Y., Potts, C.N., Tautenhahn, T., van de Velde, S.L., 1998. Scheduling a batching machine. Journal of Scheduling 1, 31-54.
Bukchin, J., Tzur, M., Jaffe, M., 2002. Lot splitting to minimize average flow-time in a two-machine flow-shop. IIE Transactions 34, 953-970.
Chan, F.T.S., Wong, T.C., Chan, L.Y., 2009. The application of genetic algorithms to lot streaming in a job-shop scheduling problem. International Journal of Production Research 47, 3387-3412.
Chandru, V., Lee, C.Y., Uzsoy, R., 1993a. Minimizing total completion time on batch processing machines. International Journal of Production Research 31, 2097-2121.
Chandru, V., Lee, C.Y., Uzsoy, R., 1993b. Minimizing total completion time on a batch processing machine with job families. Operations Research Letters 13, 61-65.
Chen, J.S., Pan, J.C.H., Lin, C.M., 2008. A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem. Expert Systems with Applications 34, 570-577.
Cheng T.C.E., Gupta J.N.D., Wang G., 2000a. A review of flow shop scheduling research with setup times. Production and Operations Management 9, 262-282.
Cheng, T.C.E., Lin, B.M.T., Toker A., 2000b. Makespan Minimization in the Two-Machine Flowshop Batch Scheduling Problem. Naval Research Logistics 47, 128-144.
Cheng, T.C.E., Wang, G., 1999. Scheduling the fabrication and assembly of components in a two-machine flow shop. IIE Transactions 31, 135-143.
Damodaran, P., Manjeshwar, P.K., Srihari, K., 2006. Minimizing makespan on a batch processing machine with non-identical job sizes using genetic algorithms. International Journal of Production Economics 103, 882-891.
Du, J., Leung, J., 1990. Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research 15, 483-495.
Eren, T., 2007. A multicriteria flow shop scheduling problem with setup times. Journal of Materials Processing Technology 186, 60-65.
Framinan, J.M., Leisten, R., Ruiz-Usano, R., 2002. Efficient heuristics for flow shop sequencing with the objectives of makespan and flow time minimization. European Journal of Operational Research 141, 559-569.
Garey, M.R., Johnson, D.S., Sethi, R., 1976. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research 1, 117-129.
Gokhale, R., Mathirajan, M., 2011. Heuristic algorithms for scheduling of a batch processor in automobile gear manufacturing. International Journal of Production Research 49, 2705-2728.
Gong, H., Tang, L., Duin, C.W., 2010. A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times. Computers & Operations Research 37, 960-969.
Hariri, A.M.A., Potts, C.N., 1997. A branch and bound algorithm for the two-stage assembly scheduling problem. European Journal of Operational Research 103, 547-556.
Hillier, F.S., Lieberman, G.J., 2001. Introduction to Operations Research, 7th Edition. McGraw-Hill, New York, pp 576-590.
Hochbaum, D.S., Landy, D., 1997. Scheduling semiconductor burn-in operations to minimize total flow-time. Operations Research 45, 874-885.
Hochbaum, D.S., Landy, D., 1997. Scheduling with batching: Two job types. Discrete Applied Mathematics 72, 99-114.
Hoogeveen, J.A., Kawaguchi, T., 1999. Minimizing total completion time in a two-machine flowshop: Analysis of special cases. Mathematics of Operations Research 24, 887-913.
Hoogeveen, J.A., van de Velde, S.L., 1998. Scheduling by positional completion times: analysis of a two-stage with a batching machine. Mathematical Programming 82, 273-289.
Huang G.Q., Zhang Y.F., Jiang P.Y., 2007. RFID-based wireless manufacturing for walking-worker assembly islands with fixed-position layouts. Robotics and Computer-Integrated Manufacturing 23, 469-477.
Kadipasaoglu, S.N., Xiang, W., Khumawala, B.M., 1999. Batch scheduling in a multistage, multiproduct manufacturing system - an application. International Journal of Operations and Production Management 19, 421-437.
Kim, D.W., Na, D.G., Chen F. F., 2003. Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective. Robotics and Computer Integrated Manufacturing 19, 173-181.
Koulamas, C., Kyparisis, G.J., 2007. A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines. European Journal of Operational Research 182, 945-951.
Laha, D., Sarin, S.C., 2009. A heuristic to minimize total flow-time in permutation flow shop. Omega 37, 734-739.
Lee, W.C., Wu, C.C., 2004. Minimizing total completion time in a two-machine flowshop with a learning effect. International Journal of Production Economics 88, 85-93.
Lee, C.Y., Cheng, T.C.E., Lin, B.M.T., 1993. Minimizing the makespan in the 3-machine assembly-type flow shop scheduling problem. Management Science 39, 616-625.
Lee, C.Y., Uzsoy, R., 1999. Minimizing makespan on a single batch processing machine with dynamic job arrivals. International Journal of Production Research 1, 219-236.
Lee, C.Y., Uzsoy, R., Martin-Vega, L.A., 1992. Efficient algorithms for scheduling semiconductor burn-in operations. Operations Research 40, 764-775.
Lin, B.M.T., Cheng, T.C.E., 2002. Fabrication and assembly scheduling in a two machine flow shop. IIE Transactions 34, 1015-1020.
Lin, B.M.T., Cheng, T.C.E., Chou, A.S.C., 2007. Scheduling in an assembly-type production chain with batch transfer. Omega 35, 143-151.
Liu, L.L., Ng, C.T., Cheng, T.C.E., 2009. Bicriterion scheduling with equal processing times on a batch processing machine. Computers & Operations Research 36,110-118.
Liu, Z., Yu, W., 2000. Scheduling one batch processor subject to job release dates. Discrete Applied Mathematics 105, 129-136.
Luo, H., Huang, G.Q., Zhang, Y.F., Dai, Q.Y., 2011. Hybrid flowshop scheduling with batch-discrete processors and machine maintenance in time windows. International Journal of Production Research 49, 1575-1603.
Melouk, S., Damodaran, P., Chang, P.Y., 2004. Minimising makespan for single machine batch processing with non-identical job sizes using simulated annealing. International Journal of Production Economics 87, 141-147.
Mokhtari, H., Abadi, I.N.K. and Cheraghalikhani, A., 2011. A multi-objective flow shop scheduling with resource-dependent processing times: trade-off between makespan and cost of resources. International Journal of Production Research, 49, 5851–5875.
Neale, J.J., Duenyas, I., 2000. Control of manufacturing networks which contain a batch processing machine. IIE Transactions 32, 1027-1041.
Potts, C.N., Sevast’Janov, S.V., Strusevich, V.A., Wassenhove, L.N., Zwaneveld, C.M., 1995. The two-stage assembly scheduling problem: Complexity and approximation. Operations Research 43, 346-355.
Potts, C.N., Strusevich, V.A., Tautenhahn, T., 2001. Scheduling batches with simultaneous job processing for two-machine shop problems. Journal of Scheduling 4, 25-51.
Pranzo, M., 2004. Batch scheduling in a two-machine flow shop with limited bufferand sequence independent setup times and removal times. European Journal of Operations Research 153, 581-592.
Qin, W., and Huang, G.Q., 2009. A two-level genetic algorithm for scheduling in assembly islands with fixed-position layouts. Proceedings of the 16th ISPE International Conference on Concurrent Engineering. London, Springer, Part 1, 17–28.
Rajendran, C., Chaudhuri, D., 1992. Scheduling in n-job, m-stage flowshop with parallel processors to minimize makespan. International Journal of Production Economics 27, 137-143.
Rajendran, C., Ziegler, H., 1997. An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs. European Journal of Operational Research, 103, 129-138.
Sabouni, M.T.Y., Jolai, F., 2010. Optimal methods for batch processing problem with makespan and maximum lateness objectives. Applied Mathematical Modelling 34, 314-324.
Su, L.H., Yang, D.L., Chou, H.K., 2009. A two-stage flowshop scheduling with limited buffer. Asia-Pacific Journal of Operational Research 26, 503-522.
Taboada, H.A., Coit, D.W., 2008. Multi-objective scheduling problems: Determi- nation of pruned Pareto sets. IIE Transactions 40, 552-564.
The MathWorks Inc., 2004. Getting Started with MATLAB Version 7. MathWorks Inc. 3 Apple Hill Drive Natick, MA.
Tozkapan, A., Kirca, O., Chung, C.S., 2003. Abranch and bound algorithm to minimize the total weighted flow time for the two-stage assembly scheduling problem. Computers and Operations Research 30, 309-320.
Uzsoy, R., 1994. Scheduling a single batch processing machine with non-identical job sizes. International Journal of Production Research 32, 1615-1635.
Webster, S., Baker, K.R., 1995. Scheduling groups of jobs on a singe machine. Operations Research 43, 692-703.
Yokoyama, M., 2001. Hybrid flow shop scheduling with assembly operations. International Journal of Production Economics 73, 103-116.
Yokoyama, M., 2004. Scheduling for two-stage production system with setup and assembly operations. Computers & Operations Research 31, 2063-78.
Yokoyama, M., 2008. Flow-shop scheduling with setup and assembly operations. European Journal of Operational Research 187, 1184-1195.