The main goal of a scheduling process is to decide when and how to execute each of the project's activities. Despite large variety of researched scheduling problems, the majority of them can be described as generalisations of the resource-constrained project scheduling problem (RCPSP). Because of wide applicability and challenging difficulty, RCPSP has attracted vast amount of attention in the research community and great variety of heuristics have been adapted for solving it. Even though these heuristics are structurally different and operate according to diverse principles, they are designed to obtain only one solution at a time. In the recent researches on RCPSPs, it was proven that these kind of problems have complex multimodal fitness landscapes, which are characterised by a wide solution search spaces and presence of multiple local and global optima. The main goal of this thesis is twofold. Firstly, it presents a variation of the RCPSP that considers optimisation of projects in an uncertain environment where resources are modelled to adapt to their environment and, as the result of this, improve their efficiency. Secondly, modification of a novel evolutionary computation method Cuckoo Search (CS) is proposed, which has been adapted for solving combinatorial optimisation problems and modified to obtain multiple solutions. To test the proposed methodology, two sets of experiments are carried out. Firstly, the developed algorithm is applied to a real-life software development project. Secondly, the performance of the algorithm is tested on universal benchmark instances for scheduling problems which were modified to take into account specifics of the proposed optimisation model. The results of both experiments demonstrate that the proposed methodology achieves competitive level of performance and is capable of finding multiple global solutions, as well as prove its applicability in real-life projects.

This paper analyses the current state of research regarding solution methods dealing with resource-constrained project scheduling problems. The intention is to present a concentrated survey and brief scientific overview on models, their decision variables and constraints as well as current solution methods in the field of project scheduling. The allocation of scarce resources among multiple projects with different, conflicting decision variables is a highly difficult problem in order to achieve an optimal schedule which meets all (usually different) of the projects’ objectives. Those projects, e.g. the assembly of complex machinery and goods, consume many renewable, e.g. workforce/staff, and non-renewable, e.g. project budget, resources. Each single process within these projects can often be performed in different ways – so called execution modes can help to make a schedule feasible. On the other hand the number of potential solutions increases dramatically through this fact. Additional constraints, e.g. min/max time lags, preemption or specific precedence relations of activities, lead to highly complex problems which are NP-hard in the strong sense.

This dissertation examines a profit-maximizing project selection and scheduling problem. Assume that a set of potentially profitable projects are available, yet limited available resources may not allow all of them to be pursued. Profit profiles for projects are assumed to be non-increasing functions of project completion times, i.e. profit returns are sensitive to time-to-market. Decision needs to be made on which sub-set of projects should be chosen and how resources should be allocated to these projects such that the total profit is maximized.Formal mathematical models are formulated for various versions of the problem, including such ones incorporating a third team formation aspect. Structure of the problem is examined and insights are gained regarding prioritization of project, specifically. Although prioritization is sub-optimal in general, heuristic solution methods based on prioritization are pursued, since the scheduling sub-problem itself is NP-hard.A decomposition heuristic framework is first proposed to obtain good solutions using minimum computational time. Sets of test instances are generated using project network data from well-known source in the literature. Computational runs reveal that three priority rules achieve significantly better profits than the benchmarking random priority rule.Improving upon the prioritization based decomposition heuristic, an implicit enumeration is proposed. This algorithm does not examine all priority sequences, yet guarantees an optimal priority sequence when the computation is completed. Several fathoming rules are proposed to cut back computational time effectively. Comparison to the profits achieved by the best priority rule and the benchmarking random priority rule shows a significant improvement on profits, yet at a cost of reasonable added computation time.Future research areas include identifying general conditions under which prioritization of projects would lead us to an optimal solution. Developing better upper bounds for the implicit enumeration scheme is also of interest. The team formation aspect has yet to be treated computationally. It would also be of interest to consider how synergy deviation information may be fed back to the earlier stages of project selection and scheduling decision. Trade-off between profit and team synergy may also be considered in the future.

