A New model for integrated lot sizing and scheduling in flexible job shop problem

Document Type : Research Paper

Authors

Industrial Engineering, Shahed University

Abstract

In this paper an integrated lot-sizing and scheduling problem in a flexible job shop environment with machine-capacity-constraint is studied. The main objective is to minimize the total cost which includes the inventory costs, production costs and the costs of machine’s idle times. First, a new mixed integer programming model,with small bucket time approach,based onProportional Lot sizing and Scheduling Problems (PLSP), is proposed to formulate the problem. Since the problem under study is NP-hard, a modified harmony search algorithm, with a new built-in local search heuristic is proposed as solution technique.In this algorithm,it is improvised a New Harmony vector in two phases to enhance search ability.Additionally, Taguchi method is used to calibrate the parameters of the modified harmony search algorithm. Finally, comparative results demonstrate the effectiveness of the modified harmony search algorithm in solving the problem.It is also demonstrated that the proposed algorithm can find good quality solutions for all size problems. The objective values obtained by proposed algorithm are better from HS algorithm and exact method results.

Keywords

Main Subjects


Adetunji, O. A. B., &Yadavalli, V. (2012). An integrated utilisation, scheduling and lot-sizing algorithm for pull production.International Journal of Industrial Engineering: Theory, Applications and Practice, 19(3).
 
Akrami, B., Karimi, B., &Hosseini, S. M. (2006). Two metaheuristic methods for the common cycle economic lot sizing and scheduling in flexible flow shops with limited intermediate buffers: The finite horizon case. Applied Mathematics and Computation, 183(1), 634-645.
 
Almada-Lobo, B., & James, R. J. (2010). Neighbourhood search meta-heuristics for capacitated lot-sizing with sequence-dependent setups.International Journal of Production Research, 48(3), 861-878.
 
Beraldi, P., Ghiani, G., Grieco, A., &Guerriero, E. (2008). Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs.Computers & Operations Research, 35(11), 3644-3656.
 
Drexl, A., &Haase, K. (1995).Proportional lotsizing and scheduling.International Journal of Production Economics, 40(1), 73-87.
 
Fandel, G., &Stammen-Hegene, C. (2006).Simultaneous lot sizing and scheduling for multi-product multi-level production.International Journal of Production Economics, 104(2), 308-316.
 
Fattahi, P., Jolai, F., &Arkat, J. (2009).Flexible job shop scheduling with overlapping in operations.Applied Mathematical Modelling, 33(7), 3076-3087.
 
Fattahi, P., Mehrabad, M. S., &Jolai, F. (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of Intelligent Manufacturing, 18(3), 331-342.
 
Gao, K. Z., Suganthan, P. N., Pan, Q. K., Chua, T. J., Cai, T. X., & Chong, C. S. (2014). Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives.Journal of Intelligent Manufacturing, 1-12.
 
Geem, Z. W., Kim, J. H., &Loganathan, G. V. (2001). A new heuristic optimization algorithm: harmony search. Simulation, 76(2), 60-68.
 
Gómez Urrutia, E. D., Aggoune, R., &Dauzère-Pérès, S. (2014). Solving the integrated lot-sizing and job-shop scheduling problem.International Journal of Production Research, 52(17), 5236-5254.
 
Haase, K., &Kimms, A. (2000).Lot sizing and scheduling with sequence-dependent setup costs and times and efficient rescheduling opportunities.International Journal of Production Economics, 66(2), 159-169.
 
Kaczmarczyk, W. (2011).Proportional lot-sizing and scheduling problem with identical parallel machines.International Journal of Production Research, 49(9), 2605-2623.
 
Karimi, B., Ghomi, S. F., & Wilson, J. M. (2003). The capacitated lot sizing problem: a review of models and algorithms. Omega, 31(5), 365-378.
 
Karimi-Nasab, M., Seyedhoseini, S. M., Modarres, M., &Heidari, M. (2013). Multi-period lot sizing and job shop scheduling with compressible process times for multilevel product structures. International Journal of Production Research, 51(20), 6229-6246.
 
Kovács, A., Brown, K. N., &Tarim, S. A. (2009).An efficient MIP model for the capacitated lot-sizing and scheduling problem with sequence-dependent setups.International Journal of Production Economics, 118(1), 282-291.
 
Mahdieh, M., Bijari, M., & Clark, A. (2011).Simultaneous Lot Sizing and Scheduling in a Flexible Flow Line.Journal of Industrial and Systems Engineering, 5(2), 107-119.
 
Modrak, V. (2012). Alternative Constructive Heuristic Algorithm for Permutation Flow-Shop Scheduling Problem with Make-Span Criterion. International Journal of Industrial Engineering: Theory, Applications and Practice, 19(7).
 
Morais, M. D. F., GodinhoFilho, M., &Boiko, T. J. P. (2014). Hybrid flow shop scheduling problems involving setup considerations: a literature review and analysis. International Journal of Industrial Engineering: Theory, Applications and Practice, 20(11-12).
 
Petrovic, S., Fayad, C., Petrovic, D., Burke, E., & Kendall, G. (2008).Fuzzy job shop scheduling with lot-sizing.Annals of Operations Research, 159(1), 275-292.
 
Pinedo, M. L. (2012). Scheduling: theory, algorithms, and systems.Springer Science & Business Media.
 
Ponnambalam, S. G., & Reddy, M. (2003). A GA-SA multiobjective hybrid search algorithm for integrating lot sizing and sequencing in flow-line scheduling.The International Journal of Advanced Manufacturing Technology, 21(2), 126-137.
 
Ramezanian, R., &Saidi-Mehrabad, M. (2013). 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), 5134-5147.
 
