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

Mixed graph colouring for unit-time scheduling

Author

Listed:
  • Ahmed Kouider
  • Hacène Ait Haddadène
  • Samia Ourari
  • Ammar Oulamara

Abstract

We consider the job shop scheduling problem with unit-time operations and the makespan criterion. This problem is reduced to finding an optimal colouring of a special class of mixed graph, where its partial graph without edges represents the union of maximal directed paths and its partial graph without arcs represents the union of maximal cliques. As the problem is known to be NP-hard, both exact and heuristic methods are proposed to solve it. This study is carried out in three steps. First, a new lower and upper bounds for the mixed chromatic number are proposed. Afterwards, a colour-indexed mathematical model using the proposed bounds is developed. Then, a tabu search using a dynamic neighbourhood structure is adapted for solving large instances. Computational experiments conducted on several modified benchmarks show the efficiency and effectiveness of the proposed resolution methods.

Suggested Citation

  • Ahmed Kouider & Hacène Ait Haddadène & Samia Ourari & Ammar Oulamara, 2017. "Mixed graph colouring for unit-time scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 55(6), pages 1720-1729, March.
    • Handle: RePEc:taf:tprsxx:v:55:y:2017:i:6:p:1720-1729
    DOI: 10.1080/00207543.2016.1224950
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/00207543.2016.1224950
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/00207543.2016.1224950?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. 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.
    2. Moreno Perez, Jose A. & Marcos Moreno-Vega, J. & Rodriguez Martin, Inmaculada, 2003. "Variable neighborhood tabu search and its application to the median cycle problem," European Journal of Operational Research, Elsevier, vol. 151(2), pages 365-378, December.
    3. 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.
    4. Fred Glover, 1989. "Tabu Search---Part I," INFORMS Journal on Computing, INFORMS, vol. 1(3), pages 190-206, August.
    5. Demange, Marc & Ekim, Tınaz & Ries, Bernard & Tanasescu, Cerasela, 2015. "On some applications of the selective graph coloring problem," European Journal of Operational Research, Elsevier, vol. 240(2), pages 307-314.
    6. N. Hefetz & I. Adiri, 1982. "An Efficient Optimal Algorithm for the Two-Machines Unit-Time Jobshop Schedule-Length Problem," Mathematics of Operations Research, INFORMS, vol. 7(3), pages 354-360, August.
    7. Qu, Rong & Burke, Edmund K. & McCollum, Barry, 2009. "Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems," European Journal of Operational Research, Elsevier, vol. 198(2), pages 392-404, October.
    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.
    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. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    2. 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.
    3. 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.
    4. Z C Zhu & K M Ng & H L Ong, 2010. "A modified tabu search algorithm for cost-based job shop problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(4), pages 611-619, April.
    5. Chiara Gruden & Irena Ištoka Otković & Matjaž Šraml, 2020. "Neural Networks Applied to Microsimulation: A Prediction Model for Pedestrian Crossing Time," Sustainability, MDPI, vol. 12(13), pages 1-22, July.
    6. Thibaud Deguilhem & Juliette Schlegel & Jean-Philippe Berrou & Ousmane Djibo & Alain Piveteau, 2024. "Too many options: How to identify coalitions in a policy network?," Post-Print hal-04689665, HAL.
    7. 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.
    8. Сластников С.А., 2014. "Применение Метаэвристических Алгоритмов Для Задачи Маршрутизации Транспорта," Журнал Экономика и математические методы (ЭММ), Центральный Экономико-Математический Институт (ЦЭМИ), vol. 50(1), pages 117-126, январь.
    9. 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.
    10. Nair, D.J. & Grzybowska, H. & Fu, Y. & Dixit, V.V., 2018. "Scheduling and routing models for food rescue and delivery operations," Socio-Economic Planning Sciences, Elsevier, vol. 63(C), pages 18-32.
    11. Cazzaro, Davide & Fischetti, Martina & Fischetti, Matteo, 2020. "Heuristic algorithms for the Wind Farm Cable Routing problem," Applied Energy, Elsevier, vol. 278(C).
    12. Kadri Sylejmani & Jürgen Dorn & Nysret Musliu, 2017. "Planning the trip itinerary for tourist groups," Information Technology & Tourism, Springer, vol. 17(3), pages 275-314, September.
    13. Huang, Yeran & Yang, Lixing & Tang, Tao & Gao, Ziyou & Cao, Fang, 2017. "Joint train scheduling optimization with service quality and energy efficiency in urban rail transit networks," Energy, Elsevier, vol. 138(C), pages 1124-1147.
    14. B Dengiz & C Alabas-Uslu & O Dengiz, 2009. "Optimization of manufacturing systems using a neural network metamodel with a new training approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1191-1197, September.
    15. S-W Lin & K-C Ying, 2008. "A hybrid approach for single-machine tardiness problems with sequence-dependent setup times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(8), pages 1109-1119, August.
    16. Joseph B. Mazzola & Robert H. Schantz, 1997. "Multiple‐facility loading under capacity‐based economies of scope," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(3), pages 229-256, April.
    17. Kadri Sylejmani & Jürgen Dorn & Nysret Musliu, 0. "Planning the trip itinerary for tourist groups," Information Technology & Tourism, Springer, vol. 0, pages 1-40.
    18. Abdmouleh, Zeineb & Gastli, Adel & Ben-Brahim, Lazhar & Haouari, Mohamed & Al-Emadi, Nasser Ahmed, 2017. "Review of optimization techniques applied for the integration of distributed generation from renewable energy sources," Renewable Energy, Elsevier, vol. 113(C), pages 266-280.
    19. Lari, Isabella & Ricca, Federica & Scozzari, Andrea, 2008. "Comparing different metaheuristic approaches for the median path problem with bounded length," European Journal of Operational Research, Elsevier, vol. 190(3), pages 587-597, November.
    20. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar, 2015. "A set covering approach for multi-depot train driver scheduling," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 636-654, April.

    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:1720-1729. 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.