Scheduling jobs in a contaminated area: a model and heuristic algorithms

Scheduling problems studied in this paper arise when some tasks have to be executed by human resources in an area contaminated with radioactive or chemical materials. The specificity of the problems is that each work period should be accompanied by a rest period whose length depends on the start time of the corresponding work period. The dependency functions are exponentially decreasing ones. The problems with a single worker and criteria of minimizing maximum lateness or total weighted completion time are proved to be NP–hard. Heuristic algorithms for their solving are developed and computational experiments are provided.