Scheduling in a contaminated area: A model and polynomial algorithms

There are n jobs to be scheduled in a contaminated area. The jobs can be rescue, de-activation or cleaning works to be executed by a single worker in an area contaminated with radio-active or chemical materials. Precedence relations can be given on the set of jobs. An execution of each job can be preempted. However, the length of the minimal uninterrupted work period is given and it is the same for all jobs. Each work period for a job should be accompanied by a rest period whose length depends on the start time of the work period and its length. We focus on a short term planning problem. We show that this problem can be modelled by a scheduling problem with start time dependent job processing times. The dependency functions are exponentially decreasing ones. We also construct two polynomial time algorithms for the both cases-with and without precedence constraints. (c) 2005 Elsevier B.V. All rights reserved.