||A Lagrangian Relaxation Approach to the Mixed-product Assembly Line Sequencing Problem: A Case Study of a Door-Lock Company in Taiwan
||Department of Transportation & Communication Management Science
Mixed-product assembly line sequencing
Lagrangian relaxation heuristic
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.
Table of Contents
1. Introduction 1
1.1. Motivation 1
1.2. Purpose 1
1.3 Research Process 5
2. Literature Review 7
2.1 Assembly Line Sequencing Problem 7
2.2 Workforce Scheduling 11
2.3 Lagrangian Relaxation 15
3. Mathematical Formulation 19
3.1 Model Assumptions 19
3.2 Notation 21
3.3 Mathematical Model 23
4. Heuristic Design 27
4.1 LR Problem 27
4.2 LR Heuristic 34
4.3 Local Search 39
4.4 Subgradient Method 41
5. Computational Experiments 44
5.1 Computational Results 44
5.2 Sensitivity Analyses 49
5.2.1 Demand Fluctuation 50
5.2.2 Daily Demand Fulfillment 53
5.2.3 Delay Cost 56
5.2.4 Production Capacity 60
6. Conclusions and Future Research 62
7. Acknowledgements 64
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.