Processing, Please wait...

  • Home
  • About Us
  • Search:
  • Advanced Search

Growing Science » Journal of Project Management » Solving blocking flowshop scheduling problem with makespan criterion using q-learning-based iterated greedy algorithms

Journals

  • IJIEC (726)
  • MSL (2637)
  • DSL (649)
  • CCL (495)
  • USCM (1092)
  • ESM (404)
  • AC (557)
  • JPM (247)
  • IJDS (912)
  • JFS (91)
  • HE (21)

JPM Volumes

    • Volume 1 (8)
      • Issue 1 (5)
      • Issue 2 (3)
    • Volume 2 (13)
      • Issue 1 (4)
      • Issue 2 (3)
      • Issue 3 (3)
      • Issue 4 (3)
    • Volume 3 (17)
      • Issue 1 (4)
      • Issue 2 (5)
      • Issue 3 (4)
      • Issue 4 (4)
    • Volume 4 (24)
      • Issue 1 (4)
      • Issue 2 (8)
      • Issue 3 (8)
      • Issue 4 (4)
    • Volume 5 (20)
      • Issue 1 (5)
      • Issue 2 (5)
      • Issue 3 (5)
      • Issue 4 (5)
    • Volume 6 (20)
      • Issue 1 (5)
      • Issue 2 (5)
      • Issue 3 (5)
      • Issue 4 (5)
    • Volume 7 (21)
      • Issue 1 (5)
      • Issue 2 (5)
      • Issue 3 (5)
      • Issue 4 (6)
    • Volume 8 (21)
      • Issue 1 (6)
      • Issue 2 (5)
      • Issue 3 (5)
      • Issue 4 (5)
    • Volume 9 (35)
      • Issue 1 (6)
      • Issue 2 (5)
      • Issue 3 (9)
      • Issue 4 (15)
    • Volume 10 (68)
      • Issue 1 (15)
      • Issue 2 (21)
      • Issue 3 (13)
      • Issue 4 (19)

Keywords

Jordan(161)
Supply chain management(160)
Vietnam(148)
Customer satisfaction(120)
Performance(113)
Supply chain(108)
Service quality(98)
Tehran Stock Exchange(94)
Competitive advantage(93)
SMEs(86)
optimization(84)
Financial performance(83)
Trust(81)
Job satisfaction(79)
Social media(78)
Factor analysis(78)
TOPSIS(78)
Knowledge Management(77)
Genetic Algorithm(76)
Sustainability(76)


» Show all keywords

Authors

Naser Azad(82)
Mohammad Reza Iravani(64)
Zeplin Jiwa Husada Tarigan(59)
Endri Endri(45)
Muhammad Alshurideh(42)
Hotlan Siagian(39)
Jumadil Saputra(36)
Muhammad Turki Alshurideh(35)
Dmaithan Almajali(35)
Barween Al Kurdi(32)
Basrowi Basrowi(31)
Hassan Ghodrati(31)
Ahmad Makui(31)
Mohammad Khodaei Valahzaghard(30)
Shankar Chakraborty(29)
Ni Nyoman Kerti Yasa(29)
Sulieman Ibraheem Shelash Al-Hawary(28)
Prasadja Ricardianto(28)
Sautma Ronni Basana(27)
Haitham M. Alzoubi(27)


» Show all authors

Countries

Iran(2162)
Indonesia(1276)
Jordan(783)
India(779)
Vietnam(500)
Saudi Arabia(438)
Malaysia(438)
United Arab Emirates(220)
China(181)
Thailand(151)
United States(109)
Turkey(102)
Ukraine(99)
Egypt(95)
Canada(89)
Pakistan(84)
Peru(83)
United Kingdom(77)
Nigeria(77)
Morocco(73)


» Show all countries

Journal of Project Management

ISSN 2371-8374 (Online) - ISSN 2371-8366 (Print)
Quarterly Publication
Volume 9 Issue 2 pp. 85-100 , 2024

Solving blocking flowshop scheduling problem with makespan criterion using q-learning-based iterated greedy algorithms Pages 85-100 Right click to download the paper Download PDF

Authors: M. Fatih Tasgetiren, Damla Kizilay, Levent Kandiller

DOI: 10.5267/j.jpm.2024.2.002

Keywords: Q-learning-based iterated greedy algorithms, Reinforcement learning, Blocking flowshop scheduling problem

