Order Constraints for Single Machine Scheduling with Non-Linear Cost

Typically in a scheduling problem we are given jobs of different processing times pj and different priority weights wj, 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 ?wjC?j, where Cjis 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?. Copyright © 2014. by the Society for Industrial and Applied Mathematics.