A combinatorial auctions perspective on min-sum scheduling problems

Yunpeng Pan (yunpeng.pangmail.com)

Abstract: In combinatorial auctions, prospective buyers bid on bundles of items for sale, including but not limited to singleton bundles. The bid price given by a buyer on a particular bundle reflects his/her perceived utility of the bundle of items as a whole. After collecting all the bids, the auctioneer determines the revenue-maximizing assignment of winning bidders to bundles subject to nonoverlapping of bundles. To accomplish this, the auctioneer needs to solve a winner determination problem (WDP). The exactly same way of thinking can be taken to the context of min-sum scheduling, where jobs can be viewed as bidders who bid on bundles of discrete time periods on machines. Particular problems often permit only a subset of bundles. By putting appropriate restrictions on the collection of permissible bundles, we can derive from the WDP, various integer programming (IP) formulations for nonpreemptive as well as preemptive min-sum scheduling problems. We thus obtain the well-known time-indexed IP formulation in the nonpreemptive case, and further, a new strong IP formulation in the preemptive case.

Keywords: scheduling, time-indexed formulation, winner determination, preemptive

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization

Category 3: Integer Programming (0-1 Programming )

Citation: Working paper. Submitted for publication.

Download: [PDF]

Entry Submitted: 08/04/2006
Entry Accepted: 08/04/2006
Entry Last Modified: 08/04/2006

Modify/Update this entry