在各項產業中，客製化、多元化商品已成為許多企業的主要策略，本文探討台灣門鎖產業製造商於混和性商品裝配線上的指派與排程問題。門鎖產業的特性為每項產品所需要的零件種類繁多，製程複雜，故整體的製程安排與工作指派將直接影響企業的營運成本。本研究針對亞洲門鎖產業前三大的製造商－Ｆ公司作深入探討。以外銷為主的F公司主要產品為家用及商用門鎖、關門器等五金製品，在全時界各地都可以看見Ｆ公司相關系列產品，知名度相當高。本研究在需求與產能的限制之下，藉由建構一整數規劃之數學模式，以求解及探討製程安排與工作指派對整體存貨，人力以及延遲交貨等營運成本的影響。再以隱含式列舉演算法加快求解速度並改善求解效率，使此問題能夠擴大規模，更貼近實務需求。

This thesis investigates the mixed-product assembly line sequencing problem for a door lock manufacturing company in Taiwan. Companies in the door lock industry schedule their production processes to minimize their costs while meeting customer demand. The variance and diversity of lock components complicate the mixed-product assembly line sequencing problem and directly influence the material requirement planning and human resources costs. The assembly line sequencing problem of one of the largest ironware manufacturing companies in Asia, company F, is studied and an integer programming mathematical model with constraints on production lines, labor, warehouse capacity, and order fulfillment rates is formulated to minimize the total cost. A heuristic based on the Lagrangian relaxation principle is devised to solve this mixed-product assembly line sequencing problem. The efficiency of the proposed Lagrangian relaxation heuristic is evaluated by comparing its solutions with those obtained using CPLEX. The results show that the proposed heuristic solves the real-world problem almost 15 times faster than CPLEX in terms of CPU time, with equal solution quality. The salient results and practical issues involved in this unique problem are discussed in detail.

