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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2019-04-18


    Size :

    15 pages





    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English





    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

    Free access

    IDLING DETECTION DEVICE AND IDLING DETECTION METHOD

    MIYAMOTO SHINTARO | European Patent Office | 2021

    Free access

    IDLING SUPPRESSION APPARATUS AND IDLING SUPPRESSION METHOD

    KATO KENJI / MARUYAMA REI | European Patent Office | 2017

    Free access

    IDLING STOP SYSTEM

    TANAKA HIDEKAZU | European Patent Office | 2016

    Free access