Author name cluster

Na Fu

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.

5 papers

2 author rows

IJCAI Conference 2017 Conference Paper

Mechanism Design for Strategic Project Scheduling

Pradeep Varakantham
Na Fu

Organizing large scale projects (e. g. , Conferences, IT Shows, F1 race) requires precise scheduling of multiple dependent tasks on common resources where multiple selfish entities are competing to execute the individual tasks. In this paper, we consider a well studied and rich scheduling model referred to as RCPSP (Resource Constrained Project Scheduling Problem). The key change to this model that we consider in this paper is the presence of selfish entities competing to perform individual tasks with the aim of maximizing their own utility. Due to the selfish entities in play, the goal of the scheduling problem is no longer only to minimize makespan for the entire project, but rather, to maximize social welfare while ensuring incentive compatibility and economic efficiency. We show that traditional VCG mechanism is not incentive compatible in this context and hence we provide two new practical mechanisms that extend on VCG. These new mechanisms referred to as Individual Completion based Payments (ICP) and Social Completion based Payments (SCP) provide strong theoretical properties including strategy proofness.

PDF Details

AAAI Conference 2016 Conference Paper

A Proactive Sampling Approach to Project Scheduling under Uncertainty

Pradeep Varakantham
Na Fu
Hoong Chuin Lau

Uncertainty in activity durations is a key characteristic of many real world scheduling problems in manufacturing, logistics and project management. RCPSP/max with durational uncertainty is a general model that can be used to represent durational uncertainty in a wide variety of scheduling problems where there exist resource constraints. However, computing schedules or execution strategies for RCPSP/max with durational uncertainty is NP-hard and hence we focus on providing approximation methods in this paper. We provide a principled approximation approach based on Sample Average Approximation (SAA) to compute proactive schedules for RCPSP/max with durational uncertainty. We further contribute an extension to SAA for improving scalability significantly without sacrificing on solution quality. Not only is our approach able to compute schedules at comparable runtimes as existing approaches, it also provides lower α-quantile makespan (also referred to as α-robust makespan) values than the best known approach on benchmark problems from the literature.

PDF Details

ICAPS Conference 2016 Conference Paper

Robust Partial Order Schedules for RCPSP/max with Durational Uncertainty

Na Fu
Pradeep Varakantham
Hoong Chuin Lau

In this work, we consider RCPSP/max with durational uncertainty. We focus on computing robust Partial Order Schedules (or, in short POS) which can be executed with risk controlled feasibility and optimality, i. e. , there is stochastic posteriori quality guarantee that the derived POS can be executed with all constraints honored and completion before robust makespan. To address this problem, we propose BACCHUS: a solution method on Benders Accelerated Cut Creation for Handling Uncertainty in Scheduling. In our proposed approach, we first give an MILP formulation for the deterministic RCPSP/max and partition the model into POS generation process and start time schedule determination. Then we develop Benders algorithm and propose cut generation scheme designed for effective convergence to optimality for RCPSP/max. To account for durational uncertainty, we extend the deterministic model by additional consideration of duration scenarios. In the extended MILP, the risks of constraint violation and failure to meet robust makespan are counted during POS exploration. We then approximate the uncertainty problem with computing a risk value related percentile of activity durations from the uncertainty distributions. Finally, we apply Pareto cut generation scheme and propose heuristics for infeasibility cuts to accelerate the algorithm process. Experimental results demonstrate that BACCHUS efficiently and effectively generates robust solutions for scheduling under uncertainty.

Details

ICAPS Conference 2010 Conference Paper

Towards Finding Robust Execution Strategies for RCPSP/max with Durational Uncertainty

Na Fu
Pradeep Varakantham
Hoong Chuin Lau

Resource Constrained Project Scheduling Problems with minimum and maximum time lags (RCPSP/max) have been studied extensively in the literature. However, the more realistic RCPSP/max problems - ones where durations of activities are not known with certainty - have received scant interest and hence are the main focus of the paper. Towards addressing the significant computational complexity involved in tackling RCPSP/max with durational uncertainty, we employ a local search mechanism to generate robust schedules. In this regard, we make two key contributions: (a) Introducing and studying the key properties of a new decision rule to specify start times of activities with respect to dynamic realizations of the duration uncertainty; and (b) Deriving the fitness function that is used to guide the local search towards robust schedules. Experimental results show that the performance of local search is improved with the new fitness evaluation over the best known existing approach.

Details

ICAPS Conference 2008 Conference Paper

Generating Robust Schedules Subject to Resource and Duration Uncertainties

Na Fu
Hoong Chuin Lau
Fei Xiao

We consider the Resource-Constrained Project Scheduling Problem with minimal and maximal time lags under resource and duration uncertainties. To manage resource uncertainties, we build upon the work of Lambrechts et al 2007 and develop a method to analyze the effect of resource breakdowns on activity durations. We then extend the robust local search framework of Lau et al 2007 with additional considerations on the impact of unexpected resource breakdowns to the project makespan, so that partial order schedules (POS) can absorb both resource and duration uncertainties. Experiments show that our proposed model is capable of addressing the uncertainty of resources, where the most robust POS is generated to minimize the robust makespan with statistical guarantee. Compared with prevailing methods, our method is also capable of achieving more feasible solutions with better robust makespan.

Details