IDEAS home Printed from https://ideas.repec.org/a/taf/tprsxx/v55y2017i6p1549-1564.html
   My bibliography  Save this article

Mixed graph model and algorithms for parallel-machine job-shop scheduling problems

Author

Listed:
  • Yuri N. Sotskov
  • Omid Gholami

Abstract

Heuristic algorithms are developed to solve the parallel-machine job-shop problems FJ|ri|Φ$ FJ|r_i|\Phi $, where the criterion Φ$ \Phi $ is the minimisation of the makespan, Φ=Cmax$ \Phi =C_{\max } $, or the sum of completion times, Φ=∑Ci$ \Phi =\sum C_i $. The developed algorithms include sequencing and assigning stages. At the sequencing stage, the job-shop problem J|ri|Φ$ J|r_i|\Phi $ is solved, where job Ji∈J$ J_i \in \mathcal{J} $ is available for processing from time ri$ r_i $. The problem J|ri|Φ$ J|r_i|\Phi $ is modelled by a mixed graph G=(O,A,E)$ G=(\mathcal{O}, A, E) $, where the vertices O$ \mathcal{O} $ are the operations to be processed. The precedence constraints on the set O$ \mathcal{O} $ are determined by the arc set A$ A $. The resource constraints are determined by the edge set E$ E $. In order to resolve a conflict arising between two operations processed on the same machine, the algorithm should substitute a conflict edge from the set E$ E $ by an arc incident to the same vertices from the set O$ \mathcal{O} $. The resulting digraph Gt=(O,A⋃At,∅)$ G_t=(\mathcal{O}, A \bigcup A_t, \varnothing ) $ determines a heuristic solution to the problem J|ri|Φ$ J|r_i|\Phi $, where all machines are different. The digraph Gt$ G_t $ determines a semi-active schedule for the problem FJ|ri|Φ$ FJ|r_i|\Phi $. A mixed graph model is used for solving the problem FJ|ri|Φ$ FJ|r_i|\Phi $, which allows a scheduler to construct an efficient schedule via deleting some arcs from the set At$ A_t $ in the digraph Gt$ G_t $ or (and) via changing orientations of the arcs. Several heuristics have been developed to transform the digraph Gt$ G_t $ into a new digraph as a proper answer for the problem FJ|ri|Φ$ FJ|r_i|\Phi $. The developed algorithms have been tested on the benchmark instances. It is demonstrated how these algorithms may be used for solving a train timetabling problem.

