Publications Repository - Gdańsk University of Technology

We study the shared processor scheduling problem with a single shared processor to maximize total weighted overlap, where an overlap for a job is the amount of time it is processed on its private and shared processor in parallel. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an (log)-time optimization algorithm for a class of instances in which non-decreasing order of jobs with respect to processing times provides a non-increasing order with respect to weights—this instance generalizes the unweighted case of the problem. This algorithm also leads to a 1/2-approximation algorithm for the general weighted problem. The complexity of the weighted problem remains open.

Authors

• prof. dr hab. inż. Dariusz Dereniowski link open in new tab ,
• Wiesław Kubiak