An adaptive memory programming framework for the resource-constrained project scheduling problem

The Resource-Constrained Project Scheduling Problem (RCPSP) is one of the most intractable combinatorial optimisation problems that combines a set of constraints and objectives met in a vast variety of applications and industries. Its solution raises major theoretical challenges due to its complexity, yet presenting numerous practical dimensions. Adaptive memory programming (AMP) is one of the most successful frameworks for solving hard combinatorial optimisation problems (e.g. vehicle routing and scheduling). Its success stems from the use of learning mechanisms that capture favourable solution elements found in high-quality solutions. This paper challenges the efficiency of AMP for solving the RCPSP, to our knowledge, for the first time in the literature. Computational experiments on well-known benchmark RCPSP instances show that the proposed AMP consistently produces high-quality solutions in reasonable computational times.     

An activity-list-based nested partitions algorithm for resource-constrained project scheduling

The resource-constrained project scheduling problem (RCPSP) has received wide attention. In this paper, an activity-list-based nested partitions algorithm (ALNP) is developed for solving the RCPSP and a P-ALNP is proposed to improve ALNP with local adjustment. In the algorithms, to improve the search efficiency, a partial double justification is employed as local search mechanism. The computational experiments on the PSPLIB and analysis on robustness of the algorithms show that ALNP outperforms the traditional serial scheduling scheme for solving the large-scale, complex RCPSPs, and P-ALNP can improve ALNP and obtain better results. P-ALNP is a competitive algorithm for solving the RCPSP.     

A novel branch-and-bound algorithm for the chance-constrained resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) has been widely studied during the last few decades. In real-world projects, however, not all information is known in advance and uncertainty is an inevitable part of these projects. The chance-constrained resource-constrained project scheduling problem (CC-RCPSP) has been recently introduced to deal with uncertainty in the RCPSP. In this paper, we propose a branch-and-bound (B&B) algorithm and a mixed integer linear programming (MILP) formulation that solve a sample average approximation of the CC-RCPSP. We introduce two different branching schemes and eight different priority rules for the proposed B&B algorithm. The computational results suggest that the proposed B&B procedure clearly outperforms both a proposed MILP formulation and a branch-and-cut algorithm from the literature.     

Hybrid genetic algorithm for bi-objective resource-constrained project scheduling

In this study, we considered a bi-objective, multi-project, multi-mode resource-constrained project scheduling problem. We adopted three objective pairs as combinations of the net present value (NPV) as a financial performance measure with one of the time-based performance measures, namely, makespan (C_max), mean completion time (MCT), and mean flow time (MFT) (i.e., minC_max/maxNPV, minMCT/maxNPV, and minMFT/maxNPV). We developed a hybrid non-dominated sorting genetic algorithm II (hybrid-NSGA-II) as a solution method by introducing a backward–forward pass (BFP) procedure and an injection procedure into NSGA-II. The BFP was proposed for new population generation and post-processing. Then, an injection procedure was introduced to increase diversity. The BFP and injection procedures led to improved objective functional values. The injection procedure generated a significantly high number of non-dominated solutions, thereby resulting in great diversity. An extensive computational study was performed. Results showed that hybrid-NSGA-II surpassed NSGA-II in terms of the performance metrics hypervolume, maximum spread, and the number of non-dominated solutions. Solutions were obtained for the objective pairs using hybrid-NSGA-II and three different test problem sets with specific properties. Further analysis was performed by employing cash balance, which was another financial performance measure of practical importance. Several managerial insights and extensions for further research were presented.     

Truncated branch-and-bound,schedule-construction,and schedule-improvement procedures for resource-constrained project scheduling

We present heuristic procedures for approximately solving large project scheduling problems with general temporal and resource constraints. In particular, we propose several truncated branch-and-bound techniques, priority-rule methods, and schedule-improvement procedures of types tabu search and genetic algorithm. A detailed experimental performance analysis compares the different heuristics devised and shows that large problem instances with up to 1000 activities and several resources can efficiently be solved with sufficient accuracy.