Suggested Citation

  • Yuri N. Sotskov & Omid Gholami, 2017. "Mixed graph model and algorithms for parallel-machine job-shop scheduling problems," International Journal of Production Research, Taylor & Francis Journals, vol. 55(6), pages 1549-1564, March.
  • Handle: RePEc:taf:tprsxx:v:55:y:2017:i:6:p:1549-1564
    DOI: 10.1080/00207543.2015.1075666
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/00207543.2015.1075666
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1080/00207543.2015.1075666?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Peter Brucker & Yu Sotskov & Frank Werner, 2007. "Complexity of shop-scheduling problems with fixed number of jobs: a survey," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 65(3), pages 461-481, June.
    2. Sprecher, Arno & Kolisch, Rainer & Drexl, Andreas, 1995. "Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 80(1), pages 94-102, January.
    3. Paulli, Jan, 1995. "A hierarchical approach for the FMS scheduling problem," European Journal of Operational Research, Elsevier, vol. 86(1), pages 32-42, October.
    4. Chiang, Tsung-Che & Lin, Hsiao-Jou, 2013. "A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling," International Journal of Production Economics, Elsevier, vol. 141(1), pages 87-98.
    5. Egon Balas, 1969. "Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm," Operations Research, INFORMS, vol. 17(6), pages 941-957, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gao, Yuan & Kroon, Leo & Yang, Lixing & Gao, Ziyou, 2018. "Three-stage optimization method for the problem of scheduling additional trains on a high-speed rail corridor," Omega, Elsevier, vol. 80(C), pages 175-191.
    2. Du, Yiying & Zhou, Wenyuan & Lian, Feng, 2022. "A scheme for passenger service-like backhaul for China railway express trains," Transport Policy, Elsevier, vol. 120(C), pages 56-68.

    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. Hosseini, Amir & Otto, Alena & Pesch, Erwin, 2024. "Scheduling in manufacturing with transportation: Classification and solution techniques," European Journal of Operational Research, Elsevier, vol. 315(3), pages 821-843.
    2. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    3. Yuri N. Sotskov, 2020. "Mixed Graph Colorings: A Historical Review," Mathematics, MDPI, vol. 8(3), pages 1-24, March.
    4. Kolisch, Rainer & Padman, Rema, 1997. "An integrated survey of project scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 463, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    5. Abdollah Arasteh, 2020. "Considering Project Management Activities for Engineering Design Groups," SN Operations Research Forum, Springer, vol. 1(4), pages 1-29, December.
    6. Li, Xinyu & Gao, Liang, 2016. "An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem," International Journal of Production Economics, Elsevier, vol. 174(C), pages 93-110.
    7. Kumar, V.N.S.A. & Kumar, V. & Brady, M. & Garza-Reyes, Jose Arturo & Simpson, M., 2017. "Resolving forward-reverse logistics multi-period model using evolutionary algorithms," International Journal of Production Economics, Elsevier, vol. 183(PB), pages 458-469.
    8. Pierre Hansen & Julio Kuplinsky & Dominique Werra, 1997. "Mixed graph colorings," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 45(1), pages 145-160, February.
    9. Rego, César & Duarte, Renato, 2009. "A filter-and-fan approach to the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 194(3), pages 650-662, May.
    10. 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.
    11. Zoghby, Jeriad & Wesley Barnes, J. & Hasenbein, John J., 2005. "Modeling the reentrant job shop scheduling problem with setups for metaheuristic searches," European Journal of Operational Research, Elsevier, vol. 167(2), pages 336-348, December.
    12. Choo Jun Tan & Siew Chin Neoh & Chee Peng Lim & Samer Hanoun & Wai Peng Wong & Chu Kong Loo & Li Zhang & Saeid Nahavandi, 2019. "Application of an evolutionary algorithm-based ensemble model to job-shop scheduling," Journal of Intelligent Manufacturing, Springer, vol. 30(2), pages 879-890, February.
    13. 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.
    14. Dayal Madhukar & Verma, Sanjay, 2015. "Multi-processor Exact Procedures for Regular Measures of the Multi-mode RCPSP," IIMA Working Papers WP2015-03-25, Indian Institute of Management Ahmedabad, Research and Publication Department.
    15. Raúl Mencía & Carlos Mencía, 2021. "One-Machine Scheduling with Time-Dependent Capacity via Efficient Memetic Algorithms," Mathematics, MDPI, vol. 9(23), pages 1-24, November.
    16. Monaci, Marta & Agasucci, Valerio & Grani, Giorgio, 2024. "An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents," European Journal of Operational Research, Elsevier, vol. 312(3), pages 910-926.
    17. Nicolás Álvarez-Gil & Rafael Rosillo & David de la Fuente & Raúl Pino, 2021. "A discrete firefly algorithm for solving the flexible job-shop scheduling problem in a make-to-order manufacturing system," 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. 29(4), pages 1353-1374, December.
    18. Xiuli Wu & Shaomin Wu, 2017. "An elitist quantum-inspired evolutionary algorithm for the flexible job-shop scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 28(6), pages 1441-1457, August.
    19. 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.
    20. Shadrokh, Shahram & Kianfar, Fereydoon, 2007. "A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty," European Journal of Operational Research, Elsevier, vol. 181(1), pages 86-101, August.

    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:taf:tprsxx:v:55:y:2017:i:6:p:1549-1564. 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: Chris Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/TPRS20 .

    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.