1. Al-E-Hashem, S., Malekly, H., & Aryanezhad, M. B. (2011), "A multi-objective robust optimization model for multi-product multi-site aggregate production planning in a supply chain under uncertainty,"International Journal of Production Economics, 134(1) pp.28~42.
2. Ahuja, R. K. , Magnanti, T. L., Orlin, J. B. (1993) Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River.
3. Alsheddy, A., & Tsang, E. P. K. (2011), "Empowerment scheduling for a field workforce,"Journal of Scheduling, 14(6) pp.639~654.
4. Barutcuoglu, S., & Azizoglu, M. (2011), "Flexible assembly line design problem with fixed number of workstations,"International Journal of Production Research, 49(12) pp.3691~3714.
5. Bautista, J., & Cano, A. (2011), "Solving mixed model sequencing problem in assembly lines with serial workstations with work overload minimisation and interruption rules,"European Journal of Operational Research, 210(3) pp.495~513.
6. Bianco, L., & Caramia, M. (2011), "Minimizing the completion time of a project under resource constraints and feeding precedence relations: a Lagrangian relaxation based lower bound,"4or-a Quarterly Journal of Operations Research, 9(4) pp.371~389.
7. Boysen, N., Fliedner, M., & Scholl, A. (2007), "A classification of assembly line balancing problems,"European Journal of Operational Research, 183(2) pp.674~693.
8. Brucker, P., Qu, R., & Burke, E. (2011), "Personnel scheduling: Models and complexity,"European Journal of Operational Research, 210(3) pp.467~473.
9. Bukchin, J., Dar-El, E. M., & Rubinovitz, J. (2002), "Mixed model assembly line design in a make-to-order environment,"Computers & Industrial Engineering, 41(4) pp.405~421.
10. Bukchin, J., & Masin, M. (2004), "Multi-objective design of team oriented assembly systems,"European Journal of Operational Research, 156(2) pp.326~352.
11. Castillo, I., Joro, T., & Li, Y. Y. (2009), "Workforce scheduling with multiple objectives,"European Journal of Operational Research, 196(1) pp.162~170.
12. Celano, G., Costa, A., Fichera, S., & Perrone, G. (2004), "Human factor policy testing in the sequencing of manual mixed model assembly lines,"Computers & Operations Research, 31(1) pp.39~59.
13. Chan, F. T. S., Wang, Z., & Zhang, J. (2007), "A two-level hedging point policy for controlling a manufacturing system with time-delay, demand uncertainty and extra capacity,"European Journal of Operational Research, 176(3) pp.1528~1558.
14. Chen, C. T., & Huang, S. F. (2006), "Order-fulfillment ability analysis in the supply-chain system with fuzzy operation times,"International Journal of Production Economics, 101(1) pp.185~193.
15. Dematta, R. (1994), "A lagrangean decomposition solution to a single line multiproduct scheduling problem,"European Journal of Operational Research, 79(1) pp.25~37.
16. Ding, F. Y., & He, J. (2008), "A heuristic procedure for the automobile assembly-line sequencing problem considering multiple product options,"International Journal of Production Research, 46(20) pp.5827~5847.
17. Eliiyi, D. T., & Oezlen, M. (2008), "A Lagrangean relaxation approach for the mixed-model flow line sequencing problem,"Computers & Operations Research, 35(3) pp.933~943.
18. Frangioni, A., & Gallo, G. (1999), "A bundle type dual-ascent approach to linear multicommodity min-cost flow problems,"Informs Journal on Computing, 11(4) pp.370~393.
19. Fumero, F. (2001), "A modified subgradient algorithm for Lagrangean relaxation,"Computers & Operations Research, 28(1) pp.33~52.
20. Giard, V., & Jeunet, J. (2010), "Optimal sequencing of mixed models with sequence-dependent setups and utility workers on an assembly line,"International Journal of Production Economics, 123(2) pp.290~300.
21. Hallgren, M., & Olhager, J. (2006), "Differentiating manufacturing focus,"International Journal of Production Research, 44(18-19) pp.3863~3878.
22. Krishnamoorthy, M., Ernst, A. T., & Baatar, D. (2012), "Algorithms for large scale shift minimisation personnel task scheduling problems,"European Journal of Operational Research, 219(1) pp.34~48.
23. Li, H., & Womer, K. (2009), "Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm,"Journal of Scheduling, 12(3) pp.281~298.
24. Little, D., & Hemmings, A. (1994), "Automated assembly scheduling - a review,"Computer Integrated Manufacturing Systems, 7(1) pp.51~61.
25. Lovgren, R. H., & Racer, M. J. (2000), "Algorithms for mixed-model sequencing with due date restrictions,"European Journal of Operational Research, 120(2) pp.408~422.
26. Martins, A. X., Duhamel, C., Mahey, P., Saldanha, R. R., & de Souza, M. C. (2012), "Variable neighborhood descent with iterated local search for routing and wavelength assignment,"Computers & Operations Research, 39(9) pp.2133~2141.
27. Mohan, S. (2008), "Scheduling part-time personnel with availability restrictions and preferences to maximize employee satisfaction,"Mathematical and Computer Modelling, 48(11-12) pp.1806~1813.
28. Nazarian, E., Ko, J. H., & Wang, H. (2010), "Design of multi-product manufacturing lines with the consideration of product change dependent inter-task times, reduced changeover and machine flexibility,"Journal of Manufacturing Systems, 29(1) pp.35~46.
29. Rekiek, B., De Lit, P., & Delchambre, A. (2000), "Designing mixed-product assembly lines,"IEEE Transactions on Robotics and Automation, 16(3) pp.268~280.
30. Rizk, N., Martel, A., & Ramudhin, A. (2006), "A Lagrangean relaxation algorithm for multi-item lot-sizing problems with joint piecewise linear resource costs,"International Journal of Production Economics, 102(2) pp.344~357.
31. Russell, M. L., & Meller, R. D. (2003), "Cost and throughput modeling of manual and automated order fulfillment systems,"IIE Transactions, 35(7) pp.589~603.
32. Srivastava, B., & Chen, W. H. (1996), "Batching in production planning for flexible manufacturing systems,"International Journal of Production Economics, 43(2-3) pp.127~137.
33. Suhail, A. (1983), "Realiability and Optimization Considerations in A Conveyor-Paced Assembly Line System,"International Journal of Production Research, 21(5) pp.627~640.
34. Sural, H., Denizel, M., & Van Wassenhove, L. N. (2009), "Lagrangean relaxation based heuristics for lot sizing with setup times,"European Journal of Operational Research, 194(1) pp.51~63.
35. Then, X. S., & Tsai, F. C. (2008), "The optimal production plan under limited production capacity at any point in time,"Journal of the Operations Research Society of Japan, 51(1) pp.81~94.
36. Tseng, Y.-J., Kao, H.-T., & Huang, F.-Y. (2010), "Integrated assembly and disassembly sequence planning using a GA approach,"International Journal of Production Research, 48(20) pp.5991~6013.
37. Wang, X., & Cheng, T. C. E. (2009), "Logistics scheduling to minimize inventory and transport costs,"International Journal of Production Economics, 121(1) pp.266~273.
38. Zhao, X. B., & Ohno, K. (2000), "Properties of a sequencing problem for a mixed model assembly line with conveyor stoppages,"European Journal of Operational Research, 124(3) pp.560~570.