---

---

Received: July 26, 2000 / Accepted: May 15, 2001     

Hybridization of genetic algorithm and fully informed particle swarm for solving the multi-mode resource-constrained project scheduling problem

In this article, the genetic algorithm (GA) and fully informed particle swarm (FIPS) are hybridized for solving the multi-mode resource-constrained project scheduling problem (MRCPSP) with minimization of project makespan as the objective subject to resource and precedence constraints. In the proposed hybrid genetic algorithm–fully informed particle swarm algorithm (HGFA), FIPS is a popular variant of the particle swarm optimization algorithm. A random key and the related mode list representation schemes are used as encoding schemes, and the multi-mode serial schedule generation scheme (MSSGS) is considered as the decoding procedure. Furthermore, the existing mode improvement procedure in the literature is modified. The results show that the proposed mode improvement procedure remarkably improves the project makespan. Comparing the results of the proposed HGFA with other approaches using the well-known PSPLIB benchmark sets validates the effectiveness of the proposed algorithm to solve the MRCPSP.     

Multi-objective optimization for the multi-mode finance-based project scheduling problem

The finance-based scheduling problem (FBSP) is about scheduling project activities without exceeding a credit line financing limit. The FBSP is extended to consider different execution modes that result in the multi-mode FBSP (MMFBSP). Unfortunately, researchers have abandoned the development of exact models to solve the FBSP and its extensions. Instead, researchers have heavily relied on the use of heuristics and meta-heuristics, which do not guarantee solution optimality. No exact models are available for contractors who look for optimal solutions to the multi-objective MMFBSP. CPLEX, which is an exact solver, has witnessed a significant decrease in its computation time. Moreover, its current version, CPLEX 12.9, solves multi-objective optimization problems. This study presents a mixed-integer linear programming model for the multi-objective MMFBSP. Using CPLEX 12.9, we discuss several techniques that researchers can use to optimize a multi-objective MMFBSP. We test our model by solving several problems from the literature. We also show how to solve multi-objective optimization problems by using CPLEX 12.9 and how computation time increases as problem size increases. The small increase in computation time compared with possible cost savings make exact models a must for practitioners. Moreover, the linear programming-relaxation of the model, which takes seconds, can provide an excellent lower bound.     

An ant colony optimization heuristic for an integrated production and distribution scheduling problem

Make-to-order or direct-order business models that require close interaction between production and distribution activities have been adopted by many enterprises in order to be competitive in demanding markets. This article considers an integrated production and distribution scheduling problem in which jobs are first processed by one of the unrelated parallel machines and then distributed to corresponding customers by capacitated vehicles without intermediate inventory. The objective is to find a joint production and distribution schedule so that the weighted sum of total weighted job delivery time and the total distribution cost is minimized. This article presents a mathematical model for describing the problem and designs an algorithm using ant colony optimization. Computational experiments illustrate that the algorithm developed is capable of generating near-optimal solutions. The computational results also demonstrate the value of integrating production and distribution in the model for the studied problem.     

A scatter search heuristic for maximising the net present value of a resource-constrained project with fixed activity cash flows

In this paper, we present a meta-heuristic algorithm for the resource-constrained project scheduling problem with discounted cash flows. We assume fixed payments associated with the execution of project activities and develop a heuristic optimisation procedure to maximise the net present value of a project subject to the precedence and renewable resource constraints. We investigate the use of a bi-directional generation scheme and a recursive forward/backward improvement method from literature and embed them in a meta-heuristic scatter search framework. We generate a large dataset of project instances under a controlled design and report detailed computational results. The solutions and project instances can be downloaded from a website in order to facilitate comparison with future research attempts.     

A robust scheduling for the multi-mode project scheduling problem with a given deadline under uncertainty of activity duration

