The Preemptive Just-in-time Scheduling Problem in a Flow Shop Scheduling System
الموضوعات :Javad Rezaeian 1 , Sadegh Hosseini-Kia 2 , Iraj Mahdavi 3
1 - Department of industrial engineering, Mazandaran University of Science and Technology, Babol, Iran
2 - Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran.
3 - Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran
الکلمات المفتاحية: Preemption, Flow shop, Idle time, JIT scheduling,
ملخص المقالة :
Flow shop scheduling problem has a wide application in the manufacturing and has attracted much attention in academic fields. From other point, on time delivery of products and services is a major necessity of companies’ todays; early and tardy delivery times will result additional cost such as holding or penalty costs. In this paper, just-in-time (JIT) flow shop scheduling problem with preemption and machine idle time assumptions is considered in which objective function is minimizing the sum of weighted earliness and tardiness. A new non-linear mathematical model is formulated for this problem and due to high complexity of the problem meta-heuristic approaches have been applied to solve the problem for finding optimal solution. The parameters of algorithms are set by Taguchi method. Each parameter is tested in three levels. By implementation of many problems with different sizes these levels are determined .The proposed model is solved by three meta-heuristic algorithms: genetic algorithm (GA), imperialist competitive algorithm (ICA) and hybrid of GA and ICA. To evaluate the performance of the proposed algorithms many test problems have been designed. The Computational results indicate the superiority of the performance of hybrid approach than GA and ICA in finding thebest solution in reasonable computational time.
Afshar nadjafi, B., & Shadrokh, S. (2010). The preemptive resource-constrained project scheduling problem subject to due dates and preemption penalties: An integer programming approach. Journal of Optimization in Industrial Engineering, Volume 1(Issue 1), 35-39.
Atashpaz-Gargari, E., & Lucas, C. (2007, 25-28 Sept. 2007). Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition. Paper presented at the 2007 IEEE Congress on Evolutionary Computation.
Baker, K. R., & Scudder, G. D. (1990). Sequencing with Earliness and Tardiness Penalties: A Review. Operations Research, 38(1), 22-36. doi:10.1287/opre.38.1.22
Behnamian, J., & Fatemi Ghomi, S. M. T. (2014). Multi-objective fuzzy multiprocessor flowshop scheduling. Applied Soft Computing, 21, 139-148. doi:http://dx.doi.org/10.1016/j.asoc.2014.03.031
Chandra, P., Mehta, P., & Tirupati, D. (2009). Permutation flow shop scheduling with earliness and tardiness penalties. International Journal of Production Research, 47(20), 5591-5610. doi:10.1080/00207540802124301
Ebadi, A., & Moslehi, G. (2012). Mathematical models for preemptive shop scheduling problems. Computers & Operations Research, 39(7), 1605-1614. doi:http://dx.doi.org/10.1016/j.cor.2011.09.013
Esteve, B., Aubijoux, C., Chartier, A., & T’kindt, V. (2006). A recovering beam search algorithm for the single machine Just-in-Time scheduling problem. European Journal of Operational Research, 172(3), 798-813. doi:http://dx.doi.org/10.1016/j.ejor.2004.11.014
Finke, D. A., Medeiros, D. J., & Traband, M. T. (2007). Multiple machine JIT scheduling: a tabu search approach. International Journal of Production Research, 45(21), 4899-4915. doi:10.1080/00207540600871228
Fu, Q., Sivakumar, A. I., & Li, K. (2012). Optimisation of flow-shop scheduling with batch processor and limited buffer. International Journal of Production Research, 50(8), 2267-2285. doi:10.1080/00207543.2011.565813
Gerstl, E., Mor, B., & Mosheiov, G. (2015). A note: Maximizing the weighted number of just-in-time jobs on a proportionate flowshop. Information Processing Letters, 115(2), 159-162. doi:http://dx.doi.org/10.1016/j.ipl.2014.09.004
Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning: Addison-Wesley, Reading, MA.
Hasanpour, j., ghodoosi, m., & hosseini, z. s. (2016). Optimizing a bi-objective preemptive multi-mode resource constrained project scheduling problem: NSGA-II and MOICA algorithms. Journal of Optimization in Industrial Engineering, 10(21), 79-92.
Hendel, Y., Runge, N., & Sourd, F. (2009). The one-machine just-in-time scheduling problem with preemption. Discrete Optimization, 6(1), 10-22. doi:http://dx.doi.org/10.1016/j.disopt.2008.08.001
Hendel, Y., & Sourd, F. (2006). Efficient neighborhood search for the one-machine earliness–tardiness scheduling problem. European Journal of Operational Research, 173(1), 108-119. doi:http://dx.doi.org/10.1016/j.ejor.2004.11.022
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems: University of Michigan Press.
Huynh Tuong, N., & Soukhal, A. (2010). Due dates assignment and JIT scheduling with equal-size jobs. European Journal of Operational Research, 205(2), 280-289. doi:http://dx.doi.org/10.1016/j.ejor.2010.01.016
Khorasanian, D., & Moslehi, G. (2017). Two-machine flow shop scheduling problem with blocking, multi-task flexibility of the first machine, and preemption. Computers & Operations Research, 79, 94-108. doi:http://dx.doi.org/10.1016/j.cor.2016.09.023
Khorshidian, H., Javadian, N., Zandieh, M., Rezaeian, J., & Rahmani, K. (2011). A genetic algorithm for JIT single machine scheduling with preemption and machine idle time. Expert Systems with Applications, 38(7), 7911-7918. doi:http://dx.doi.org/10.1016/j.eswa.2010.10.066
Koulamas, C. (1998a). On the complexity of two-machine flowshop problems with due date related objectives. European Journal of Operational Research, 106(1), 95-100. doi:http://dx.doi.org/10.1016/S0377-2217(98)00323-3
Koulamas, C. (1998b). A guaranteed accuracy shifting bottleneck algorithm for the two-machine flowshop total tardiness problem. Computers & Operations Research, 25(2), 83-89. doi:http://dx.doi.org/10.1016/S0305-0548(97)00028-2
Lann, A., & Mosheiov, G. (1996). Single machine scheduling to minimize the number of early and tardy jobs. Computers & Operations Research, 23(8), 769-781. doi:http://dx.doi.org/10.1016/0305-0548(95)00078-X
Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of Machine Scheduling Problems. In E. L. J. B. H. K. P.L. Hammer & G. L. Nemhauser (Eds.), Annals of Discrete Mathematics (Vol. Volume 1, pp. 343-362): Elsevier.
Liao, C.-J., & Cheng, C.-C. (2007). A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date. Computers & Industrial Engineering, 52(4), 404-413. doi:http://dx.doi.org/10.1016/j.cie.2007.01.004
Mehravaran, Y., & Logendran, R. (2012). Non-permutation flowshop scheduling in a supply chain with sequence-dependent setup times. International Journal of Production Economics, 135(2), 953-963. doi:http://dx.doi.org/10.1016/j.ijpe.2011.11.011
Najafi, E., Naderi, B., Sadeghi, H., & Yazdani, M. (2012). A Mathematical Model and a Solution Method for Hybrid Flow Shop Scheduling. Journal of Optimization in Industrial Engineering, 5(10), 65-72.
Nikjo, B., & Rezaeian, J. (2014). Meta heuristic for Minimizing Makespan in a Flow-line Manufacturing Cell with Sequence Dependent Family Setup Times. Journal of Optimization in Industrial Engineering, 7(16), 21-29.
Rezaeian, J., Seidgar, H., & Kiani, M. (2013). Scheduling of a flexible flow shop with multiprocessor task by a hybrid approach based on genetic and imperialist competitive algorithms. Journal of Optimization in Industrial Engineering, 6(13), 1-11.
Runge, N., & Sourd, F. (2009). A new model for the preemptive earliness–tardiness scheduling problem. Computers & Operations Research, 36(7), 2242-2249. doi:http://dx.doi.org/10.1016/j.cor.2008.08.018
Schaller, J. (2012). Scheduling a permutation flow shop with family setups to minimise total tardiness. International Journal of Production Research, 50(8), 2204-2217. doi:10.1080/00207543.2011.575094
Schaller, J., & Valente, J. M. S. (2013). A comparison of metaheuristic procedures to schedule jobs in a permutation flow shop to minimise total earliness and tardiness. International Journal of Production Research, 51(3), 772-779. doi:10.1080/00207543.2012.663945
Shabtay, D. (2012). The just-in-time scheduling problem in a flow-shop scheduling system. European Journal of Operational Research, 216(3), 521-532. doi:http://dx.doi.org/10.1016/j.ejor.2011.07.053
Shabtay, D., Bensoussan, Y., & Kaspi, M. (2012). A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system. International Journal of Production Economics, 136(1), 67-74. doi:http://dx.doi.org/10.1016/j.ijpe.2011.09.011
Sourd, F. (2005). Punctuality and idleness in just-in-time scheduling. European Journal of Operational Research, 167(3), 739-751. doi:http://dx.doi.org/10.1016/j.ejor.2004.07.018
Sun, D.-h., Song, X.-x., Zhao, M., & Zheng, L.-J. (2012). Research on a JIT scheduling problem in parallel motorcycle assembly lines considering actual situations. International Journal of Production Research, 50(18), 4923-4936. doi:10.1080/00207543.2011.616232
Tadayoni Rad, S., Gholami, S., Shafaei, R., & Seidgar, H. (2015). Bi-objective Optimization for Just in Time Scheduling: Application to the Two-Stage Assembly Flow Shop Problem. Journal of Quality Engineering and Production Optimization, 1(1), 21-32. doi:10.22070/jqepo.2015.186
Varmazyar, M., & Salmasi, N. (2012). Sequence-dependent flow shop scheduling problem minimising the number of tardy jobs. International Journal of Production Research, 50(20), 5843-5858. doi:10.1080/00207543.2011.632385
Ventura, J. A., & Radhakrishnan, S. (2003). Single machine scheduling with symmetric earliness and tardiness penalties. European Journal of Operational Research, 144(3), 598-612. doi:http://dx.doi.org/10.1016/S0377-2217(02)00163-7
Zegordi, S. H., Itoh, K., & Enkawa, T. (1995). A knowledgeable simulated annealing scheme for the early/tardy flow shop scheduling problem. International Journal of Production Research, 33(5), 1449-1466. doi:10.1080/00207549508930220
