ISSN:
1572-9338
Keywords:
Scheduling
;
flow shops
;
resource constraints
;
message transmission
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract We consider the problem of scheduling tasks on flow shops when each task may also require the use of additional resources. It is assumed that all operations have unit lengths, the resource requirements are of 0–1 type and there is one type of the additional resource in the system. It is proved that when the number of machines is arbitrary, the problem of minimizing schedule length is NP-hard, even when only one unit of the additional resource is available in the system. On the other hand, when the number of machines is fixed, then the problem is solvable in polynomial time, even for an arbitrary number of resource units available. For the two machine case anO(n log 2 2 n) algorithm minimizing maximum lateness is also given. The presented results are also of importance in some message transmission systems.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02283747
Permalink
