IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i21p3342-d1506120.html
   My bibliography  Save this article

A Radial Memetic Algorithm to Resolve the No-Wait Job-Shop Scheduling Problem

Author

Listed:
  • Ricardo Pérez-Rodríguez

    (Research Group, CONAHCYT, Av Insurgentes Sur 1582, Crédito Constructor, Benito Juárez, Mexico City 03940, Mexico)

Abstract

A new radial memetic algorithm is proposed to resolve the no-wait job-shop scheduling problem. Basically, each sequencing solution is factorized as a distance-based ranking model, i.e., each solution is decomposed in n − 1 terms, where n is the number of jobs to be sequenced. After that, a cumulative radial distribution of hydrogen is considered to produce new factorizations using the offspring information (genes). Such radial distribution is applied in the local optimization procedure of the memetic algorithm. A benchmarking dataset is used to show the performance of this new experimental technique, as well as other current procedures. Statistical tests were implemented to confirm the performance of the proposed scheme.

Suggested Citation

  • Ricardo Pérez-Rodríguez, 2024. "A Radial Memetic Algorithm to Resolve the No-Wait Job-Shop Scheduling Problem," Mathematics, MDPI, vol. 12(21), pages 1-15, October.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:21:p:3342-:d:1506120
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/21/3342/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/21/3342/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Nicholas G. Hall & Chelliah Sriskandarajah, 1996. "A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process," Operations Research, INFORMS, vol. 44(3), pages 510-525, June.
    2. Robert H. Storer & S. David Wu & Renzo Vaccari, 1992. "New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling," Management Science, INFORMS, vol. 38(10), pages 1495-1509, October.
    3. Tang, Lixin & Liu, Jiyin & Rong, Aiying & Yang, Zihou, 2000. "A mathematical programming model for scheduling steelmaking-continuous casting production," European Journal of Operational Research, Elsevier, vol. 120(2), pages 423-435, January.
    4. Grabowski, Jozef & Pempera, Jaroslaw, 2000. "Sequencing of jobs in some production system," European Journal of Operational Research, Elsevier, vol. 125(3), pages 535-550, September.
    5. Joseph Adams & Egon Balas & Daniel Zawack, 1988. "The Shifting Bottleneck Procedure for Job Shop Scheduling," Management Science, INFORMS, vol. 34(3), pages 391-401, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Marco Pranzo & Dario Pacciarelli, 2016. "An iterated greedy metaheuristic for the blocking job shop scheduling problem," Journal of Heuristics, Springer, vol. 22(4), pages 587-611, August.
    2. Christoph Schuster, 2006. "No-wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 63(3), pages 473-491, July.
    3. Alvarez-Valdes, R. & Fuertes, A. & Tamarit, J. M. & Gimenez, G. & Ramos, R., 2005. "A heuristic to schedule flexible job-shop in a glass factory," European Journal of Operational Research, Elsevier, vol. 165(2), pages 525-534, September.
    4. Zhu, Jie & Li, Xiaoping & Wang, Qian, 2009. "Complete local search with limited memory algorithm for no-wait job shops to minimize makespan," European Journal of Operational Research, Elsevier, vol. 198(2), pages 378-386, October.
    5. Mascis, Alessandro & Pacciarelli, Dario, 2002. "Job-shop scheduling with blocking and no-wait constraints," European Journal of Operational Research, Elsevier, vol. 143(3), pages 498-517, December.
    6. Sels, Veronique & Craeymeersch, Kjeld & Vanhoucke, Mario, 2011. "A hybrid single and dual population search procedure for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 215(3), pages 512-523, December.
    7. Ganesan, Viswanath Kumar & Sivakumar, Appa Iyer, 2006. "Scheduling in static jobshops for minimizing mean flowtime subject to minimum total deviation of job completion times," International Journal of Production Economics, Elsevier, vol. 103(2), pages 633-647, October.
    8. Meloni, Carlo & Pranzo, Marco & Samà, Marcella, 2022. "Evaluation of VaR and CVaR for the makespan in interval valued blocking job shops," International Journal of Production Economics, Elsevier, vol. 247(C).
    9. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    10. Bierwirth, C. & Kuhpfahl, J., 2017. "Extended GRASP for the job shop scheduling problem with total weighted tardiness objective," European Journal of Operational Research, Elsevier, vol. 261(3), pages 835-848.
    11. Steinhofel, K. & Albrecht, A. & Wong, C. K., 1999. "Two simulated annealing-based heuristics for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 118(3), pages 524-548, November.
    12. Edzard Weber & Anselm Tiefenbacher & Norbert Gronau, 2019. "Need for Standardization and Systematization of Test Data for Job-Shop Scheduling," Data, MDPI, vol. 4(1), pages 1-21, February.
    13. Selcuk Goren & Ihsan Sabuncuoglu & Utku Koc, 2012. "Optimization of schedule stability and efficiency under processing time variability and random machine breakdowns in a job shop environment," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(1), pages 26-38, February.
    14. Mattfeld, Dirk C. & Bierwirth, Christian, 2004. "An efficient genetic algorithm for job shop scheduling with tardiness objectives," European Journal of Operational Research, Elsevier, vol. 155(3), pages 616-630, June.
    15. Diarmuid Grimes & Emmanuel Hebrard, 2015. "Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 268-284, May.
    16. Ronconi, Débora P. & Henriques, Luís R.S., 2009. "Some heuristic algorithms for total tardiness minimization in a flowshop with blocking," Omega, Elsevier, vol. 37(2), pages 272-281, April.
    17. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    18. G I Zobolas & C D Tarantilis & G Ioannou, 2009. "A hybrid evolutionary algorithm for the job shop scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(2), pages 221-235, February.
    19. Guinet, Alain & Legrand, Marie, 1998. "Reduction of job-shop problems to flow-shop problems with precedence constraints," European Journal of Operational Research, Elsevier, vol. 109(1), pages 96-110, August.
    20. Smutnicki, Czeslaw & Pempera, Jaroslaw & Bocewicz, Grzegorz & Banaszak, Zbigniew, 2022. "Cyclic flow-shop scheduling with no-wait constraints and missing operations," European Journal of Operational Research, Elsevier, vol. 302(1), pages 39-49.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:12:y:2024:i:21:p:3342-:d:1506120. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.