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.
Parallel Scheduling Subject to Release Dates and Delivery Times Under the Non-idling Constraint
Informatics in Control, Automation and Robotics ; 1 ; 135-149
Lecture Notes in Electrical Engineering ; 495 , 1
18.04.2019
15 pages
Aufsatz/Kapitel (Buch)
Elektronische Ressource
Englisch
Idling stop fines for exceeding legal idling times – From the driver’s perspective
Online Contents | 2014
|IDLING SUPPRESSION APPARATUS AND IDLING SUPPRESSION METHOD
Europäisches Patentamt | 2017
|