A multi-unit combinatorial auction based approach for decentralized multi-project scheduling

In industry, many problems are considered as the decentralized resource-constrained multi-project scheduling problem (DRCMPSP). Existing approaches encounter difficulties in dealing with large DRCMPSP cases while respecting the information privacy requirements of the project agents. In this paper, w...

Full description

Saved in:
Bibliographic Details
Main Authors: Song, Wen, Kang, Donghun, Zhang, Jie, Xi, Hui
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2019
Subjects:
Online Access:https://hdl.handle.net/10356/83124
http://hdl.handle.net/10220/49103
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-83124
record_format dspace
spelling sg-ntu-dr.10356-831242020-03-07T11:48:55Z A multi-unit combinatorial auction based approach for decentralized multi-project scheduling Song, Wen Kang, Donghun Zhang, Jie Xi, Hui School of Computer Science and Engineering Rolls-Royce@NTU Corporate Lab Engineering::Computer science and engineering Multi-project Scheduling Multi-unit Combinatorial Auction In industry, many problems are considered as the decentralized resource-constrained multi-project scheduling problem (DRCMPSP). Existing approaches encounter difficulties in dealing with large DRCMPSP cases while respecting the information privacy requirements of the project agents. In this paper, we tackle DRCMPSP by formulating it as a multi-unit combinatorial auction (Wellman et al. in Games Econ Behav 35(1):271–303, 2001), which does not require sensitive private project information. To handle the hardness of bidder valuation, we introduce the capacity query which uses different item capacity profiles to efficiently elicit valuation information from bidders. Based on the capacity query, we adopt two existing strategies (Gonen and Lehmann in Proceedings of the 2nd ACM conference on electronic commerce, pp 13–20, 2000) for solving multi-unit winner determination problems to find good allocations of the DRCMPSP auctions. The first strategy employs a greedy allocation process, which can rapidly find good allocations by allocating the bidder with the best answer after each query. The second strategy is based on a branch-and-bound process to improve the results of the first strategy, by searching for a better sequence of granting the bids from the bidders. Empirical results indicate that the two strategies can find good solutions with higher quality than state-of-the-art decentralized approaches, and scale well to large-scale problems with thousands of activities from tens of projects. NRF (Natl Research Foundation, S’pore) 2019-07-03T04:22:33Z 2019-12-06T15:12:16Z 2019-07-03T04:22:33Z 2019-12-06T15:12:16Z 2017 Journal Article Song, W., Kang, D., Zhang, J., & Xi, H. (2017). A multi-unit combinatorial auction based approach for decentralized multi-project scheduling. Autonomous Agents and Multi-Agent Systems, 31(6), 1548-1577. doi:10.1007/s10458-017-9370-z 1387-2532 https://hdl.handle.net/10356/83124 http://hdl.handle.net/10220/49103 10.1007/s10458-017-9370-z en Autonomous Agents and Multi-Agent Systems © 2017 The Author(s). All rights reserved.
institution Nanyang Technological University
building NTU Library
country Singapore
collection DR-NTU
language English
topic Engineering::Computer science and engineering
Multi-project Scheduling
Multi-unit Combinatorial Auction
spellingShingle Engineering::Computer science and engineering
Multi-project Scheduling
Multi-unit Combinatorial Auction
Song, Wen
Kang, Donghun
Zhang, Jie
Xi, Hui
A multi-unit combinatorial auction based approach for decentralized multi-project scheduling
description In industry, many problems are considered as the decentralized resource-constrained multi-project scheduling problem (DRCMPSP). Existing approaches encounter difficulties in dealing with large DRCMPSP cases while respecting the information privacy requirements of the project agents. In this paper, we tackle DRCMPSP by formulating it as a multi-unit combinatorial auction (Wellman et al. in Games Econ Behav 35(1):271–303, 2001), which does not require sensitive private project information. To handle the hardness of bidder valuation, we introduce the capacity query which uses different item capacity profiles to efficiently elicit valuation information from bidders. Based on the capacity query, we adopt two existing strategies (Gonen and Lehmann in Proceedings of the 2nd ACM conference on electronic commerce, pp 13–20, 2000) for solving multi-unit winner determination problems to find good allocations of the DRCMPSP auctions. The first strategy employs a greedy allocation process, which can rapidly find good allocations by allocating the bidder with the best answer after each query. The second strategy is based on a branch-and-bound process to improve the results of the first strategy, by searching for a better sequence of granting the bids from the bidders. Empirical results indicate that the two strategies can find good solutions with higher quality than state-of-the-art decentralized approaches, and scale well to large-scale problems with thousands of activities from tens of projects.
author2 School of Computer Science and Engineering
author_facet School of Computer Science and Engineering
Song, Wen
Kang, Donghun
Zhang, Jie
Xi, Hui
format Article
author Song, Wen
Kang, Donghun
Zhang, Jie
Xi, Hui
author_sort Song, Wen
title A multi-unit combinatorial auction based approach for decentralized multi-project scheduling
title_short A multi-unit combinatorial auction based approach for decentralized multi-project scheduling
title_full A multi-unit combinatorial auction based approach for decentralized multi-project scheduling
title_fullStr A multi-unit combinatorial auction based approach for decentralized multi-project scheduling
title_full_unstemmed A multi-unit combinatorial auction based approach for decentralized multi-project scheduling
title_sort multi-unit combinatorial auction based approach for decentralized multi-project scheduling
publishDate 2019
url https://hdl.handle.net/10356/83124
http://hdl.handle.net/10220/49103
_version_ 1681047427985965056