Simple assembly line balancing problem under task deterioration

Abstract: This paper introduces the effect of task deterioration in simple assembly line balancing problem. In many realistic assembly lines, a deterioration task is considered when a task is started earlier than the assigned time since the station time is constant and the earliness of the task does not reduce the cycle time. This phenomenon is known as deteriorating tasks. Therefore, we seek an optimal assignment and schedule of tasks in workstations, in order to minimize the number of stations for a given cycle time, which is known as SALBP-1. For this purpose, a mathematical model is proposed. Since the pure SALBP-1 is proved to be NP-hard and considering task deterioration complicates problem further, we propose a genetic algorithm for solving such problem. Several well-known test problems are solved to study the performance of the proposed approach.

How to cite this paper

 Noushabadi, M., Bahalke, U., Dolatkhahi, K., Dolatkhahi, S & Makui, A. (2011). Simple assembly line balancing problem under task deterioration.International Journal of Industrial Engineering Computations , 2(3), 583-592.

Refrences

Andre´s, C., Miralles, C., & Pastor, R. (2008). Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. European Journal of Operational Research, 187, 1212–1223.

Becker, C. & Scholl, A. (2006). A survey on problems and methods in generalized assembly line balancing. European Journal of Operational Research, 168, 694–715.

Browne, S. & Yechiali, U. (1990). Scheduling deteriorating jobs on a single processor. Operations Research, 38, 495–498.

Bryton, B. (1954). Balancing of a continuous production line. MS Thesis, Northwestern University, Evanston, Illinois.

Chen, R.-S., Lu, K.-Y., & Yu, S.-C. (2002). A hybrid genetic algorithm approach on multi-objective of assembly planning problem. Engineering Applications and Artificial. Intelligence, 15, 447–457.

Erel, E. & Sarin, S. C. (1998). A survey of the assembly line procedures. Production Planning & Control, 9 (5), 414–434.

Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Addision-Wesley, Reading, Massachusetts.

Gupta, J. N. D. & Gupta, S. K. (1988). Single facility scheduling with nonlinear processing times. Computers & Industrial Engineering, 14, 387–393.

Ji, M., & Cheng, T. C. E. (2009). Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan. European Journal of Operational Research, 202, 90-98.

Ji, M., & Cheng, T. C. E. (2008), Parallel-machine scheduling with simple linear deterioration to minimize total completion time. European Journal of Operational Research, 188, 342–347.

Kara, Y., Paksoy, T., & Chang, C.-T. (2009). Binary fuzzy goal programming approach to single model straight and U-shaped assembly line balancing. European Journal of Operational Research, 195(2), 335–347.

Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer applications, Eds R. E. Miller and J. W. Thatcher, 85–104, Plenum Press, New York.

Kim, Y. K., Song, W. S., & Kim, J. H. (2009). A mathematical model and a genetic algorithm for two-sided assembly line balancing. Computers & Operations Research, 36, 853–865.

Kunnathur, A. S. & Gupta, S. K. (1990). Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. European Journal of Operational Research, 47, 56–64.

Lapierre, S. D., Ruiz, A., & Soriano, P. (2006). Balancing assembly lines with tabu search. European Journal of Operational Research, 168, 826–837.

Levitin, G., Rubinovitz, J., & Shnits, B. (2006). A genetic algorithm for robotic assembly line balancing. European Journal of Operational Research, 168, 811–825.

Low, C., Hsu, C.-J., & Su, C.-T. (2008). Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration. Computational Mathematics & Applications, 56, 257–265.

Michalewicz, Z. (1996). Genetic algorithms + data structures evolution programs, 3rd edition, Springer, Berlin/Heidelberg, Germany.

Özcan, U., & Toklu, B. (2009). Multiple-criteria decision making in two-sided assembly line balancing: a goal programming and a fuzzy goal programming model. Computers & Operations Research, 36(6), 1955–1965.

Salveson, M. E. (1955). The assembly line balancing problem. Journal of Industrial Engineering, 6(3), 18–25.

Scholl, A., & Becker, C. (2006). State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research, 168, 666–693.

Sivanandam, S. N., & Deepa, S. N. (2008). Introduction to genetic algorithms, Springer, Berlin/Heidelberg/New York.

Toksari, M. D., Isleyen, S. K., Güner, E., & Baykoc, Ö. F. (2008), Simple and U-type assembly line balancing problems with a learning effect. Applied Mathematical Modeling, 32, 2954–2961.

Toksari, M.D., Isleyen, S. K.,Güner, E., & Bayko¸c, Ö. F. (2010). Assembly line balancing problem with deterioration tasks and learning effect. Expert Systems with Applications, 37(2), 1223–1228.

Wang, J.-B., Gao, W.-J., Wang, L.-Y., & Wang, D. (2009a). Single machine group scheduling with general linear deterioration to minimize the makespan. International Journal of Advanced Manufacturing Technology, 43, 146–150.

Wang, J.-B., Huang, X., Wang, X.-Y., Yin, N., & Wang, L.-Y. (2009b). Learning effect and deteriorating jobs in the single machine scheduling problems. Applied Mathematical Modeling, 33, 3848–3853.

Wang, J.-B., Wang, L.-Y., Wang, D., & Wang, X.-Y. (2009c). Single-machine scheduling with a time dependent deterioration. International Journal of Advanced Manufacturing Technology, 43(7–8), 805–809.

Yin, N., Wang, J.-B., Wang, D., Wang, L.-Y., & Wang, X.-Y. (2010). Deteriorating jobs and learning effects on a single-machine scheduling with past-sequence dependent setup times. International Journal of Advanced Manufacturing Technology, 46(5–8), 707–714.