The problem of this paper deals with the multi-mode project scheduling problem under uncertainty of activity duration where only the renewable resources are taken into account and a given deadline has to be met at the cost of recruiting additional resources. A heuristic algorithm is employed to solve this problem, and to maintain the robustness of the baseline schedule, the concept of critical chain project management (CCPM) is applied in which a new definition to resource buffer is considered. A simulation methodology is used to determine the size and location of resource buffers in the schedules in which three different buffer sizes and three different uncertainty levels are considered. Results and analysis of the simulation outcomes illustrate that resource buffers are useful and should be simulated by the CCPM schedules, as they help to decrease the total duration of the project during implementation and meet the deadline of the project with more assurance.     

Coordinating supplier selection and project scheduling in resource-constrained construction supply chains

In this paper, we study the problem of coordinating supplier selection and project scheduling, motivated by a real-life operational challenge encountered in the construction industry. In particular, we consider a project network consisting of multiple concurrent projects, with the objective of minimising the total tardiness of all projects. These projects are independent in operation but are subject to shared suppliers and the final quality inspection by the same committee, which then leads to the need for project review sequencing. The earliest starting time of each activity in a project depends on the availability of required resources (both renewable and non-renewable), as well as the activity precedence constraints. We formulate this problem as a mixed integer linear programming model, and propose a mathematical programming-based heuristic to solve the model. The heuristic decomposes the model into subproblems, and solves the subproblems through an iterative process. Each subproblem has a much smaller size and can be solved quickly and independently. The information obtained in solving subproblems is used to guide the search process. Numerical examples show the computational effectiveness of the proposed heuristic, and the benefits of coordination.     

A model, heuristic procedure and decision support system for solving the movie shoot scheduling problem

Creating a movie shoot schedule is an important part of the movie production process. Even for a small movie project already 50 activities requiring 130 resources such as different actors, director, team, special effects and locations etc. have to be scheduled respecting complex constraints which may be imposed on single resources as well as on every activity. In this paper, we present the movie shoot scheduling problem and formulate a conceptual model. We present a metaheuristic approach for generating operational schedules, outline the modules of the decision support system Schedule This which we have developed and finally we shortly report practical experiences. Our experience from using the DSS in real movie shooting projects shows significant improvements with respect to faster and better scheduling as well as ad hoc re-scheduling.     

Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling

In this paper, Resource Constrained Scheduling (RCS) consists of scheduling activities on scarce resources, each activity may require more than one resource at a time, and each resource is available in the same quantity throughout the planning period. This paper described a methodology for RCS that can be easily adapted to consider different regular measures of performance. The solution approach is local search using a recent development published in the literature; namely, problem-space based neighborhoods. Computational results are encouraging when searching these spaces using simple local search techniques. Further improvements are explored through the use of a genetic algorithm. In both cases, close-to-optimal solutions are found for standard problems from the literature. The adaptability of the methodology is demonstrated using makespan and mean tardiness as performance measures.     

An effective methodology for the stochastic project compression problem

In this paper, we consider the problem of planning a complex project when task durations are random. Specifically, we consider the problem of deciding how much to compress tasks in order to minimize the expected total cost that is defined by the sum of direct, indirect, and incentive costs. We initially consider this problem under the assumption that task durations can be modeled by a negative exponential distribution although we later relax this assumption and show that our methodology can be applied to any general distribution. To solve this problem, we develop an effective heuristic algorithm that we call the Stochastic COmpression Project (SCOP) algorithm; the SCOP algorithm is straightforward to implement and our numerical tests indicate that the algorithm performs significantly better than previously reported heuristics. In addition, we compare our approach to solutions found using expected values embedded in a deterministic approach (an approach that is frequently used to solve this problem in practice). Using our results, we show that the deterministic approximation approach, such as the classic PERT model, provides biased results and should be avoided.     

A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem

