Search
Abstract
The problem of scheduling n identical jobs on 4 uniform machines with speeds s1>=s2>=s3>=s4 is considered.The aim is to find a schedule with minimum possible length. We assume that jobs are subject to mutual exclusion constraints modeled by a bipartite incompatibility graph of degree delta. We show that the general problem is NP-hard even if s1=s2=s3. If, however, delta<5 and s1>12s2 s2=s3=s4, then the problem can be solved to optimality in polynomial time. The same algorithm returns a solution of value at most 2 times optimal provided that s1>2s2.
Citations
-
4
CrossRef
-
0
Web of Science
-
1 1
Scopus
Authors (2)
-
Hanna Furmańczyk
- University of Gdańsk Institute of Informatics
Cite as
Full text
download paper
downloaded 13 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1515/bpasts-2017-0004
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
Bulletin of the Polish Academy of Sciences-Technical Sciences
no. 65,
pages 29 - 34,
ISSN: 0239-7528 - Language:
- English
- Publication year:
- 2017
- Bibliographic description:
- Furmańczyk H., Kubale M.: Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines// Bulletin of the Polish Academy of Sciences-Technical Sciences. -Vol. 65, iss. 1 (2017), s.29-34
- DOI:
- Digital Object Identifier (open in new tab) 10.1515/bpasts-2017-0004
- Verified by:
- Gdańsk University of Technology
seen 87 times