The standard one-machine scheduling problem consists in scheduling
a set of jobs in one machine which can handle only one job at a
time, minimizing the maximum lateness. Each job is available for
processing at its release date, requires a known processing time
and after finishing the processing, it is delivery after a certain
time. There also can exists precedence constraints between pairs
of jobs, requiring that the first jobs must be completed before
the second job can start. An extension of ...
The standard one-machine scheduling problem consists in scheduling
a set of jobs in one machine which can handle only one job at a
time, minimizing the maximum lateness. Each job is available for
processing at its release date, requires a known processing time
and after finishing the processing, it is delivery after a certain
time. There also can exists precedence constraints between pairs
of jobs, requiring that the first jobs must be completed before
the second job can start. An extension of this problem consists
in assigning a time interval between the processing of the jobs
associated with the precedence constrains, known by finish-start
time-lags. In presence of this constraints, the problem is NP-hard
even if preemption is allowed. In this work, we consider a special
case of the one-machine preemption scheduling problem with time-
lags, where the time-lags have a chain form, and propose a
polynomial algorithm to solve it. The algorithm consist in a
polynomial number of calls of the preemption version of the Longest
Tail Heuristic. One of the applicability of the method is to obtain
lower bounds for NP-hard one-machine and job-shop scheduling
problems. We present some computational results of this
application, followed by some conclusions.
+