Typically in a scheduling problem we are given jobs of different processing times p_j and different priority weights w_j, and need to schedule them on a single machine in order to minimize a specific cost function. In this paper we consider the non-linear objective function ∑w_jC_j~β, where C_j is the completion time of job j and β > 0 is some arbitrary real constant. Except for β = 1 the complexity status of this problem is open. Past research mainly focused on the quadratic case (β = 2) and proposed different techniques to speed up exact algorithms. This paper proposes new pruning rules and generalizations of existing rules to non-integral β. An experimental study evaluates the impact of the proposed rules on the exact algorithm A~*.
展开▼
