Scheduling and combinatorial auctions: Lagrangean relaxation-based bonds for the WJISP

In this paper we consider the following problem: a Company wants to sell consecutive time slots on a single machine. It wants to maximize the revenues, whereby market prizes are not known. Additionally, consider a number of potential buyers of those time slots providing each at least one job. All these jobs can be executed on that machine, but the number of time slots is not large enough to schedule all jobs. Furthermore assume, that every customer gains a job-specific profit with the processing of one of his jobs, whereby this profit is private information and thus, only known to him. What the company faces then is an allocation problem: Which buyer should get what time slot(s) at what prize in order to maximize the company's revenue. In the following we will show that this problem is well suited to be solved by a combinatorial auction. Within combinatorial auctions bidders are enabled to place bids on any subset of items that are auctioned off. We will focus on the winner determination problem for such an auction. The winner determination is understood as the assignment of items to bidders after all bids have been placed, with the objective to maximize the auctioneers outcome. It will be shown that the winner determination problem here can be described as so-called Weighted Job Interval Scheduling Problem (WJISP). Since this problem is known to be NP-hard, heuristics have become a main research interest. Unfortunately, there has not been done much research on upper bounds so far. Furthermore, to the best of our knowledge, no runtime studies are available in the literature yet. Here, we try to close these gaps. First, we present a Lagrangean heuristic for the WJISP and characterize relevant test instances. Using this test-bed, the considered upper and lower bounds are respectively compared to the LP-solution and to a heuristic taken from the literature.