Benchmark Problems for Oversubscribed Scheduling

Abstract

When organizing a scheduling competition one important issue is identifying the test problems for which the participating teams should demonstrate the performance of their approach. Ideally, the results of a competitive evaluation of different approaches should be useful to both scheduling researchers and practitioners. To enable this, we believe that the process of producing problem instances for the competition should focus on two main issues: 1) generating benchmark problems that abstract features from real-world domains, while still providing guidance to solving problem instances from these domains and 2) choosing the real-world domain/domains to be representative for the type of challenges human schedulers are facing. The contribution of our paper is twofold. First, we propose problems with resource oversubscription as good candidates for the competition problems. Second, we present our approach to generating problems by merging the main common features of two similar real-world oversubscribed applications.