Modeling and Scheduling Two-stage Assembly Flow Shop Problems with Non-Identical Assembly Machines
Authors
Abstract
The purpose of this research is to deal with the problem of two-stage assembly flow shop scheduling. A number of single-item products (identical) each formed of several different parts are ordered. Each part has m operations done at the first stage with m different machines. After manufacturing the parts, they are assembled into a final product with some non-identical machines. The purpose of the problem is to find the optimal sequence of the parts in the manufacturing stage, allocation and the optimal sequence of the products in the assembly stage. A mixed integer linear programming model and two metaheuristic algorithms, which are particle swarm with local search (MPSO) and simulated annealing (SA), are presented to solve this problem. Computational experiments are conducted to evaluate the performance of the proposed model and algorithms. The results show that the MPSO algorithm performs better than the SA one.
Keywords
1. Yokoyama, M., and Santos, D. L., “Three-stage Flow-shop Scheduling with Assembly Operations to Minimize the Weighted Sum of Product Completion Times”, European Journal of Operational Research, Vol. 161, pp. 754-770, 2005.
2. Kan, A. H. G. R., Machine Scheduling Problems, Martinus Nijhoff, Hague, 1976.
3. Allahverdi, A., and Al-Anzi, F. S., “The Two-stage Assembly Scheduling Problem to Minimize Total Completion Time with Setup Times”, Computers and Operations Research, Vol. 36, pp. 2740-2747, 2009.
4. Lee, C. Y., Cheng, T. C. E., and Lin, B. M. T., “Minimizing the Makespan in the 3-machine Assembly-type Flowshop Scheduling Problem”, Management Science, Vol. 39, pp. 616-625, 1993.
5. Potts, C. N., Sevast Janov, S. V., Strusevich, V. A., Van Wassenhove, L. N., and Zwaneveld, C. M., “The Two-Stage Assembly Scheduling Problem: Complexity and Approximation”, Operations Research, Vol. 43, pp. 346-355, 1995.
6. Hariri, A. M. A., and Potts, C. N., “A Branch and Bound Algorithm for the Two-stage Assembly Scheduling Problem”, European Journal of Operational Research, Vol. 103, pp. 547-556, 1997.
7. Cheng, T. C. E., and Wang, G., “Scheduling the Fabrication and Assembly of Components in a Two-machine Flowshop”, IIE Transactions, Vol. 31, pp. 135-143, 1999.
8. Sung, C. S., and John, J., “Makespan Minimization for a 2-stage Assembly Scheduling Problem Subject to Component Available Time Constraint”, International Journal of Production, Vol. 119, pp. 392-401, 2009.
9. Yokoyama, M., “Hybrid Flow-shop Scheduling with Assembly Operations”, International Journal of Production Economics, Vol. 73, pp. 103-116, 2001.
10. Rios-Mercado, R. Z., and Bard, J. F., “The Flowshop Scheduling Polyhedron with Setup Times”, Journal of Combinatorial Optimization, Vol. 7, pp. 291-318, 2003.
11. Kennedy, J., and Eberhart, R., “Particle Swarm Optimization”, Proceedings of IEEE International Conference on Neural Networks, Vol. 4, pp. 1942-1948, 1995.
12. Ge, H. W., Sun, L., Liang, Y. C., and Qian, F., “An Effective PSO and AIS-based Hybrid Intelligent Algorithm for Job-shop Scheduling”, IEEE Transactions on Systems, Man and Cybernetics, Part A, Vol. 38, pp. 358-368, 2008.
13. Kuo, I. H., Horng, S. J., Kao, T. W., Lin, T. L., Lee, C. L., and Terano, T., “An Efficient Flow-shop Scheduling Algorithm Based on a Hybrid Particle Swarm Optimization Model”, Expert Systems with Applications, Vol. 36, pp. 7027-7032, 2009.
14. Liao, C. J., Tseng, C. T., and Luarn, P., “A Discrete Version of Particle Swarm Optimization for Flowshop Scheduling Problems”, Computers and Operations Research, Vol. 34, pp. 3099-3111, 2007.
15. Xia, W., and Wu, Z., “A Hybrid Particle Swarm Optimization Approach for the Jobshop Scheduling Problem”, The International Journal of Advanced Manufacturing Technology, Vol. 29, pp. 360-366, 2005.
16. Gen, M., Tsujimura, Y., and Kubota, E., “Solving Job Shop Scheduling Problem using Genetic Algorithms”, Proceedings of the 16th International Conference on Computer and Industrial Engineering, Ashikaga, Japan, pp. 576-579, 1994.
17. Lin, T. L., Hong, S. J., Kao, T. W., Chen, Y. H., Run, R. S., Chen, R. J., Lai, J. L., and Kuo, I. H., “An Efficient Job-shop Scheduling Algorithm Based on Particle Swarm Optimization”, Expert Systems with Applications, Vol. 37, pp. 2629-2636, 2010.
18. Cochran, W. G., and Cox, G. M., Experimental Designs, 2nd ed., Wiley, USA, 1992.
19. Ross, R. J., Taguchi Techniques for Quality Engineering, McGraw-Hill, USA, 1989.
2. Kan, A. H. G. R., Machine Scheduling Problems, Martinus Nijhoff, Hague, 1976.
3. Allahverdi, A., and Al-Anzi, F. S., “The Two-stage Assembly Scheduling Problem to Minimize Total Completion Time with Setup Times”, Computers and Operations Research, Vol. 36, pp. 2740-2747, 2009.
4. Lee, C. Y., Cheng, T. C. E., and Lin, B. M. T., “Minimizing the Makespan in the 3-machine Assembly-type Flowshop Scheduling Problem”, Management Science, Vol. 39, pp. 616-625, 1993.
5. Potts, C. N., Sevast Janov, S. V., Strusevich, V. A., Van Wassenhove, L. N., and Zwaneveld, C. M., “The Two-Stage Assembly Scheduling Problem: Complexity and Approximation”, Operations Research, Vol. 43, pp. 346-355, 1995.
6. Hariri, A. M. A., and Potts, C. N., “A Branch and Bound Algorithm for the Two-stage Assembly Scheduling Problem”, European Journal of Operational Research, Vol. 103, pp. 547-556, 1997.
7. Cheng, T. C. E., and Wang, G., “Scheduling the Fabrication and Assembly of Components in a Two-machine Flowshop”, IIE Transactions, Vol. 31, pp. 135-143, 1999.
8. Sung, C. S., and John, J., “Makespan Minimization for a 2-stage Assembly Scheduling Problem Subject to Component Available Time Constraint”, International Journal of Production, Vol. 119, pp. 392-401, 2009.
9. Yokoyama, M., “Hybrid Flow-shop Scheduling with Assembly Operations”, International Journal of Production Economics, Vol. 73, pp. 103-116, 2001.
10. Rios-Mercado, R. Z., and Bard, J. F., “The Flowshop Scheduling Polyhedron with Setup Times”, Journal of Combinatorial Optimization, Vol. 7, pp. 291-318, 2003.
11. Kennedy, J., and Eberhart, R., “Particle Swarm Optimization”, Proceedings of IEEE International Conference on Neural Networks, Vol. 4, pp. 1942-1948, 1995.
12. Ge, H. W., Sun, L., Liang, Y. C., and Qian, F., “An Effective PSO and AIS-based Hybrid Intelligent Algorithm for Job-shop Scheduling”, IEEE Transactions on Systems, Man and Cybernetics, Part A, Vol. 38, pp. 358-368, 2008.
13. Kuo, I. H., Horng, S. J., Kao, T. W., Lin, T. L., Lee, C. L., and Terano, T., “An Efficient Flow-shop Scheduling Algorithm Based on a Hybrid Particle Swarm Optimization Model”, Expert Systems with Applications, Vol. 36, pp. 7027-7032, 2009.
14. Liao, C. J., Tseng, C. T., and Luarn, P., “A Discrete Version of Particle Swarm Optimization for Flowshop Scheduling Problems”, Computers and Operations Research, Vol. 34, pp. 3099-3111, 2007.
15. Xia, W., and Wu, Z., “A Hybrid Particle Swarm Optimization Approach for the Jobshop Scheduling Problem”, The International Journal of Advanced Manufacturing Technology, Vol. 29, pp. 360-366, 2005.
16. Gen, M., Tsujimura, Y., and Kubota, E., “Solving Job Shop Scheduling Problem using Genetic Algorithms”, Proceedings of the 16th International Conference on Computer and Industrial Engineering, Ashikaga, Japan, pp. 576-579, 1994.
17. Lin, T. L., Hong, S. J., Kao, T. W., Chen, Y. H., Run, R. S., Chen, R. J., Lai, J. L., and Kuo, I. H., “An Efficient Job-shop Scheduling Algorithm Based on Particle Swarm Optimization”, Expert Systems with Applications, Vol. 37, pp. 2629-2636, 2010.
18. Cochran, W. G., and Cox, G. M., Experimental Designs, 2nd ed., Wiley, USA, 1992.
19. Ross, R. J., Taguchi Techniques for Quality Engineering, McGraw-Hill, USA, 1989.
)