Project scheduling in distributed and dynamic environments

• Main Author: Song, Wen
• Other Authors: Zhang Jie
• Format: Theses and Dissertations
• Language: English
• Published: 2018
• Subjects: DRNTU::Engineering::Computer science and engineering
• Online Access: http://hdl.handle.net/10356/75889
• Institution: Nanyang Technological University

Project scheduling is an important task of modern business management. Classic project scheduling approaches assume a centralized and deterministic environment. However, today's manufacturing and management have entered into a more open and dynamic environment, which jeopardizes the effectiveness of traditional approaches. Two important practical factors that cause this issue are: 1) distributed management, where multiple decision makers with conflicting individual objectives are involved in the scheduling process, and 2) execution uncertainty, where projects are executed in dynamic environments containing various uncertainty sources. It is non-trivial to incorporate these practical factors since they make the project scheduling problems, which are already computationally intractable, even harder to solve. In this thesis, we provide effective approaches to address the two above-mentioned practical factors. We first study the scheduling problem in a distributed multi-project setting, where each project is controlled by an autonomous project agent. Classic centralized approaches cannot be applied in such a distributed multi-agent environment. However, existing distributed approaches encounter difficulties in dealing with large problems while preserving information privacy of project agents. We design a novel distributed approach based on multi-unit combinatorial auction, which does not require sensitive project information. To handle the hard valuation problem of the participators, we introduce the capacity query to efficiently elicit useful information from the project agents. We then design two allocation strategies that work with the capacity query to find good schedules, including a greedy strategy and a branch-and-bound heuristic. Empirical results indicate that the two strategies can find good solutions with higher quality than state-of-the-art distributed approaches, and scale well to large problem instances. We next study the risk-neutral proactive scheduling problem with uncertain activity durations. More specifically, we aim at finding an optimal project execution strategy that minimizes the expected makespan. Traditional approaches assume that the uncertain duration of an activity can be modeled as a random variable that does not depend on its start time. However, this can be violated in many real-world scenarios. In this work, we generalize the traditional time-independent model to support the time-dependent workability uncertainty, which has not been studied before and does make the activity duration time-dependent. Since the resultant discrete stochastic optimization problem is hard to solve, we propose a principled approximate approach based on Sample Average Approximation (SAA). By exploiting interesting problem properties, we design two efficient branch-and-bound algorithms to optimally solve the SAA problem. The effectiveness of our approach is verified by the experiments on multiple uncertainty models, including a real-world workability uncertainty distribution. Finally, we study the risk-aware proactive scheduling problem, which tries to optimize the robust makespan instead of expected makespan. Robust makespan is considered to be more practical in real-world applications, since it constraints the actual makespan within certain (probabilistic) risk level. State-of-the-art approaches for this problem are based on probabilistic constrained optimization, which leads to complex Mixed Integer Linear Programs that must be heuristically approximated. Instead, we propose a principled approximate approach by optimizing the robust makespan via Conditional Value-at-Risk (CVaR). However, existing CVaR optimization methods assume linear solution spaces, and hence are not applicable to our problem due to the combinatorial nature of resource-constrained scheduling. Hence, we design a general branch-and-bound framework for CVaR optimization in combinatorial spaces. We then instantiate this framework by adapting the branch-and-bound algorithms designed in our previous work to solve the risk-aware proactive problem. Results confirm that our approach scales well to a large number of samples, and can produce much better solutions than state-of-the-art approaches. To sum up, we have proposed a series of approaches to cope with challenging project scheduling problems with practical factors including distributed management and execution uncertainty. These contributions can also shed light on solving more complex and practical scheduling problems.