Scheduling for the flexible job-shop is a very important issue in both fields of combinatorial optimization and production operations. However, due to combination of the routing and sequencing problems, flexible job-shop scheduling problem (FJSP) presents additional difficulty than the classical job-shop scheduling problem and requires more effective algorithms. This paper developed a filtered-beam-search-based heuristic algorithm (named as HFBS) to find sub-optimal schedules within a reasonable computational time for the FJSP with multiple objectives of minimising makespan, the total workload of machines and the workload of the most loaded machine. The proposed algorithm incorporates dispatching rules based heuristics and explores intelligently the search space to avoid useless paths, which makes it possible to improve the search speed. Through computational experiments, the performance of the presented algorithm is evaluated and compared with those of existing literature and those of commonly used dispatching rules, and the results demonstrate that the proposed algorithm is an effective and practical approach for the FJSP.     

Operation strategies for scheduling problems in project management

Abstract

This article analyzes different operation strategies in project management from an economic viewpoint and proposes a general procedure to schedule a project when inflation is either considered, with linear or ladder type, or not considered.     

A heuristic algorithm for master production scheduling problem with controllable processing times and scenario-based demands

Master production scheduling (MPS) is widely used by manufacturing industries in order to handle the production scheduling decisions in the production planning hierarchy. The classical approach to MPS assumes infinite capacity, fixed (i.e. non-controllable) processing times and a single pre-determined scenario for the demand forecasts. However, the deterministic optimisation approaches are sometimes not suitable for addressing the real-world problems with high uncertainty and flexibility. Accordingly, in this paper, we propose a new practical model for designing an optimal MPS for the environments in which processing times may be controllable by allocating resources such as facilities, energy or manpower. Due to the NP-hardness of our model, an efficient heuristic algorithm using local search technique and theory of constraints is developed and analysed. The computational results especially for large-sized test problems show that the average optimality gap of proposed algorithm is four times lower than that of exact solution using GAMS while it consumes also significantly smaller run times. Also, the analysis of computational results confirms that considering the controllable processing times may improve the solution space and help to more efficiently utilise the available resources. According to the model structure and performance of the algorithm, it may be proposed for solving large and complex real-world problems particularly the machining and steel industries.     

A simple and effective heuristic for the resource constrained project scheduling problem

This paper investigates the development and application of a simple heuristic to the resource constrained project scheduling problem (RCPSP). This computer heuristic, which is based on the COMSOAL heuristic, constructs a feasible solution at each iteration and chooses the best solution of several iterations. Although COMSOAL was originally a solution approach for the assembly-line balancing problem, it can be extended to provide solutions to the resource allocation problem. The Modified COMSOAL technique presented in this paper uses priority schemes intermittently with a random selection technique. This hybrid of randomness and priority scheme allows a good solution to be found quickly while not being forced into the same solution at each iteration. Several different priority schemes are examined within this research. The COMSOAL heuristic modified with the priority schemes heuristic was tested on several established test sets and the solution values are compared with both known optimal values and the results of several other resource allocation heuristics. In the vast majority of cases, the Modified COMSOAL heuristic outperformed the other heuristics in terms of both average and maximum percentage difference from optimal. The Modified COMSOAL heuristic seems to have several advantages over other RCPSP heuristics in that it is easy to understand, easy to implement, and achieves good results.     

An improved method for the hot strip mill production scheduling problem

In most research on the hot strip mill production scheduling problem (HSMPSP) arising in the steel industry, it is accepted that a schedule with lower penalty caused by jumps of width, hardness, and gauge will result in lower roller wear, so it is regarded as a better schedule. However, based on the analysis of production processes, it is realised that rolling each coil also cause roller wear. In order to assessing the roller wear associated with production scheduling more precisely, it is necessary to consider it as another factor besides those jumps, especially when complicated constraints are involved. In this paper, an improved method is proposed to quantify the expected wear of the rollers done by those jumps and rolling processes. Then the HSMPSP whose objective is to maximise the total length of all scheduled coils is formulated as a team orienteering problem with time windows and additional production constraints. A heuristic method combining an improved Ant Colony Extended algorithm with local search procedures dedicated to HSMPSP is developed. Finally, computational results on instances generated based on production data from an integrated steel mill in China indicate that the proposed algorithm is a promising solution specific to HSMPSP.