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 radio-active 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.