The main goal of a scheduling process is to decide when and how to execute each of the project’s activities. Despite large variety of researched scheduling problems, the majority of them can be described as generalisations of the resource-constrained project scheduling problem (RCPSP). Because of wide applicability and challenging difficulty, RCPSP has attracted vast amount of attention in the research community and great variety of heuristics have been adapted for solving it. Even though these heuristics are structurally different and operate according to diverse principles, they are designed to obtain only one solution at a time. In the recent researches on RCPSPs, it was proven that these kind of problems have complex multimodal fitness landscapes, which are characterised by a wide solution search spaces and presence of multiple local and global optima. The main goal of this thesis is twofold. Firstly, it presents a variation of the RCPSP that considers optimisation of projects in an uncertain environment where resources are modelled to adapt to their environment and, as the result of this, improve their efficiency. Secondly, modification of a novel evolutionary computation method Cuckoo Search (CS) is proposed, which has been adapted for solving combinatorial optimisation problems and modified to obtain multiple solutions. To test the proposed methodology, two sets of experiments are carried out. Firstly, the developed algorithm is applied to a real-life software development project. Secondly, the performance of the algorithm is tested on universal benchmark instances for scheduling problems which were modified to take into account specifics of the proposed optimisation model. The results of both experiments demonstrate that the proposed methodology achieves competitive level of performance and is capable of finding multiple global solutions, as well as prove its applicability in real-life projects.

Project managers are faced with the challenging task of managing an environment filled with uncertainties that may lead to multiple disruptions during project execution. In particular, they are frequently confronted with planning for routine and non-routine unplanned work: known, identified, tasks that may or may not occur depending upon various, often unpredictable, factors. This problem is known as the stochastic task insertion problem, where tasks of deterministic duration occur stochastically. Traditionally, project managers may include an extra margin within deterministic task times or an extra time buffer may be allotted at the end of the project schedule to protect the final project completion milestone. Little scientific guidance is available to better integrate buffers strategically into the project schedule. Motivated by the Critical Chain and Buffer Management approach of Goldratt, this research identifies, defines, and demonstrates new buffer sizing techniques to improve project duration and stability metrics associated with the stochastic resource constrained project scheduling problem with stochastic task insertions. Specifically, this research defines and compares partial buffer sizing strategies for projects with varying levels of resource and network complexity factors as well as the level and location of the stochastically occurring tasks. Several project metrics may be impacted by the stochastic occurrence or non-occurrence of a task such as the project makespan and the project stability. New duration and stability metrics are developed in this research and are used to evaluate the effectiveness of the proposed buffer sizing techniques. These "robustness measures" are computed through the comparison of the characteristics of the initial schedule (termed the infeasible base schedule), a modified base schedule (or as-run schedule) and an optimized version of the base schedule (or perfect knowledge schedule). Seven new buffer sizing techniques are introduced in this research. Three are based on a fixed percentage of task duration and the remaining four provide variable buffer sizes based upon the location of the stochastic task in the schedule and knowledge of the task stochasticity characteristic. Experimental analysis shows that partial buffering produces improvements in the project stability and duration metrics when compared to other baseline scheduling approaches. Three of the new partial buffering techniques produced improvements in project metrics. One of these partial buffers was based on a fixed percentage of task duration and the other two used a variable buffer size based on knowledge of the location of the task in the project network. This research provides project schedulers with new partial buffering techniques and recommendations for the type of partial buffering technique that should be utilized when project duration and stability performance improvements are desired. When a project scheduler can identify potential unplanned work and where it might occur, the use of these partial buffer techniques will yield a better estimated makespan. Furthermore, it will result in less disruption to the planned schedule and minimize the amount of time that specific tasks will have to move to accommodate the unplanned tasks.

