An improved model and a heuristic for capacitated lot sizing and scheduling in job shop problems

Document Type : Article

Authors

Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran

Abstract

This paper studies the problem of capacitated lot-sizing and scheduling in job shops with a carryover set-up and a general product structure. After analyzing the literature, the shortcomings are easily realized; for example, the available mathematical model is unfortunately not only non-linear but also incorrect. No lower bound and heuristic is developed for the problem. Therefore, we first develop a linear model for the problem on-hand. Then, we adapt an available lower bound in the literature to the problem studied here. Since the problem is NP-hard, a heuristics based on production shifting concept is also proposed. Numerical experiments are used to evaluate the proposed model and algorithm. The proposed heuristic is assessed by comparing it against other algorithms in the literature. The computational results demonstrate that our algorithm has an outstanding performance in solving the problem.

Keywords

Main Subjects


References
1. Guimar~aes, L., Klabjan, D., and Almada-Lobo, B.
\Modelling lotsizing and scheduling problems with
sequence dependent set-ups", European Journal of
Operational Research, 239(3), pp. 644-662 (2014).
2. Fandel, G. and Stammen-Hegene, C. \Simultaneous
lot sizing and scheduling for multi-product multilevel
production", International Journal of Production
Economic, 104(2), pp. 308-316 (2006).
3. Meyr, H. \Simultaneous lotsizing and scheduling by
combining local search with dual reoptimization",
European Journal of Operation Research, 120(2), pp.
311-326 (2000).
4. Karimi, B., Fatemi-Ghomi, S.M.T., and Wilson, J.
\The capacitated lot sizing problem: a review of
models and algorithms", Omega, 31, pp. 365-378
(2003).
5. Ouenniche, J. and Bertrand, J.W.M. \The nite
horizon economic lot sizing problem in job shops:
the multiple cycle approach", International Journal of
Production Economics, 74, pp. 49-61 (2001).
6. Ouenniche, J., Boctor, F.F., and Martel, A. \The
impact of sequencing decisions on multi-item lot sizing
and scheduling in
ow shops", International Journal
of Production Research, 10, pp. 2253-2270 (1999).
7. Maravelias, C.T. and Sung, C. \Integration of production
planning and scheduling: Overview, challenges
and opportunities", Computers and Chemical Engineering,
33, pp. 1919-1930 (2009).
8. Karimi-Nasab, M. and Seyedhoseini, S.M. \Multi-level
lot sizing and job shop scheduling with compressible
process times: A cutting plan approach", European
Journal of Operational Research, 231(3), pp. 598-616
(2013).
9. Stadtler, H. and Sahling, F. \A lot-sizing and scheduling
model for multi-stage
ow lines with zero lead
times", European Journal of Operational Research,
225, pp. 404-419 (2013).
10. Babaei, M., Mohammadi, M., and Fatemi-Ghomi,
S.M.T. \Lot sizing and scheduling in
ow shop with
sequence-dependent set-ups and backlogging", International
Journal of Computer Applications, 8, pp.
0975-8887 (2011).
11. Mohammadi, M., Fatemi-Ghomi, S.M.T., Karimi, B.,
and Torabi, S.A. \MIP-based heuristics for lotsizing in
capacitated pure
ow shop with sequence-dependent
set-ups", International Journal of Production Research,
10, pp. 2957-2973 (2010).
12. Clark, A.R. and Clark, S.J. \Rolling-horizon lot-sizing
when set-up times are sequence-dependent", International
Journal Production Research, 38(10), pp. 2287-
2308 (2000).
13. Mohammadi, M., Fatemi-Ghomi, S.M.T., Karimi, B.,
and Torabi, S.A. \Rolling-horizon and x-and-relax
O. Poursabzi et al./Scientia Iranica, Transactions E: Industrial Engineering 25 (2018) 3667{3684 3683
heuristics for the multi-product multi-level capacitated
lot sizing problem with sequence-dependent set-ups",
J. Int. Manuf., 21, pp. 501-510 (2010).
14. Mohammadi, M., Fatemi-Ghomi, S.M.T., and Jafari,
J. \A genetic algorithm for simultaneous lotsizing
and sequencing of the permutation
ow shops with
sequence-dependent set-ups", International Journal
of Computer Integrated Manufacturing, 1, pp. 87-93
(2011).
15. Mohammadi, M., Fatemi-Ghomi, S.M.T., Karimi, B.,
and Torabi, S.A. \MIP-based heuristics for lotsizing in
capacitated pure
ow shop with sequence-dependent
set-ups", International Journal of Production Research,
10, pp. 2957-2973 (2010).
16. Mohammadi, M. and Jafari, N. \A new mathematical
model for integrating lot sizing, loading, and scheduling
decisions in
exible
ow shops", International
Journal of Advanced Manufacturing Technology, 55,
pp. 709-721 (2011).
17. Ramezanian, R., Saidi-Mehrabad, M., and Teimoury,
E. \A mathematical model for integrating lot-sizing
and scheduling problem in capacitated
ow shop environments",
International Journal of Advanced Manufacturing
Technology, pp. 347-361 (2013).
18. Ramezanian, R. and Saidi-Mehrabad, M. \Hybrid simulated
annealing and MIP-based heuristics for stochastic
lot-sizing and scheduling problem in capacitated
multi-stage production system", Applied Mathematical
Modelling, 37(7), pp. 5134-5147 (2012).
19. Lasserre, J.B. \An integrated model for job-shop planning
and scheduling", Management Science, 38(8), pp.
1201-1211 (1992).
20. Dauzere-Peres, S. and Lasserre, J.B. \Integration of
lot sizing and scheduling decisions in a job-shop",
European Journal of Operational Research, 75, pp.
413-426 (1994).
21. Lalitha, J.L., Mohan, N., and Pillai, V.M. \Lot streaming
in [N 􀀀 1](1) + N(m) hybrid
ow shop", Journal
of Manufacturing Systems, 44, pp. 12-21 (2017).
22. Giglio, D., Paolucci, M., and Roshani, A. \Integrated
lot sizing and energy-ecient job shop scheduling
problem in manufacturing/remanufacturing systems",
Journal of Cleaner Production, 148, pp. 624-641
(2017).
23. Wolosewicza, C., Dauzere-Peresa, S., and Aggouneb,
R. \A Lagrangian heuristic for an integrated lot-sizing
and xed scheduling problem", European Journal of
Operational Research, 000, pp. 1-10 (2015).
24. Karimi-Nasab, M., Modarres, M., and Seyedhoseini,
S.M. \A self-adaptive PSO for joint lot sizing and
job shop scheduling with compressible process times",
Applied Soft Computing, 27, pp. 137-147 (2015).
25. Karimi-Nasab, M., Modarres, M., and Seyedhoseini,
S.M. \Lot sizing and job shop scheduling with compressible
process times: A cut and branch approach",
Computer and Industrial Engineering, 85, pp. 196-205
(2015).
26. Urrutia, E.D.G., Aggoune, R., and Dauzere-Peres,
S. \Solving the integrated lot-sizing and job-shop
scheduling problem", International Journal of Production
Research, 52(17), pp. 5236-5254 (2014). DOI:
10.1080/00207543.2014.902156
27. Mateus, G.R., Ravetti, M.G., de Souza, M.C., and
Valeriano, T.M. \Capacitated lot sizing and sequence
dependent set-up scheduling: an iterative approach for
integration", Journal of Scheduling, 13, pp. 245-259
(2010). DOI 10.1007/s10951-009-0156-2
28. Zhang, X.D. and Yan, H.S. \Integrated optimization
of production planning and scheduling for a kind of
job-shop", International Journal of Advanced Manufacturing
Technology, 26, pp. 876-886 (2005). DOI
10.1007/s00170-003-2042-y
29. Ouenniche, J. and Boctor, F. \Sequencing. Lot sizing
and scheduling of several products in job shop: the
common cycle approach", International Journal of
Production Research, 36(4), pp. 1125-1140 (1998).
30. Shim, I.S., Kim, H.C., Doh, H.H., and Lee, D.H. \A
two-stage heuristic for single machine capacitated lotsizing
and scheduling with sequence-dependent set-up
costs", Computers & Industrial Engineering, 61, pp.
920-929 (2011).
31. Afentakis, P. and Gavish, P. \Optimal lot-sizing algorithms
for complex product structures", Operation
Research, 34, pp. 237-249 (1986).
32. Franca, P.M., Armentano, V., Berretta, R.E., and
Clarc, A.R. \A heuristic method for lot-sizing in multistage
systems", Computers and Operations Research,
24(9), pp. 861-874 (1997).
33. Xie, J. and Dong, J. \Heuristic genetic algorithms
for general capacitated lot-sizing problem", Computer
and Mathematics with Applications, pp. 44263-44276
(2001).
34. Mohammadi, M. and Poursabzi, O. \A rolling horizonbased
heuristic to solve a multi-level general lot sizing
and scheduling problem with multiple machines
(MLGLSP MM) in job shop manufacturing system",
Uncertain Supply Chain Management, 2, pp. 167-178
(2014).