This work addresses the problem of scheduling, on two uniform machines, of a set of unit-time jobs subject to the constraints that some conflicting jobs cannot be scheduled simultaneously on different machines. In the context of our study, these conflicts are modeled by general graphs. The problem of minimizing the maximum completion time (makespan) is known to be NP-hard in the strong sense for the speed values 1 and 2. We prove the NP-hardness in the strong sense for any fixed values speed a and b (a¹b). We propose a Mixed Integer Linear Programming (MILP) model. Then, we develop a branch and bound (B&B) algorithm based on new lower and upper bound procedures. We further provide a computer simulation to measure the performance of the proposed approaches. Our computational study shows that all the instances of size up to 300 jobs are optimally solved by the B&B algorithm or the MILP model.
Scheduling on Two Uniform Machines with Unit Processing Times and Conflict Graph
1 Views
1 Downloads