Volume 2 Issue 3 pp. 617-630 Summer, 2011


Multi-objective group scheduling with learning effect in the cellular manufacturing system


Mohammad Taghi Taghavi-fard, Hassan Javanshir, Mohammad Ali Roueintan and Ehsan Soleimany


Group scheduling problem in cellular manufacturing systems consists of two major steps. Sequence of parts in each part-family and the sequence of part-family to enter the cell to be processed. This paper presents a new method for group scheduling problems in flow shop systems where it minimizes makespan (Cmax) and total tardiness. In this paper, a position-based learning model in cellular manufacturing system is utilized where processing time for each part-family depends on the entrance sequence of that part. The problem of group scheduling is modeled by minimizing two objectives of position-based learning effect as well as the assumption of setup time depending on the sequence of parts-family. Since the proposed problem is NP-hard, two meta heuristic algorithms are presented based on genetic algorithm, namely: Non-dominated sorting genetic algorithm (NSGA-II) and non-dominated rank genetic algorithm (NRGA). The algorithms are tested using randomly generated problems. The results include a set of Pareto solutions and three different evaluation criteria are used to compare the results. The results indicate that the proposed algorithms are quite efficient to solve the problem in a short computational time.


DOI: 10.5267/j.ijiec.2011.02.002

Keywords: Cellular manufacturing system, Group scheduling, Multi-objective optimization, Learning effect Multi-objective genetic algorithm
References

Al Jadaan, O., Rajamani, L., & Rao, C. R. (2008a). Non-dominated ranked genetic algorithm for solving multi-objective optimization problems: NRGA. Journal of Theoretical and Applied Information Technology, 4 (1), 60-67.

Al Jadaan, O., Rao, C. R., & Rajamani, L., (2008b). Improved selection operator GA. Journal of Theoretical and Applied Information Technology, 2, 269-277.

Biskup, D., (2008). A State-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188(2), 315-329.

Biskup, D., (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115, 173-178.

Chen, P., Wu, C.-C., & Lee, W.-C., (2006). A bi-Criteria two-machine flow shop scheduling Problem with a learning effect. Journal of the Operational Research Society, 57, 1113-1125.

Ghosh,T., Sengupta, S., Chattopadhyay, M. & Dan, P. K. (2011). Meta-heuristics in cellular manufacturing: A state-of-the-art review. International Journal of Industrial Engineering Computations, 2(1), 87-122.

Deb, K., Agrawal, S., Pratap, A., & Meyarivan, T., (2000). A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In Proceedings of the Parallel Problem Solving from Nature VI Conference, 849–858.

Dejong, J. R., (1957). The effects of increasing skill on cycle time and its consequences for time

standards, Ergonomics, 1, 51-60.

Eren, T., & Guner, E., (2007). Minimizing total tardiness in a scheduling problem with a learning effect. Applied Mathematical Modelling, 31, 1351-1361.

Eren, T. (2009). A bicriteria parallel machine scheduling with a learning effect of setup and removal times. Applied Mathematical Modelling, 33, 1141–1150.

Kuo, W., & Yang, D. (2007). Single-machine scheduling with past-sequence-dependent setup times and learning effects, Information Processing Letters, 102, 22-26.

Koulamas, C., & Kyparisis, G. J., (2007). Single-Machine and two-machine flow shop scheduling with general learning function. European Journal of Operational Research, 178, 402-407.

Lee W.-C, & Wu C.-C, (2004). Minimizing total completion time in a two-machine flow shop with a learning effect. International Journal of Production Economics, 88, 85-93.

Lee, W.-C, Wu, C.-C, & Sung, H.-J, (2004). A bi-criterion single-machine scheduling problem with learning considerations. Acta Informatics, 40, 303-315.

Lee, W-C., & Wu, C.-C. (2009). A note on single-machine group scheduling problems with position-based learning effect. Applied Mathematical Modelling. 33(4), 2159-2163.

Logendran, R., Salmasi, N., & Sriskandarajah, C., (2006).Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups. Computers & Operations Research, 33, 158-180.

Mosheiov, G., (2001a). Scheduling problems with a learning effect. European Journal of Operational Research, 132, 687-693.

Mosheiov, G., (2001b). Parallel machine scheduling with a learning effect. Journal of the Operational Research Society, 52, 1-5.

Nanda, R., & Alder, G. L., (1982). Learning curves: theory and application, Atlanta: Industrial Engineering & Management Press.

Schaller, J.E., Gupta, J.N.D., & Vakharia, A.J., (2000). Scheduling a flow line manufacturing cell with sequence dependent family setup times. European Journal of Operational Research, 125(2), 324-339.

Wang, J., & Xia, Z., (2005). Flow-shop scheduling with a learning effect. Journal of the Operational Research Society, 56(4), 1325-1330.

Wu, C-C., & Lee, W-C., (2009). Single-machine and flow shop scheduling with a general learning effect model. Computers & Industrial Engineering, 56(4), 1553-1558.

Zegordi, S.H., Itoh, K., & Enkawa, T., (1995). A knowledge simulated annealing scheme for the early/tardy flow shop scheduling problem. International Journal of Production Research, 33(5), 1449-1466.

Zitzler, E., & Thiele, L., (1999). Multi objective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 4(3), 257-271.

Zitzler, E., Deb, K., & Thiele, L., (2000). Comparison of multi objective evolutionary algorithms. Evolutionary Computation journal. 8(2), 125-148.

Zhao, C.-L., Zhang, Q.-L., & Tang, H.-Y. (2004). Machine scheduling problems with learning effects. Dynamics of Continuous, discrete and Impulsive Systems, Series A: Mathematical Analysis, 11, 741-750.