Lot-Sizing and Scheduling on Parallel Machine due to Earliness and Tardiness Cost

Document Type: Research Paper


Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran


In this research, lot-sizing and scheduling problem on parallel machines has been studied. Holding inventory and backlog cost has been considered as an earliness-tardiness penalties. A mixed integer programming formulation has been proposed based on TSP. Number of product batch is calculated as a parameter before solving the model. The computational result demonstrated that the MIP uses large CPU time to get result due to the problem complexity. So in the next step, problem has been modeled by constraint programming method that reduces solving time significantly. So that for an instance with 2 hours CPU solving time in MIP, the CP method reduces solving time to 2 minutes. To complete the solving process, a heuristic algorithm is proposed to assign orders to products. A case-study in steel-mill industry shows the efficiency of designed system rather than the existing system. Experimental results show that the proposed system have planned the orders less than 10 minutes solving time for different instances; while this is 1 to 2 hours for the existing system.


Main Subjects

1. Fleischmann, B., and Meyr, H. (1997). “The general lotsizing and scheduling problem”, ORSpectrum, Vol. 19, No.1?, PP. 11–21.
2. Almada-Lobo, B., Oliveira, J. F., and Carravilla, M.A. (2008). “A note on the capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times”, Computers & Operations Research, Vol. 35, No.4, PP. 1374–1376.
3. Gupta, D., and Magnusson, T. (2005). “The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times”, Computer & Operations Research, Vol. 32, No. 4, PP. 727–747.
4. Clark, A. R., and Clark, S. J. (2000). “Rolling-horizon lot-sizing when set-up times are sequence-dependent”, International Journal of Production Research, Vol. 38, No. 10, PP. 2287– 2307.
5. James, R. J. W., and Almada-Lobo, B. (2011). “Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics”, Computers & Operations Research, Vol. 38, No. 12, PP. 1816–1825.
6. Vaez, P., Bijari, M., and Moslehi, G. (2017). “Simultaneous Scheduling and Lot-Sizing with Earliness/Tardiness Penalties”, International Journal of Planning and Scheduling, in press.
7. Laborie, P., and Godard, D. (2007). “Self-adapting large neighborhood search: application to single-mode scheduling problems”, In Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications, Paris.
8. Baptiste, P., Laborie, P., Lepape, C., and Nuijten, W. (2006). “Constraint-based scheduling and planning”, In Handbook of constraint programming, Elsevier, PP. 761–799.
9. Zeballos, L., Quiroga, O., and Henning, G. (2010). “A constraint programming model for the scheduling of flexible manufacturing systems with machine and tool limitations”, Engineering Application of Artificial Intelligence, Vol. 23, No.2, PP. 229–248.
10. El Khayat, G. , Langevin, A., and Riopel, D. (2006). “Integrated production and material handling scheduling using mathematical programming and constraint programming”, European Journal of Operational Research, Vol. 175, No. 3, PP. 1818–1832.
11. Shaw, P. (1998). “Using constraint programming and local search methods to solve vehicle routing problems”, In Proceedings of the 3rd international conference on Principles and Practice of Constraint Programming,  Pisa, Italy, PP. 417–431.
12. Zhao, Z., and Li, X. (2014). “Scheduling elective surgeries with sequence-dependent setup times to multiple operating rooms using constraint programming”, Operations Research for Health Care, Vol. 3, No. 3, PP. 160–167.