Modeling and Solving of a Bi-Criteria Scheduling Problem for a Cellular Manufacturing System with Sequence-Dependent Cell Setup Times

Document Type : Research Article

Authors

Abstract

This paper presents a new, bi-criteria mixed-integer programming model for scheduling cells (part families) and parts within each cell in a manufacturing cellular system. The objective of this model is to minimize the makespan and inter-cell movements simultaneously, while considering sequence-dependent cell setup times. In the CMS design and planning, three main steps must be considered, namely cell formation (i.e., part families and machine grouping), inter and intra-cell layouts, and scheduling issue. Due to the NP-hardness of the proposed model and the scheduling problem in the CMS, a genetic algorithm (GA) as an efficient meta-heuristic method is proposed to solve such a hard problem. Finally, a number of test problems are solved to show the efficiency of the proposed GA and the related computational results are compared with the results obtained by the use of an optimization tool.

Keywords

References

[1] Soleymanpour, M., Vrat, P., Shankar, R., "A transiently chaotic neural network approach to the design of cellular manufacturing", International Journal of Production Research, Vol. 40 (10), p.p. 2225–2244, 2002.
[2] Yoshida, T., Hitomi, K., "Optimal two-stage production scheduling with setup times separated", AIIE Transactions, Vol. 11, p.p. 261–263, 1979.
[3] Sekiguchi, Y., "Optimal schedule in a GT-type flow-shop under series-parallel precedence constraints", Journal of the Operations Research Society of Japan, Vol. 26, p.p. 226–251, 1983.
[4] Baker, K.R., "Scheduling groups of jobs in the two machine flow shop", Mathematical and Computer Modeling, Vol. 13, p.p. 29-36, 1990.
[5] Yang, D.L., Chern, M..S., "Two-machine flow shop group scheduling problem", Computers & Operations Research, Vol. 27, p.p. 975–985, 2000.
[6] Hitomi, K., Ham, I., "Operations scheduling for group technology applications", Annals of the CIRP, Vol. 25 (1), p.p. 419–422, 1976.
[7] Logendran, R., Sriskandarajah, C., "Two-machine group scheduling problem with blocking and anticipatory setups", European Journal of Operational Research, Vol. 69 (3), p.p., 467–481., 1993.
[8] Logendran, R., Nudtasomboon, N., "Minimizing the makespan of a group scheduling problem: A new heuristic", International Journal of Production Economics, Vol. 22, p.p. 217–230, 1991.
[9] Nawaz, M., Enscore, J.E.E., Ham, I., "A heuristic algorithm for the m-machine, n-job flow shop sequencing problem", OMEGA: International Journal of Management Science, Vol. 11 (1), p.p. 91–95., 1983.
[10] Wemmerl. ov, U., Vakharia, A.J., "Job and family scheduling of a flow-line manufacturing cell: A simulation study", IIE Transactions, Vol. 23 (4), p.p. 383–393, 1991.
[11] Mahmoodi, F., Dooley, K.J., "Group scheduling and order releasing: Review and foundations for research", Production Planning & Control, Vol. 3 (1), p.p. 70–80, 1992.
[12] Eom, D.H., Shin, H.J., Kwun, I.H., Shim, J.K., Kim, S.S., "Scheduling jobs on parallel machines with sequence-dependent family setup times". Advanced Manufacturing Technology, Vol. 19, p.p. 926–932, 2002.
[13] Logendran, R., Mai, L., Talkington, D., "Combined heuristics for bi-level group scheduling problems", International Journal of Production Economics, Vol. 38, p.p. 133–145, 1995.
[14] Campbell, H.G., Dudek, R.A., Smith, M.L., "A heuristic algorithm for the n job, m machine sequencing problem", Management Science, Vol. 16, p.p. 630-637. 1970.
[15] Yang, W. H., Liao, C. J., "Group scheduling on two cells with inter-cell movement", Computers & Operations Research, Vol. 23 (10), p.p. 997–1006, 1996.
[16] Schaller, J., "A new lower bound for the flow shop group scheduling problem", Computers & Industrial Engineering, Vol. 41, p.p. 151–161, 2001.
[17] Schaller, J.E., Gupta, J.N.D., Vakharia, A.J., "Scheduling a flowline manufacturing cell with sequence dependent family setup times". European Journal of Operational Research, Vol. 125, p.p. 324–339, 2000.
[18] Franca, P.M., Gupta, J.N.D., Mendes, A.S., Moscato, P., Veltink, K.J., "Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups". Computers & Industrial Engineering, Vol. 48 (3), p.p. 491–506, 2005.
[19] Hendizadeh, S.H., Faramarzi, H., Mansouri, S.A., "Meta-heuristics for scheduling a flowline manufacturing cell with sequence dependent family setup times". International Journal of Production Economics, Vol. 111 (2), p.p. 593-605, 2008.
[20] Tavakkoli-Moghaddam, R., Gholipour-Kanani, Y., Cheraghalizadeh, R., "A genetic algorithm and memetic algorithm to sequencing and scheduling of cellular manufacturing systems", International Journal of Management Science and Engineering Management, Vol. 3 (2), pp. 119-130, 2008.
[21] Holland, J.; Adaptation natural and artificial systems, University of Michigan press, An Arbor, MI, MIT Press, Cambridge, Ma, 1975.
[22] Gen, M., Cheng, R.; Genetic algorithms & engineering design, New York, A Wiley Interscience Publication, 1997.

Files

Share

How to cite

Statistics