Abstract: This study proposes Q-learning-based iterated greedy (IGQ) algorithms to solve the blocking flowshop scheduling problem with the makespan criterion. Q learning is a model-free machine intelligence technique, which is adapted into the traditional iterated greedy (IG) algorithm to determine its parameters, mainly, the destruction size and temperature scale factor, adaptively during the search process. Besides IGQ algorithms, two different mathematical modeling techniques. One of these techniques is the constraint programming (CP) model, which is known to work well with scheduling problems. The other technique is the mixed integer linear programming (MILP) model, which provides the mathematical definition of the problem. The introduction of these mathematical models supports the validation of IGQ algorithms and provides a comparison between different exact solution methodologies. To measure and compare the performance of IGQ algorithms and mathematical models, extensive computational experiments have been performed on both small and large VRF benchmarks available in the literature. Computational results and statistical analyses indicate that IGQ algorithms generate substantially better results when compared to non-learning IG algorithms.

How to cite this paper
Tasgetiren, M., Kizilay, D & Kandiller, L. (2024). Solving blocking flowshop scheduling problem with makespan criterion using q-learning-based iterated greedy algorithms.Journal of Project Management, 9(2), 85-100.

Refrences
Aqil, S., & Allali, K. (2021). Two efficient nature inspired meta-heuristics solving blocking hybrid flow shop manufacturing problem. Engineering Applications of Artificial Intelligence, 100, 104196. https://doi.org/10.1016/j.engappai.2021.104196
Birgin, E. G., Ferreira, J. E., & Ronconi, D. P. (2020). A filtered beam search method for the m-machine permutation flowshop scheduling problem minimizing the earliness and tardiness penalties and the waiting time of the jobs. Computers and Operations Research, 114, 104824. https://doi.org/10.1016/j.cor.2019.104824
Blazewicz, J., H. Ecker, K., Pesch, E., Schmidt, G., & Wȩglarz, J. (2007). Handbook on scheduling. From theory to applications. International Handbook on Information Systems. https://doi.org/10.1007/978-3-540-32220-7
Caraffa, V., Ianes, S., P. Bagchi, T., & Sriskandarajah, C. (2001). Minimizing makespan in a blocking flowshop using genetic algorithms. International Journal of Production Economics, 70(2), 101–115. https://doi.org/10.1016/S0925-5273(99)00104-8
Carlier, J., Haouari, M., Kharbeche, M., & Moukrim, A. (2010). An optimization-based heuristic for the robotic cell problem. European Journal of Operational Research, 202(3), 636–645. https://doi.org/10.1016/j.ejor.2009.06.035
Chen, H., Zhou, S., Li, X., & Xu, R. (2014). A hybrid differential evolution algorithm for a two-stage flow shop on batch processing machines with arbitrary release times and blocking. International Journal of Production Research, 52(19), 5714–5734. https://doi.org/10.1080/00207543.2014.910625
Cheng, C.-Y., Ying, K.-C., Chen, H.-H., & Lu, H.-S. (2019). Minimising makespan in distributed mixed no-idle flowshops. International Journal of Production Research, 57(1), 48–60. https://doi.org/10.1080/00207543.2018.1457812
Dubois-Lacoste, J., Pagnozzi, F., & Stützle, T. (2017). An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem. Computers & Operations Research, 81, 160–166. https://doi.org/10.1016/J.COR.2016.12.021
Elmi, A., & Topaloglu, S. (2013). A scheduling problem in blocking hybrid flow shop robotic cells with multiple robots. Computers and Operations Research, 40(10), 2543–2555. https://doi.org/10.1016/j.cor.2013.01.024
Fernandez-Viagas, V., Ruiz, R., & Framinan, J. M. (2017). A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation. European Journal of Operational Research, 257(3), 707–721. https://doi.org/10.1016/J.EJOR.2016.09.055
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The Complexity of Flowshop and Jobshop Scheduling. Math. Oper. Res., 1(2), 117–129. https://doi.org/10.1287/moor.1.2.117
Gilmore, P. C., Lawler, E. L., & Shmoys, D. B. (1984). Well-solved Special Cases of the Traveling Salesman Problem. University of California at Berkeley.
Glover, F. (1990). Tabu search—part II. ORSA Journal on Computing, 2, 4–32. https://doi.org/10.1287/ijoc.2.1.4
Gong, D., Han, Y., & Sun, J. (2018). A novel hybrid multi-objective artificial bee colony algorithm for blocking lot-streaming flow shop scheduling problems. Knowledge-Based Systems, 148, 115–130. https://doi.org/10.1016/j.knosys.2018.02.029
Gong, H., Tang, L., & Duin, C. W. (2010). A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times. Computers and Operations Research, 37(5), 960–969. https://doi.org/10.1016/j.cor.2009.08.001
Hall, N. G., & Sriskandarajah, C. (1996). A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process. Oper. Res., 44(3), 510–525. https://doi.org/10.1287/opre.44.3.510
Han, Y.-Y., Gong, D., & Sun, X. (2015). A discrete artificial bee colony algorithm incorporating differential evolution for the flow-shop scheduling problem with blocking. Engineering Optimization, 47(7), 927–946. https://doi.org/10.1080/0305215X.2014.928817
Han, Y.-Y., Liang, J. J., Pan, Q.-K., Li, J.-Q., Sang, H.-Y., & Cao, N. N. (2013). Effective hybrid discrete artificial bee colony algorithms for the total flowtime minimization in the blocking flowshop problem. The International Journal of Advanced Manufacturing Technology, 67(1), 397–414. https://doi.org/10.1007/s00170-012-4493-5
Han, Y.-Y., Pan, Q.-K., Li, J.-Q., & Sang, H. (2012). An improved artificial bee colony algorithm for the blocking flowshop scheduling problem. The International Journal of Advanced Manufacturing Technology, 60(9), 1149–1159. https://doi.org/10.1007/s00170-011-3680-0
Han, Y., Gong, D., Li, J., & Zhang, Y. (2016). Solving the blocking flow shop scheduling problem with makespan using a modified fruit fly optimisation algorithm. International Journal of Production Research, 54(22), 6782–6797. https://doi.org/10.1080/00207543.2016.1177671
Han, Y., Li, J., Sang, H., Liu, Y., Gao, K., & Pan, Q. (2020). Discrete evolutionary multi-objective optimization for energy-efficient blocking flow shop scheduling with setup time. Applied Soft Computing Journal, 93, 106343. https://doi.org/10.1016/j.asoc.2020.106343
Johnson, S. M. (1954). Optimal Two and Three Stage Production Schedules With Set-Up Time Included. Naval Research Logistics Quarterly, 1, 61–68. https://doi.org/10.1002/nav.3800010110
Kaelbling, L. P., Littman, M. L., & Moore, A. W. (1996). Reinforcement Learning: A Survey. J. Artif. Int. Res., 4(1), 237–285.
Karimi-Mamaghan, M., Mohammadi, M., Pasdeloup, B., & Meyer, P. (2022). Learning to select operators in meta-heuristics: An integration of Q-learning into the iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2022.03.054
Kizilay, D., Tasgetiren, M. F., Pan, Q. K., & Gao, L. (2019). A variable block insertion heuristic for solving permutation flow shop scheduling problem with makespan criterion. Algorithms, 12(5). https://doi.org/10.3390/a12050100
Mccormick, S., Pinedo, M., J. Shenker, S., & Wolf, B. (1989). Sequencing in an Assembly Line With Blocking to Minimize Cycle Time. Operations Research, 37, 925–935. https://doi.org/10.1287/opre.37.6.925
Merchan, A. F., & Maravelias, C. T. (2016). Preprocessing and tightening methods for time-indexed MIP chemical production scheduling models. Computers and Chemical Engineering, 84, 516–535. https://doi.org/10.1016/j.compchemeng.2015.10.003
Miyata, H. H., & Nagano, M. S. (2019). The blocking flow shop scheduling problem: A comprehensive and conceptual review. In Expert Systems with Applications (Vol. 137, pp. 130–156). Elsevier Ltd. https://doi.org/10.1016/j.eswa.2019.06.069
Naderi, B., & Ruiz, R. (2010). The distributed permutation flowshop scheduling problem. Computers & Operations Research, 37(4), 754–768. https://doi.org/10.1016/J.COR.2009.06.019
Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95. https://doi.org/10.1016/0305-0483(83)90088-9
Newton, M. A. H., Riahi, V., Su, K., & Sattar, A. (2019). Scheduling blocking flowshops with setup times via constraint guided and accelerated local search. Computers & Operations Research, 109, 64–76. https://doi.org/10.1016/J.COR.2019.04.024
Osman, I., & N. Potts, C. (1989). Simulated Annealing for Permutation Flow-Shop Scheduling. Omega, 17, 551–557. https://doi.org/10.1016/0305-0483(89)90059-5
Öztop, H, Tasgetiren, M. F., Kandiller, L., & Pan, Q.-K. (2020). A Novel General Variable Neighborhood Search through Q-Learning for No-Idle Flowshop Scheduling. 2020 IEEE Congress on Evolutionary Computation (CEC), 1–8. https://doi.org/10.1109/CEC48606.2020.9185556
Öztop, Hande, Tasgetiren, M. F., Kandiller, L., & Pan, Q.-K. (2022). Metaheuristics with restart and learning mechanisms for the no-idle flowshop scheduling problem with makespan criterion. Computers & Operations Research, 138, 105616. https://doi.org/https://doi.org/10.1016/j.cor.2021.105616
Pan, Q.-K., & Ruiz, R. (2012). An estimation of distribution algorithm for lot-streaming flow shop problems with setup times. Omega, 40(2), 166–180. https://doi.org/10.1016/J.OMEGA.2011.05.002
Ramezanian, R., Vali-Siar, M. M., & Jalalian, M. (2019). Green permutation flowshop scheduling problem with sequence-dependent setup times: a case study. International Journal of Production Research, 57(10), 3311–3333. https://doi.org/10.1080/00207543.2019.1581955
Riahi, V., Newton, M. A. H., Su, K., & Sattar, A. (2019). Constraint guided accelerated search for mixed blocking permutation flowshop scheduling. Computers & Operations Research, 102, 102–120. https://doi.org/10.1016/J.COR.2018.10.003
Ribas, I., & Companys, R. (2015). Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization. Computers & Industrial Engineering, 87, 30–39. https://doi.org/https://doi.org/10.1016/j.cie.2015.04.013
Ribas, I., Companys, R., & Tort-Martorell, X. (2015). An efficient Discrete Artificial Bee Colony algorithm for the blocking flow shop problem with total flowtime minimization. Expert Systems with Applications, 42(15), 6155–6167. https://doi.org/https://doi.org/10.1016/j.eswa.2015.03.026
Ribas, I., Companys, R., & Tort-Martorell, X. (2017). Efficient heuristics for the parallel blocking flow shop scheduling problem. Expert Systems with Applications, 74, 41–54. https://doi.org/10.1016/j.eswa.2017.01.006
Ribas, I., Companys, R., & Tort-Martorell, X. (2019). An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem. Expert Systems with Applications, 121, 347–361. https://doi.org/10.1016/j.eswa.2018.12.039
Ronconi, D P, & Armentano, V. A. (2001). Lower bounding schemes for flowshops with blocking in-process. Journal of the Operational Research Society, 52(11), 1289–1297. https://doi.org/10.1057/palgrave.jors.2601220
Ronconi, Débora P. (2004). A note on constructive heuristics for the flowshop problem with blocking. International Journal of Production Economics, 87(1), 39–48. https://doi.org/10.1016/S0925-5273(03)00065-3
Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033–2049. https://doi.org/https://doi.org/10.1016/j.ejor.2005.12.009
Shao, Z., Pi, D., & Shao, W. (2018a). Estimation of distribution algorithm with path relinking for the blocking flow-shop scheduling problem. Engineering Optimization, 50(5), 894–916. https://doi.org/10.1080/0305215X.2017.1353090
Shao, Z., Pi, D., & Shao, W. (2018b). A novel discrete water wave optimization algorithm for blocking flow-shop scheduling problem with sequence-dependent setup times. Swarm and Evolutionary Computation, 40, 53–75. https://doi.org/10.1016/j.swevo.2017.12.005
Shao, Z., Pi, D., & Shao, W. (2020). Hybrid enhanced discrete fruit fly optimization algorithm for scheduling blocking flow-shop in distributed environment. Expert Systems with Applications, 145, 113147. https://doi.org/https://doi.org/10.1016/j.eswa.2019.113147
Shao, Z., Pi, D., Shao, W., & Yuan, P. (2019). An efficient discrete invasive weed optimization for blocking flow-shop scheduling problem. Engineering Applications of Artificial Intelligence, 78, 124–141. https://doi.org/10.1016/j.engappai.2018.11.005
Shao, Z., Shao, W., & Pi, D. (2020). Effective heuristics and metaheuristics for the distributed fuzzy blocking flow-shop scheduling problem. Swarm and Evolutionary Computation, 59, 100747. https://doi.org/10.1016/j.swevo.2020.100747
Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (Second Edi). The MIT Press.
Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1), 65–74. https://doi.org/10.1016/0377-2217(90)90090-X
Tasgetiren, M. Fatih, Kizilay, D., Pan, Q. K., & Suganthan, P. N. (2017). Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion. Computers and Operations Research, 77. https://doi.org/10.1016/j.cor.2016.07.002
Tasgetiren, M. Fatih, Pan, Q.-K., & Liang, Y.-C. (2009). A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times. Computers & Operations Research, 36(6), 1900–1915. https://doi.org/https://doi.org/10.1016/j.cor.2008.06.007
Tasgetiren, M.F., Pan, Q.-K., Kizilay, D., & Gao, K. (2016). A Variable Block Insertion Heuristic for the Blocking Flowshop Scheduling Problem with Total Flowtime Criterion. Algorithms, 9(4). https://doi.org/10.3390/a9040071
Trabelsi, W., Sauvey, C., & Sauer, N. (2012). Heuristics and metaheuristics for mixed blocking constraints flowshop scheduling problems. Computers & Operations Research, 39(11), 2520–2527. https://doi.org/https://doi.org/10.1016/j.cor.2011.12.022
Vallada, E., Ruiz, R., & Framinan, J. M. (2015). New hard benchmark for flowshop scheduling problems minimising makespan. European Journal of Operational Research, 240(3), 666–677. https://doi.org/https://doi.org/10.1016/j.ejor.2014.07.033
Wang, L., Pan, Q.-K., & Fatih Tasgetiren, M. (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. https://doi.org/10.1016/J.ESWA.2010.04.042
Wang, L., Pan, Q.-K., Suganthan, P. N., Wang, W.-H., & Wang, Y.-M. (2010). A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems. Computers & Operations Research, 37(3), 509–520. https://doi.org/10.1016/J.COR.2008.12.004
Wang, X., & Tang, L. (2012). A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking. Applied Soft Computing Journal, 12(2), 652–662. https://doi.org/10.1016/j.asoc.2011.09.021
Watkins, C. (1989). Learning From Delayed Rewards [King’s College]. http://www.cs.rhul.ac.uk/~chrisw/new_thesis.pdf
Yuan, S., Li, T., & Wang, B. (2020). A co-evolutionary genetic algorithm for the two-machine flow shop group scheduling problem with job-related blocking and transportation times. Expert Systems with Applications, 152, 113360. https://doi.org/10.1016/j.eswa.2020.113360
Zhang, G., Xing, K., & Cao, F. (2018). Discrete differential evolution algorithm for distributed blocking flowshop scheduling with makespan criterion. Engineering Applications of Artificial Intelligence, 76, 96–107. https://doi.org/10.1016/J.ENGAPPAI.2018.09.005
  • 0
  • 1
  • 2
  • 3
  • 4
  • 5

Journal: Journal of Project Management | Year: 2024 | Volume: 9 | Issue: 2 | Views: 1117 | Reviews: 0

Related Articles:
  • Evaluating procedures in the NEH heuristic for the PFSP - SIST
  • A branch and bound method in a permutation flow shop with blocking and setu ...
  • A computational evaluation of constructive heuristics for the parallel bloc ...
  • Solving the permutation flow shop problem with blocking and setup time cons ...
  • Evaluating the performance of constructive heuristics for the blocking flow ...

Add Reviews

Name:*
E-Mail:
Review:
Bold Italic Underline Strike | Align left Center Align right | Insert smilies Insert link URLInsert protected URL Select color | Add Hidden Text Insert Quote Convert selected text from selection to Cyrillic (Russian) alphabet Insert spoiler
winkwinkedsmileam
belayfeelfellowlaughing
lollovenorecourse
requestsadtonguewassat
cryingwhatbullyangry
Security Code: *
Include security image CAPCHA.
Refresh Code

® 2010-2025 GrowingScience.Com