Abstract In this paper, we study the problem of scheduling jobs on identical parallel machines where the jobs are constrained with release dates and delivery times and the machines must work under the non-idling constraint. This means that each machine must process all the jobs affected to it continuously without any intermediate delays. The objective is to minimize the maximum completion time of all jobs (or makespan). This problem is strongly NP-hard [8] since its particular case on only one non-idling machine has been proved to be strongly NP-hard (see [4]). We first study the particular case on only one non-idling machine. Then, we propose a new resolution methodology for the problem with identical machines working under the non-idling constraint. We first suggest a generalization of the well known rule of Jackson [10] in order to construct an efficient feasible schedule for this problem. This rule gives priority to the ready jobs with the greatest delivery time. Then, we extend the algorithm of Potts which has been proposed in [13] to solve the one machine problem and later extended in [12] to solve its non-idling version. Finally, we present the results of a computational study which shows that the proposed heuristics are fast and yields in most tests schedules with relative deviation which is on average less than 0.5% and more than 50% of problem instances are solved optimally in few seconds.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Parallel Scheduling Subject to Release Dates and Delivery Times Under the Non-idling Constraint


    Beteiligte:
    Hermès, Fatma (Autor:in) / Ghédira, Khaled (Autor:in)


    Erscheinungsdatum :

    18.04.2019


    Format / Umfang :

    15 pages





    Medientyp :

    Aufsatz/Kapitel (Buch)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    The Lagrangean Relaxation for the Flow Shop Scheduling Problem with Precedence Constraints, Release Dates and Delivery Times

    Marcelus Fabri / Helena Ramalhinho / Mauricio C. de Souza et al. | DOAJ | 2019

    Freier Zugriff

    IDLING DETECTION DEVICE AND IDLING DETECTION METHOD

    MIYAMOTO SHINTARO | Europäisches Patentamt | 2021

    Freier Zugriff

    IDLING SUPPRESSION APPARATUS AND IDLING SUPPRESSION METHOD

    KATO KENJI / MARUYAMA REI | Europäisches Patentamt | 2017

    Freier Zugriff

    IDLING STOP SYSTEM

    TANAKA HIDEKAZU | Europäisches Patentamt | 2016

    Freier Zugriff