Scheduling with Safety Distances

Scheduling with Safety Distances

0.00 Avg rating0 Votes
Article ID: iaor19952088
Country: Switzerland
Volume: 57
Issue: 1
Start Page Number: 251
End Page Number: 264
Publication Date: Jun 1995
Journal: Annals of Operations Research
Authors: , ,
Abstract:

The authors investigate the problem of Scheduling with Safety Distances (SSD) that consists in scheduling jobs on two parallel machines without machine idle time. Every job is already assigned to its machine, and they just have to specify an ordering of the jobs for each machine. The goal is to find orderings of the jobs such that the minimum time elapsed between any two job completion times is maximized. The authors prove that this problem is NP-hard in general and give polynomial time algorithms for special cases. These results combined establish a sharp borderline between NP-complete and polynomial solvable versions of the problem SSD.

Reviews

Required fields are marked *. Your email address will not be published.