Publications Repository - Gdańsk University of Technology

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.

Authors

• Hanna Furmańczyk,
• prof. dr hab. inż. Marek Kubale link open in new tab