IDEAS home Printed from https://ideas.repec.org/a/wly/jnljam/v2012y2012i1n623230.html

A PMBGA to Optimize the Selection of Rules for Job Shop Scheduling Based on the Giffler‐Thompson Algorithm

Author

Listed:
  • Rui Zhang
  • Cheng Wu

Abstract

Most existing research on the job shop scheduling problem has been focused on the minimization of makespan (i.e., the completion time of the last job). However, in the fiercely competitive market nowadays, delivery punctuality is more important for maintaining a high service reputation. So in this paper, we aim at solving job shop scheduling problems with the total weighted tardiness objective. Several dispatching rules are adopted in the Giffler‐Thompson algorithm for constructing active schedules. It is noticeable that the rule selections for scheduling consecutive operations are not mutually independent but actually interrelated. Under such circumstances, a probabilistic model‐building genetic algorithm (PMBGA) is proposed to optimize the sequence of selected rules. First, we use Bayesian networks to model the distribution characteristics of high‐quality solutions in the population. Then, the new generation of individuals is produced by sampling the established Bayesian network. Finally, some elitist individuals are further improved by a special local search module based on parameter perturbation. The superiority of the proposed approach is verified by extensive computational experiments and comparisons.

Suggested Citation

  • Rui Zhang & Cheng Wu, 2012. "A PMBGA to Optimize the Selection of Rules for Job Shop Scheduling Based on the Giffler‐Thompson Algorithm," Journal of Applied Mathematics, John Wiley & Sons, vol. 2012(1).
    • Handle: RePEc:wly:jnljam:v:2012:y:2012:i:1:n:623230
    DOI: 10.1155/2012/623230
    as

    Download full text from publisher

    File URL: https://doi.org/10.1155/2012/623230
    Download Restriction: no
    File URL: https://libkey.io/10.1155/2012/623230?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Michael Pinedo & Marcos Singer, 1999. "A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(1), pages 1-17, February.
    2. 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.
    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. Wolosewicz, Cathy & Dauzère-Pérès, Stéphane & Aggoune, Riad, 2015. "A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem," European Journal of Operational Research, Elsevier, vol. 244(1), pages 3-12.
    2. Helena Ramalhinho-Lourenço & Olivier C. Martin & Thomas Stützle, 2000. "Iterated local search," Economics Working Papers 513, Department of Economics and Business, Universitat Pompeu Fabra.
    3. 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.
    4. Jacomine Grobler & Andries Engelbrecht & Schalk Kok & Sarma Yadavalli, 2010. "Metaheuristics for the multi-objective FJSP with sequence-dependent set-up times, auxiliary resources and machine down time," Annals of Operations Research, Springer, vol. 180(1), pages 165-196, November.
    5. 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.
    6. Bürgy, Reinhard & Bülbül, Kerem, 2018. "The job shop scheduling problem with convex costs," European Journal of Operational Research, Elsevier, vol. 268(1), pages 82-100.
    7. Mukherjee, Saral & Chatterjee Ashis K, 2002. "Applying Machine Based Decomposition in 2-Machine Flow Shops," IIMA Working Papers WP2002-08-05, Indian Institute of Management Ahmedabad, Research and Publication Department.
    8. Zhang, Rui & Song, Shiji & Wu, Cheng, 2013. "A hybrid artificial bee colony algorithm for the job shop scheduling problem," International Journal of Production Economics, Elsevier, vol. 141(1), pages 167-178.
    9. 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.
    10. Varela, Ramiro & Vela, Camino R. & Puente, Jorge & Gomez, Alberto, 2003. "A knowledge-based evolutionary strategy for scheduling problems with bottlenecks," European Journal of Operational Research, Elsevier, vol. 145(1), pages 57-71, February.
    11. Pham, Dinh-Nguyen & Klinkert, Andreas, 2008. "Surgical case scheduling as a generalized job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1011-1025, March.
    12. El-Bouri, A. & Azizi, N. & Zolfaghari, S., 2007. "A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: The case of job shop scheduling," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1894-1910, March.
    13. Christophe Sauvey & Wajdi Trabelsi & Nathalie Sauer, 2020. "Mathematical Model and Evaluation Function for Conflict-Free Warranted Makespan Minimization of Mixed Blocking Constraint Job-Shop Problems," Mathematics, MDPI, vol. 8(1), pages 1-17, January.
    14. Dušan Hvalica, 2013. "Solving job shop problems in the context of hypergraphs," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 21(1), pages 27-40, June.
    15. Pisut Pongchairerks, 2019. "A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem," Complexity, Hindawi, vol. 2019, pages 1-11, March.
    16. Agnetis, Alessandro & Billaut, Jean-Charles & Pinedo, Michael & Shabtay, Dvir, 2025. "Fifty years of research in scheduling — Theory and applications," European Journal of Operational Research, Elsevier, vol. 327(2), pages 367-393.
    17. Francis Sourd & Wim Nuijten, 2000. "Multiple-Machine Lower Bounds for Shop-Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 12(4), pages 341-352, November.
    18. Hurink, Johann & Knust, Sigrid, 2005. "Tabu search algorithms for job-shop problems with a single transport robot," European Journal of Operational Research, Elsevier, vol. 162(1), pages 99-111, April.
    19. Panos Pardalos & Oleg Shylo, 2006. "An Algorithm for the Job Shop Scheduling Problem based on Global Equilibrium Search Techniques," Computational Management Science, Springer, vol. 3(4), pages 331-348, September.
    20. Murovec, Bostjan & Suhel, Peter, 2004. "A repairing technique for the local search of the job-shop problem," European Journal of Operational Research, Elsevier, vol. 153(1), pages 220-238, February.

    More about this item

    Statistics

    Access and download statistics

    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:wly:jnljam:v:2012:y:2012:i:1:n:623230. 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: Wiley Content Delivery (email available below). General contact details of provider: https://onlinelibrary.wiley.com/journal/4185 .

    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.