Weighted Tardiness Scheduling with Sequence-Dependent Setups: A Benchmark Library

Technical Report, Intelligent Coordination and Logistics Laboratory, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, .



This report details a set of benchmark problem instances that we have generated for the weighted tardiness scheduling with sequence-dependent setups problem. The version of the problem without setup times is NP-Hard. The problem is further complicated by the sequence-dependent nature of the setups. Given that the weighted tardiness objective and the sequence-dependent setups constraint are both common real-world problem characteristics, and given the difficulty in solving this problem, we feel that it is currently under-represented in the research literature. With few algorithms currently available for the problem, this first benchmark problem set and initial results obtained via a large number of heuristic algorithms will hopefully encourage others to explore additional solutions to the problem.