Author name cluster

Donghun Kang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

JAIR Journal 2019 Journal Article

A Sampling Approach for Proactive Project Scheduling under Generalized Time-dependent Workability Uncertainty

Wen Song
Donghun Kang
Jie Zhang
Zhiguang Cao
Hui Xi

In real-world project scheduling applications, activity durations are often uncertain. Proactive scheduling can effectively cope with the duration uncertainties, by generating robust baseline solutions according to a priori stochastic knowledge. However, most of the existing proactive approaches assume that the duration uncertainty of an activity is not related to its scheduled start time, which may not hold in many real-world scenarios. In this paper, we relax this assumption by allowing the duration uncertainty to be time-dependent, which is caused by the uncertainty of whether the activity can be executed on each time slot. We propose a stochastic optimization model to find an optimal Partial-order Schedule (POS) that minimizes the expected makespan. This model can cover both the time-dependent uncertainty studied in this paper and the traditional time-independent duration uncertainty. To circumvent the underlying complexity in evaluating a given solution, we approximate the stochastic optimization model based on Sample Average Approximation (SAA). Finally, we design two efficient branch-and-bound algorithms to solve the NP-hard SAA problem. Empirical evaluation confirms that our approach can generate high-quality proactive solutions for a variety of uncertainty distributions.

PDF Details DOI

AAAI Conference 2018 Conference Paper

Risk-Aware Proactive Scheduling via Conditional Value-at-Risk

Wen Song
Donghun Kang
Jie Zhang
Hui Xi

In this paper, we consider the challenging problem of riskaware proactive scheduling with the objective of minimizing robust makespan. State-of-the-art approaches based on probabilistic constrained optimization lead to Mixed Integer Linear Programs that must be heuristically approximated. We optimize the robust makespan via a coherent risk measure, Conditional Value-at-Risk (CVaR). Since traditional CVaR optimization approaches assuming linear spaces does not suit our problem, we propose a general branch-and-bound framework for combinatorial CVaR minimization. We then design an approximate complete algorithm, and employ resource reasoning to enable constraint propagation for multiple samples. Empirical results show that our algorithm outperforms stateof-the-art approaches with higher solution quality.

PDF Details

JAAMAS Journal 2017 Journal Article

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

Wen Song
Donghun Kang
Hui Xi

Abstract 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.

Details DOI

AAAI Conference 2017 Short Paper

A Sampling Based Approach for Proactive Project Scheduling with Time-Dependent Duration Uncertainty

Wen Song
Donghun Kang
Jie Zhang
Hui Xi

Most of the existing proactive scheduling approaches assume the durations of activities can be described by independent random variables that have no relation with time. We deal with the more challenging problem where the duration uncertainty is related to the scheduled time period. We propose a sampling based approach by extending the Consensus method from stochastic optimization. Experimental results show the effectiveness of our approach in solution quality and stability.

PDF Details

AAMAS Conference 2017 Conference Paper

Automatic Construction of Agent-based Simulation Using Business Process Diagrams and Ontology-based Models

Donghun Kang
Zhenchao C. Bing
Wen Song
Zehong Hu
Shuo Chen
Jie Zhang
Hui Xi

In this paper, we present a tool for the business users to analyze different business scenarios using business process diagrams and ontology-based models. The business scenarios involve different types of entities where the business process diagrams are suitable for describing entities’ behaviors. The ontology-based model is proposed to capture entities’ attributes and their relations in a hierarchical manner. The tool can automatically construct agent-based simulation models, which can be executed instantly on the agent-based simulation engine without the help of software developers.

PDF

AAMAS Conference 2017 Conference Paper

Proactive Project Scheduling with Time-dependent Workability Uncertainty

Wen Song
Donghun Kang
Jie Zhang
Hui Xi

Proactive scheduling can effectively handle activity duration uncertainty in real-world projects, by generating a baseline solution according to a prior stochastic knowledge. However, most of the previous approaches cannot deal with the activity duration uncertainty caused by time-dependent workability uncertainty. In this paper, we aim at finding a partialorder schedule (POS) that produces the minimum expected makespan on a given probability model of workability uncertainty. Since this is a hard discrete stochastic optimization problem, we propose an approximation approach based on Sample Average Approximation (SAA), and develop a branch-and-bound algorithm to optimally solve the SAA problem. Empirical results on benchmark problem instances and real-world distribution data show that our approach outperforms the best general-purpose POS generation approaches that do not exploit the stochastic knowledge. CCS Concepts •Computing methodologies → Planning under uncertainty;

PDF

AAMAS Conference 2016 Conference Paper

Decentralized Multi-Project Scheduling via Multi-Unit Combinatorial Auction

Wen Song
Donghun Kang
Jie Zhang
Hui Xi

In industry, many problems are considered as the Decentralized Resource-Constrained Multi-Project Scheduling Problem (DRCMPSP). Existing approaches encounter difficulties in dealing with large problems while preserving information privacy of project agents. In this paper, we propose a novel approach to solve DRCMPSP based on the multi-unit combinatorial auction, which can efficiently solve the problem without violating information privacy. It adopts a greedy resource allocation strategy with fixed resource cost to simplify computation required for project (bidder) and auctioneer agents. In addition, a bid modification step is incorporated to allow project agents to better utilize resources. Analysis and empirical results indicate that our approach outperforms state-of-the-art decentralized approaches in minimizing average project delay, and scales well to large problems with thousands of activities from tens of projects.

PDF