A combinatorial auctions perspective on min-sum scheduling problems

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.