English Version

首页» 学术科研» 讲座信息

1月21日工业工程与管理系--A combinatorial auctions perspective on min-sum scheduling problems

题目:A combinatorial auctions perspective on min-sum scheduling problems


报告人: Dr. Yunpeng Pan

Inventec Appliances Corporation

时 间:2010121日(周四)上午10:30

地 点:方正大厦608会议室



In combinatorial auctions (CA), prospective buyers bid on bundles of items, including but not limited to singleton bundles. The bid price given by a buyer on a particular bundle reflects their perceived utility of the bundle of items as a whole. After collecting all the bids, the auctioneer determines the revenue-maximizing allocation of bundles to winning bidders subject to nonoverlapping of bundles. To accomplish this, the auctioneer needs to solve a winner determination problem (WDP). Min-sum scheduling problems can be re-interpreted in light of CA: Jobs (to be scheduled on machines) 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 linear programming (ILP) formulations for nonpreemptive as well as preemptive min-sum scheduling problems. We thus obtain the well-known time-indexed ILP formulation in the nonpreemptive case, and further, a new strong ILP formulation in the preemptive case.


Dr. Yunpeng Pan is a technology consultant with Inventec Appliances Corporation (IAC) in Nanjing. His prior work experience includes Associate Director of Business Development at IAC, Algorithms and Formulations Architect at CombineNet, Inc., in Pittsburgh, Pennsylvania, and Computer Scientist at Tomotherapy Inc. in Madison, Wisconsin. Dr. Pan received a Ph.D. in Industrial Engineering (2003) and an M.S. in Computer Sciences (2001) from University of Wisconsin-Madison, an M.S. in Operations Research from University of Delaware (1998), and a B.S. in Computational Mathematics from Nanjing University, China (1995). He has published in such scholarly journals as Mathematical Programming, Operations Research Letters, IEEE Transactions on Automation Science and Engineering, European Journal of Operational Research, and Journal of Systems Science and Systems Engineering.