Ramezanian, R., Saidi-Mehrabad, M., &Fattahi, P. (2013). MIP formulation and heuristics for multi-stage capacitated lot-sizing and scheduling problem with availability constraints. Journal of Manufacturing Systems, 32(2), 392-401.
 
Rohaninejad, M., Kheirkhah, A. S., VahediNouri, B., &Fattahi, P. (2015a). Two hybrid tabu search–firefly algorithms for the capacitated job shop scheduling problem with sequence-dependent setup cost. International Journal of Computer Integrated Manufacturing, 28(5), 470-487.
 
Rohaninejad, M., Kheirkhah, A., &Fattahi, P. (2015b). Simultaneous lot-sizing and scheduling in flexible job shop problems. The International Journal of Advanced Manufacturing Technology,78(1-4), 1-18.
 
Rohaninejad, M., Kheirkhah, A., Fattahi, P., &Vahedi-Nouri, B. (2015c).A hybrid multi-objective genetic algorithm based on the ELECTRE method for a capacitated flexible job shop scheduling problem.The International Journal of Advanced Manufacturing Technology, 77(1-4), 51-66.
 
Sikora, R., Chhajed, D., & Shaw, M. J. (1996).Integrating the lot-sizing and sequencing decisions for scheduling a capacitated flow line.Computers & Industrial Engineering, 30(4), 659-679.
 
Toledo, C. F. M., França, P. M., Morabito, R., &Kimms, A. (2009). Multi-population genetic algorithm to solve the synchronized and integrated two-level lot sizing and scheduling problem.International Journal of Production Research, 47(11), 3097-3119.
 
Wang, L., &Zheng, D. Z. (2001).An effective hybrid optimization strategy for job-shop scheduling problems.Computers & Operations Research, 28(6), 585-596.
 
Wang, L., Pan, Q. K., &Tasgetiren, M. F. (2010).Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms.Expert Systems with Applications, 37(12), 7929-7936.
 
Wang, L., Pan, Q. K., &Tasgetiren, M. F. (2011).A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem.Computers & Industrial Engineering, 61(1), 76-83.
 
Weidenhiller, A., &Jodlbauer, H. (2009). Equivalence classes of problem instances for a continuous-time lot sizing and scheduling problem. European Journal of Operational Research, 199(1), 139-149.
 
Wu, C. J., & Hamada, M. S. (2011). Experiments: planning, analysis, and optimization (Vol. 552). John Wiley & Sons.
 
Zhu, C. (2012). Applying Genetic Local Search Algorithm to Solve the Job-Shop Scheduling Problem.International Journal of Industrial Engineering: Theory, Applications and Practice, 19(9).