ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

Scheduling with safety distances (1995)

Spieksma, Frits C. R. ; Woeginger, Gerhard J. ; Yu, Zhongliang

Springer

Annals of operations research 57 (1995), S. 251-264

add to mindlist on the mindlist

Details

ISSN: 1572-9338

Source: Springer Online Journal Archives 1860-2000

Topics: Mathematics , Economics

Notes: Abstract We 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 we 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. We 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.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF02099701

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit