A New Mathematical Model for Simultaneous Lot-sizing and Production Scheduling Problems Considering Earliness/Tardiness Penalties and Setup Costs

Document Type : Research Paper

Author

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

Abstract

This paper investigated the problem of simultaneous determination of lot-sizing and production scheduling with earliness/tardiness penalties. In this problem, decisions about lot-sizing and scheduling are made so that the sum of holding, tardiness, and setup costs is minimized. There are n orders waiting to be processed on a machine. Each order has its own due date as well as tardiness and earliness cost being the same as holding cost .Each order is delivered only once. If the production is completed before or on the due date, delivery will be on the due date. Otherwise, the order will be delivered immediately after its production is completed. In spite of its wide applications, this problem has not yet been reported in the literature. A mathematical model was presented as solution methods for the problem. Two meta-heuristics, namely, Simulated Annealing and Ant Colony System meta-heuristic algorithms are presented for solving the problem. Also, lower bounds are obtained from solving the problem relaxation, and they are compared with the optimal solutions to estimate the goodness of two meta-heuristic algorithms. They are difficult benchmarks, widely used to measure the efficiency of metaheuristics with respect to both the quality of the solutions and the central. The results show that the Simulated Annealing recorded a lower solution time and average percentage deviation than did the Ant Colony System algorithm. The presented SA is capable to solve large instances that are mostly compatible with the real-world problems.

Keywords

Main Subjects


Almada-Lobo, Bernardo, and Ross J. W. James. (2010). Neighbourhood search meta-heuristics for capacitated lot-sizing with sequence-dependent setups. International Journal of Production Research. Vol. 48 (3), pp. 861-878.
Almada-Lobo, Bernardo, Diego Klabjan, Maria Antóniacarravilla, and José F. Oliveira. (2007). Single machine multi-product capacitated lot-sizing with sequence-dependent setups. International Journal of Production Research. Vol. 45 (20), pp.4873-4894.
Almada-Lobo, Bernardo, José F. Oliveira, and Maria Antóniacarravilla. (2008). A note on '' the capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times. Computers & Operations Research, Vol. 35 (4), pp. 1374-1376.
Almeder, Christian. (2010). A hybrid optimization approach for multi-level capacitated lot-sizing problems. European Journal of Operational Research, Vol. 200 (2), pp. 599-606.
Clark, Alistair R., and Simon J. Clark. (2000). Rolling-horizon lot-sizing when set-up times are sequence-dependent. International Journal of Production Research, Vol. 38 (10), pp. 2287-2307.
Dorigo, Marco, and Thomas Stutzle. (2004). Ant colony Optimization: MIT Press,Cambridge.
Fleischmann, Bernhard, and Herbert Meyr. (1997). the general lot-sizing and scheduling problem.OR Spectrum, Vol. 19, pp. 11-21.
Gupta, Diwakar, and Thorkell Magnusson. (2005). The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times. Computers & Operations Research, Vol. 32 (4), pp. 727-747.
Hall, Nicholas G., WieslawKubiak, and Suresh P. Sethi. (1991). Earliness-tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date. Operations Research, Vol. 39 (5), pp. 847-856.
James, Ross J. W., and Bernardo Almada-Lobo. (2011). Single and parallel machine capacitated lot-sizing and scheduling: New iterative MIP-based neighborhood search heuristics. Computers & Operations Research, Vol. 38 (12), pp.1816-1825.
Luis, Guimarães, Diego Klabjan, and Almada-Lobo Bernardo. (2014). Modeling lotsizing and scheduling problems with sequence dependent setups. European Journal of Operational Research, pp. 644-662. (DOI: 10.1016/j.ejor.2014.05.018)
Liu, Cheng-Hsiang. (2016). Discrete lot-sizing and scheduling problems considering renewable energy and CO2 emissions. Production Engineering, Vol. 10(6), pp. 607-614.
Mahdieh, Masoumeh, Mehdi Bijari, and Alistair Clark. (2011). Simultaneous Lot-Sizing and Scheduling in a Flexible Flow Line. Journal of Industrial and Systems Engineering, Vol. 5 (2), pp.107-119.
Mehdizadeh, E., Hajipour, V. and Mohammadizadeh, M. R. (2015). A bi-objective multi-item capacitated lot-sizing model: Two Pareto-based meta-heuristic algorithms. International Journal of Management Science and Engineering Management, pp. 1-15. (DOI: 10.1080/17509653.2015.1086965)
Mirabi, Mohammad. (2011). A hybrid simulated annealing for the single-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times and costs and dynamic release of jobs. The International Journal of Advanced Manufacturing Technology, Vol. 54 (9-12), pp. 1109-1119.
Mohammadi, Mohammad. (2010). Integrating lot-sizing, loading, and scheduling decisions in flexible flow shops. The International Journal of Advanced Manufacturing Technology, Vol. 50 (9-12), pp.1165-1174.
Mohammadi, Mohammad, and NiloofarJafari. (2011). A new mathematical model for integrating lot-sizing, loading, and scheduling decisions in flexible flow shops. The International Journal of Advanced Manufacturing Technology, Vol. 55 (5-8), pp.709-721.
Monden, Yasuhiro. (1998). Toyota production System: An Integrated Approach to Just-In-Time. Fourth ed. Norcross: Productivity Press.
Seeanner, F., Bernardo Almada-Lobo, and H. Meyr. (2013). Combining the principles of variable neighbourhood decomposition search and the fix & optimize heuristic to solve multi-level lot-sizing and scheduling problems. Computers & Operations Research, Vol. 40 (1), pp. 303-317.
Seeanner, Florian, and Herbert Meyr. (2013). Multi-stage simultaneous lot-sizing and scheduling for flow line production. OR Spectrum, Vol. 35 (1), pp. 33-73.
Sereshti, Narges, and Mehdi Bijari. (2013). Profit maximization in simultaneous lot-sizing and scheduling problem." Applied Mathematical Modelling, Vol. 37 (23), pp. 9516-9523.
Supithak, Wisut, Surya D. Liman, and Elliot J. Montes. (2010). Lot-sizing and scheduling problem with earliness tardiness and setup penalties. Computers & Industrial Engineering, Vol. 58 (3), pp. 363-372.
Tukey, John Wilder. (1977). Exploratory Data Analysis: Addison-Wesley,Boston.
Wang, D., Grunder, O. and Moudni, A. E. (2014). Using genetic algorithm for lot sizing and scheduling problem with arbitrary job volumes and distinct job due date considerations. International Journal of Systems Science, Vol. 45(8), pp. 1694-1707.