Flexible flow shop scheduling problem to minimize makespan with renewable resources

Document Type : Article

Authors

Department of Industrial Engineering, Babol Noshirvani University of Technology, Babol, Iran

Abstract

This paper deals with a flexible flow shop (FFS) scheduling problem with unrelated parallel machines and renewable resource shared among the stages. The FFS scheduling problem is one of the most common manufacturing environment in which there is more than a machine in at least one production stage. In such a system, to decrease the processing times, additional renewable resources are assigned to the jobs or machines, and it can lead to decrease the total completion time. For this purpose, a mixed integer linear programming (MILP) model is proposed to minimize the maximum completion time (makespan) in an FFS environment. The proposed model is computationally intractable. Therefore, a particle swarm optimization (PSO) algorithm as well as a hybrid PSO and simulated annealing (SA) algorithm named SA-PSO, are developed to solve the model. Through numerical experiments on randomly generated test problems, the authors demonstrate that the hybrid SA-PSO algorithm outperforms the PSO, especially for large size test problems.

Keywords

Main Subjects

References

References:
1.    Su, L., and Lien, C. “Scheduling parallel machines with resource-dependent processing times”, Int. J. Prod. Res. 117, 256–266 (2009).
2.    Gholami, H.R., Mehdizadeh E., Naderi, B. “Mathematical models and an elephant herding optimization for multiprocessor-task flexible flow shop scheduling problems in the manufacturing resource planning (MRPII) system”. Sci. Iran. doi: 10.24200/SCI.2018.5552.1343 (2018).
3.    Ebrahimi, M., Fatemi Ghomi, S.M.T and Karimi, B. “Hybrid flow shop scheduling with sequence dependent family setup time and uncertain due dates”, Appl. Math. Model. 38, 2490-2540 (2014).
4.    Asadi-Gangraj, E. “Lagrangian relaxation approach to minimize makespan for hybrid flow shop scheduling problem with unrelated parallel machines”, Sci. Iran. 5, 3765-3775 (2018).
5.    Zabihzadeh, S.S., and Rezaeian, J. “Two meta-heuristic algorithms for flexible flow shop scheduling problem with robotic transportation and release time”, Appl. Soft. Comput. 30, 319-330 (2016).
6.    Karimi, N., Zandieh, M. and Karamooz, H.R. “Bi-objective group scheduling in hybrid flexible flowshop: a multi-phase approach”, Expert. Syst. Appl. 37, 4024-4032 (2010).
7.    Shahvari, O. and Logendran, R. “A comparison of two stage-based hybrid algorithms for a batch scheduling problem in hybrid flow shop with learning effect”, Int. J. Prod. Econ. 195, 27-248 (2018).
8.    Almedera, C. and Hartl, R.F. “A metaheuristic optimization approach for a real-world stochastic flexible flow shop problem with limited buffer”, Int. J. Prod. Econ. 145, 88-95 (2013). 
9.    Besbes, W., Teghem, J., and Loukil, T. “Scheduling hybrid flow shop problem with non-fixed availability constraints”, Eur. J. Ind. Eng. 4, 413-433 (2010).
10.    Sangsawang, C., Sethanan, K., Fujimoto, T., and Gen, M. “Metaheuristics optimization approaches for two-stage reentrant flexible flow shop with blocking constraint”, Expert. Syst. Appl. 42, 2395-2410 (2015).
11.    Jolai, F., Asefi, H., Rabiee, M. and Ramezani, P. “Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem”, Sci. Iran. 20, 861-872 (2013).
12.     Akrami, B., Karimi, B. and Moattar Hosseini, S.M. “Two metaheuristic methods for the common cycle economic lot sizing and scheduling in flexible flow shops with limited intermediate buffers: The finite horizon case”, Appl. Math. Comp. 183, 634-645 (2006).
13.    Marichelvam, M.K., Prabaharan, T. and Yang, X.S. “Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan”, Appl. Soft. Comput. 19, 93-101 (2014). 
14.    Choong, F.,  Phon-Amnuaisuk, S. and Alias, M.Y. “Metaheuristic methods in hybrid flow shop scheduling problem”, Expert. Syst. Appl. 38, 10787-10793 (2011).
15.    Chung, T., and Liao, C. “An immunoglobulin-based artificial immune system for solving the hybrid flow shop problem”, Appl. Soft. Comput. 13, 3729-3736 (2013).
16.    Dios, M., Fernandez-Viagas, V., and Framinan, J.M. “Efficient heuristics for the hybrid flow shop scheduling problem with missing operations. Comput. Ind. Eng. 115 (2018) 88-99. 
17.    Behnamian, J., and Fatemi Ghomi, S.M.T. “Hybrid flowshop scheduling with machine and resource-dependent processing times”, Appl. Math. Model. 35, 1107-1123 (2011).
18.    Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., and Werner, F.A. “Comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria”, Comput. Oper. Res. 36, 358–378 (2009).
19.    Edis, E.B., Oguz, C. “Parallel machine scheduling with flexible resources”, Comput. Ind. Eng. 63, 433–447 (2009).
20.    Yin, N., Kang, L., Sun, T., Yue, C., and Wang, X. “Unrelated parallel machines scheduling with deteriorating jobs and resource dependent processing times”, Appl. Math. Model. 38, 4747-4755 (2014).
21.    Figielska, E. “A new heuristic for scheduling the two-stage flowshop with additional resources”, Comput. Ind. Eng. 54, 750-763 (2008).
22.    Figielska, E. “Heuristic algorithms for preemptive scheduling in a two-stage hybrid flowshop with additional renewable resources at each stage” Comput. Ind. Eng. 59, 509-519 (2010).
23.    Figielska, E. “Linear programming & metaheuristic approach for scheduling in the hybrid flowshop with resource constraints”, Control. Cybern. 4, 1209-1230 (2011).
24.    Li, K., Shi, Y.,  Yang, S. and Cheng, B. “Parallel machine scheduling problem to minimize the makespan with resource dependent processing times”, Appl. Soft. Comput. 11, 5551-5557 (2011).
25.    Liu, Y., and Feng, Z. “Two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times”, Comput. Ind. Eng. 75, 170-175  (2014).
26.    Kellerer, H. “An approximation algorithm for identical parallel machine scheduling with resource dependent processing times”, Oper. Res. Lett. 36, 157-159 (2008).
27.    Jun, P., Xinbao, L., Baoyu, L., Pardalos, P.M., and Min, K. “Single-machine scheduling with learning effect and resource-dependent processing times in the serial-batching production”, Appl. Math. Model. 58, 245-253 (2018).
28.    Wang, X., and Wang, J. “Single-machine scheduling with convex resource dependent processing times and deteriorating jobs”, Appl. Math. Model.  37, 2388-2393 (2013).
29.    Wei, C., and Ji, P. “Single-machine scheduling with time-and-resource-dependent processing times”, Appl. Math. Model. 36, 792-798 (2012).
30.    Wang, D., Wang, M., and  Wang, J., “Single-machine scheduling with learning effect and resource-dependent processing times”, Comput. Ind. Eng. 59, 458-462 (2010).
31.    Wang, X., and Cheng, T.C.E. “Single machine scheduling with resource dependent release times and processing times”, Eur. J. Oper. Res. 162, 727-739 (2005).
32.    Nguyen, S., Thiruvady, D., Ernst, A.T., and Alahakoon, D. “A Hybrid Differential Evolution Algorithm with Column Generation forResource Constrained Job Scheduling”, Comput. Oper. Res. Doi: https://doi.org/10.1016/j.cor.2019.05.009 (2019).
33.    Gupta, J.N.D., Kruger, K., Lauff, V., Werner, F., and Sotskov, Y.N. “Heuristics for hybrid flow shops with controllable processing times and assignable due dates”, Comput. Oper. Res. 29 1417–1439 (2002).
34.    Kennedy, J., and Eberhart, R.C. “Particle swarm optimization”, Proceedings of the IEEE International Conference on Neural Networks, 4, 1942–1948 (1995).
35.    Poonthalir, G., Nadarajan, R. and Geetha, S. “Vehicle routing problem with limited refueling halts using particle swarm optimization with greedy mutation operator”, RAIRO-Oper. Res. 49, 689-716 (2015).
36.    Nayeri, S., Asadi-Gangraj, E., Emami, S. “Metaheuristic algorithms to allocate and schedule of the rescue units in the natural disaster with fatigue effect”. Neural Comput. Appl. Doi: https://doi.org/10.1007/s00521-018-3599-6 (2018).
37.    Bean, J.C. “Genetics and random keys for sequencing and optimization”, ORSA J. Comput. 6, 154–160 (1994).
38.    Poli, R. and Kennedy, J. and Blackwell, T. “Particle swarm optimization: an overview”, Swarm. Intell. 1, 33–57 (2007).
39.    Tadayon, B., and Salmasi, N. “A two-criteria objective function flexible flowshop scheduling problem with machine eligibility constraint”, Int. J. Adv. Manuf. Tech. 64, 1001-1015 (2013).
40.    Kirkpatric, S. and Gelatt, C.D., and Vecci, M.P. “Optimization by simulated annealing”, Sci. 220, 671–680 (1983).
41.    Asadi-Gangraj, E., and Nahavandi, N. “A metaheuristic approach for batch sizing and scheduling problem in flexible flow shop with unrelated parallel machines”, Int. J. Comp. App., 97, 31-36 (2014).
Scientia Iranica
Volume 28, Issue 3 - Serial Number 3
Transactions on Industrial Engineering (E)
May and June 2021
Pages 1853-1870

Files

History

  • Receive Date: 18 May 2019
  • Revise Date: 04 August 2019
  • Accept Date: 02 September 2019

Share

How to cite

Statistics