本論文考慮應用物料需求規劃技術的兩階段生產環境問題。第一階段為生產不同尺寸的零組件，第二階段則將這些零組件組裝成最終成品。此生產環境可生產多種不同的成品，每一個成品可以根據物料清單分解成好幾個不同的零組件，而且在不同成品中的相同零組件均可同時生產。在文獻中，重疊和批量分割是被認為能夠有效減少作業流程時間的方法，因此，此問題之組裝作業不需等待零組件全部生產完成即可進行組裝。同時，為了要降低零組件與成品的庫存，本論文以最小提早成本和延遲成本的總和作為求解的目標。由於此問題已被證明是高度複雜的問題，因此本論文利用題目特性發展出啟發式演算法與粒子群演算法來求解。經由電腦實驗顯示，本論文所提出的演算法可有效率地求解此問題。

This thesis considers a two-stage manufacturing shop based on Material Requirement Planning (MRP) structure. The shop produces some different sizes of parts or components in stage 1 and assembles those parts and components as a final product in stage 2. Many kinds of products can be produced in this environment. According to Bill of Material (BOM), each product can be separated into various parts or components, and also can be manufactured together once there are same components in different final product. In the literatures, overlapping and batch splitting are considered as an efficient method to control total flow time, hence the assembly line in the second stage does not have to wait for all the components being processed in the first stage. In addition, there is a need to reduce the stock of component and final product, therefore the objective of this problem is to minimize the total earliness and total tardiness. Because the problem is NP-hard, a heuristic is proposed in this thesis for the problem. To obtain a better solution, a Particle Swarm Optimization (PSO) algorithm combined with the properties of this problem and the heuristic is also proposed. Experimental results show that our proposed heuristic and PSO algorithm are quite efficient for the problem.

Anger, F.D., Lee, C.Y., Martin-Vega, L.A., Single-machine scheduling with tight windows. Research Paper, 1986, 86-16.

Bukchin, J., Tzur, M. Jaffe, M., Lot splitting to minimize average flow-time in a two-machine flow-shop. IIE Transactions, 2002, 34, 953-970.

Cetinkaya, F.C., Lot streaming in two-stage flowshop with set-up, processing and removal time separated. The Journal of the Operational Research Society, 1994, 45, 1445-2455.

Chan, F.T.S., Wong, T.C., Chan, P.L.Y., Equal size lot streaming to job-shop scheduling problem using genetic algorithms. IEEE, Computer Society, 2004, 472-476.

Cheng, T.C.E., Optimal common due date with limited completion time deviation. Computers and Operations Research, 1988, 15, 91-96.

Dastidar, S.G., Nagi, R., Batch splitting in an assembly scheduling environment. International Journal of Production Economics, 2007, 105, 372-384.

Eberhart, R.C., Kennedy J., A new optimizer using particle swarm theory. Proceedings of the sixth international symposium on micro machine and human science. IEEE Service Center. Piscataway, NJ, Nagoya, Japan, 1995, 39-43.

Fox, R.E., OPT An answer for America Part IV. Inventories and Production Magazine, 1987, 3, 210-221.

Gordon, V., Proth, J.M., Chu, C., A survey of the state of-the-art of common due date assignment and scheduling research. European Journal of Operational Research, 2002, 139, 1-25.

Garey, M.R., Johnson, D.S., Sethi, R., The complexity of flowshop and job shop scheduling. Mathematics of Operations Research, 1976, 1, 117-129.

Grave, S.C., A review of production scheduling. Operations Research, 1981, 18, 841-852.

Graves, S.C., Kostreva, M.M., Overlapping operations in material requirements planning. Journal of Operations Management, 1986, 6, 283-294.

Johnson, S.M., Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1954, 1, 61-68.

Kim, Y.D., Choi, S.W., Lee, G.C., Minimizing total tardiness of orders with reentrant lots in a hybrid flowshop. International Journal of Production Research, 2005, 43, 2149-2167.

Koulamas, C., Maximizing the weighted number of on-time jobs in single machine scheduling with time windows. Mathematical and Computer Modeling, 1997, 24, 57-62.

Koulamas, C., Single-machine scheduling with time windows and earliness/ tardiness penalties. European Journal of Operational Research, 1996, 91, 190-202.

Kropp, D.H., Smunt, T.L., Optimal and heuristic models for lot splitting in a flow shop. Decision Sciences, 1990, 21, 691-709.

Pinedo, M.L., Scheduling Theory Algorithms, and Systems, third edition. Prentice Hall, 2008, 74-75.

Rock, H., The Three-Machine No-Wait Flow Shop is NP-Complete, Journal of the Association for Computing Machinery, 1984, 31, 121-125.

Sarper, H., Minimizing the sum of absolute deviations about a common due date for the two-machine flow shop problem. Applied Mathematical Modeling, 1995, 19, 153-161.

Shim, S.O., Kim, Y.D., Scheduling on parallel identical machines to minimize total tardiness. European Journal of Operational Research, 2007, 177, 135-146.

Sloan, A., Mathematical programming approaches to capacity-constrained MRP system: review, formulation and problem reduction. Management Science, 1983, 10, 11-26.

Sloan, A.P., My years with general motors. Doubleday and Company, Incorporated, 1963, 125-139.

Suer, G.A., Subramanian A., Huang J., Heuristic procedures and mathematical models for cell loading and scheduling in a shoe manufacturing company. Computers & Industrial Engineering, 2009, 56, 462-475.

Tasgetiren, M.F., Sevkli, M., Liang Y.C., Gencyilmaz, G., Particle swarm optimization algorithm for permutation flowshop sequencing problem. Lecture Notes in Computer Science, 2004, 32, 366-385.

Wagner, H.M., An integer linear-programming model for machine scheduling. Naval Research Logistics Quarterly, 1959, 6, 131-140.

Weng, M.X., Ventura, J.A., Scheduling about a large common due date with tolerance to minimize mean absolute deviation of completion times. Naval Research Logistics, 1994, 41, 843-851.

Xing, W.X., Zhang, J.W., Parallel machine scheduling with splitting jobs. Discrete Applied Mathematics, 2000, 103, 259-269.

Yoon, S.H., Ventura, J.A., Minimizing the mean weighted absolute deviation from due dates in lot-streaming flowshop scheduling. Computers & Operations Research, 2002, 29, 1301-1315.

Yeung, W.K., Oğuz, C., Cheng, T.C.E., Two-stage flowshop earliness and tardiness machine scheduling involving a common due window. International Journal of Production Economics, 2004, 90, 421-434.

Yeung, W.K., Oğuz, C., Cheng, T.C.E., Two-machine flow shop scheduling with common due window to minimize weighted number of early and tardy jobs. Naval Research Logistics, 2009, 56, 593-59.