Yes / An Improved Discrete Cuckoo Search (IDCS) is proposed in this paper to solve resource-constrained project scheduling problems (RCPSPs). The original Cuckoo Search (CS) was inspired by the breeding behaviour of some cuckoo species and was designed specifically for application in continuous optimisation problems, in which the algorithm had been demonstrated to be effective. The proposed IDCS aims to improve the original CS for solving discrete scheduling problems by reinterpreting its key elements: solution representation scheme, Lévy flight and solution improvement operators. An event list solution representation scheme has been used to present projects and a novel event movement and an event recombination operator has been developed to ensure better quality of received results and improve the efficiency of the algorithm. Numerical results have demonstrated that the proposed IDCS can achieve a competitive level of performance compared to other state-of-the-art metaheuristics in solving a set of benchmark instances from a well-known PSPLIB library, especially in solving complex benchmark instances. / Partially funded by the Innovate UK project HARNET – Harmonised Antennas, Radios and Networks under contract no. 100004607.

Yes / In this paper, a new population-based and nature-inspired metaheuristic algorithm, Discrete Flower Pollination Algorithm (DFPA), is presented to solve the Resource Constrained Project Scheduling Problem (RCPSP). The DFPA is a modification of existing Flower Pollination Algorithm adapted for solving combinatorial optimization problems by changing some of the algorithm's core concepts, such as flower, global pollination, Lévy flight, local pollination. The proposed DFPA is then tested on sets of benchmark instances and its performance is compared against other existing metaheuristic algorithms. The numerical results have shown that the proposed algorithm is efficient and outperforms several other popular metaheuristic algorithms, both in terms of quality of the results and execution time. Being discrete, the proposed algorithm can be used to solve any other combinatorial optimization problems. / Innovate UK / Awarded 'Best paper of the Month'

Der Planungsprozess des Produktionsablaufes ist insbesondere in personalintensiven Bereichen durch einen hohen Komplexitätsgrad gekennzeichnet. Dies gilt nicht allein für die Domäne der Fertigung von Industriegütern, sondern ist überall dort charakteristisch, wo projektähnliche Aufgaben und Tätigkeiten im Kurzfristbereich hinsichtlich Ressourcenzuteilung determiniert werden müssen. Personal ist hierbei weitaus weniger homogen, als dies auf andere Ressourcentypen zutrifft. Daher gilt es der Heterogenität der Prozesse und Strukturen unter Beachtung individuell ausgeprägter Eigenschaften und Fähigkeiten des Personals einen quantitativ beschreibbaren und damit operationali-sierbaren Rahmen zu geben. Die Komplexität einer personalbezogenen, zielfunktionsorientierten Zuteilungsentscheidung kann im Kontext der Kapazitätsplanung damit signifikant reduziert werden.

This thesis deals with the description of the state of resource-constrained project scheduling problem. It defines the formal problem and its complexity. It also describes variants of this problem. Algorithms for solving RCPSP are presented. Heuristic genetic algorithm GARTH is analyzed in depth. The implementation of prototypes solving RCPSP using GARTH is outlined. Several improvements to the original algorithm are designed and evaluated.

This paper analyses the current state of research regarding solution methods dealing with resource-constrained project scheduling problems. The intention is to present a concentrated survey and brief scientific overview on models, their decision variables and constraints as well as current solution methods in the field of project scheduling. The allocation of scarce resources among multiple projects with different, conflicting decision variables is a highly difficult problem in order to achieve an optimal schedule which meets all (usually different) of the projects’ objectives. Those projects, e.g. the assembly of complex machinery and goods, consume many renewable, e.g. workforce/staff, and non-renewable, e.g. project budget, resources. Each single process within these projects can often be performed in different ways – so called execution modes can help to make a schedule feasible. On the other hand the number of potential solutions increases dramatically through this fact. Additional constraints, e.g. min/max time lags, preemption or specific precedence relations of activities, lead to highly complex problems which are NP-hard in the strong sense.