The Preemptive Just-in-time Scheduling Problem in a Flow Shop Scheduling System

Journal of Optimization in Industrial Engineering

مقاله 7، دوره 12، شماره 2، مهر 2019، صفحه 79-92   

نوع مقاله: Original Manuscript

شناسه دیجیتال (DOI): 10.22094/joie.2017.499.11

نویسندگان

Javad Rezaeian^{* 1}؛ Sadegh Hosseini-Kia²؛ Iraj Mahdavi³

¹Department of industrial engineering, Mazandaran University of Science and Technology, Babol, Iran

²Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran.

³Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran

چکیده

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.

کلیدواژه‌ها

JIT scheduling؛ Flow shop؛ Preemption؛ Idle 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