Search

Addressing the resource constraints, such as manpower and equipment, faced by mine backfilling operations, this study proposed an optimization model for backfill scheduling based on the Resource-Constrained Project Scheduling Problem (RCPSP). The model considered backfilling's multi-process, multi-task, and multi-resource characteristics, aiming to minimize total delay time. Constraints included operational limits, resource requirements, and availability. The goal was to determine optimal resource configurations for each stope's backfilling steps. A heuristic genetic algorithm (GA) was employed for solution. To handle equipment unavailability, a new encoding/decoding algorithm ensured resource availability and continuous operations. Case verification using real mine data highlights the advantages of the model, showing a 20.6% decrease in completion time, an 8 percentage point improvement in resource utilization, and a 47.4% reduction in overall backfilling delay time compared to traditional methods. This work provides a reference for backfilling scheduling in similar mines and promotes intelligent mining practices. [ABSTRACT FROM AUTHOR]

In this paper we deal with a complex real world scheduling problem closely related to the well-known Resource-Constrained Project Scheduling Problem (RCPSP). The problem concerns industrial test laboratories in which a large number of tests are performed by qualified personnel using specialised equipment, while respecting deadlines and other constraints. We present different constraint programming models and search strategies for this problem. Furthermore, we propose a Very Large Neighborhood Search approach based on our CP methods. Our models are evaluated using CP solvers and a MIP solver both on real-world test laboratory data and on a set of generated instances of different sizes based on the real-world data. Further, we compare the exact approaches with VLNS and a Simulated Annealing heuristic. We could find feasible solutions for all instances and several optimal solutions and we show that using VLNS we can improve upon the results of the other approaches. [ABSTRACT FROM AUTHOR]

We study a rescheduling problem in paced aircraft assembly lines with specific resource and precedence constraints. We develop an efficient model based on constraint programming to provide rapidly rescheduling solutions to managers. We propose original optimisation criteria and show that their use outperforms the classic criteria in terms of solution time and quality. We validate our approach through experiments run on industrial problem instances of large scale and derive useful managerial insights from this experimental study. [ABSTRACT FROM AUTHOR]

The concept of anchored solutions is proposed as a new robust optimization approach to the Resource-Constrained Project Scheduling Problem (RCPSP) under processing times uncertainty. The Anchor-Robust RCPSP is defined, to compute a baseline schedule with bounded makespan, sequencing decisions, and a max-size subset of jobs with guaranteed starting times, called anchored set. It is shown that the Adjustable-Robust RCPSP from the literature fits within the framework of anchored solutions. The Anchor-Robust RCPSP and the Adjustable-Robust RCPSP can benefit from each other to find both a worst-case makespan, and a baseline schedule with an anchored set. A dedicated graph model for anchored solutions is reviewed for budgeted uncertainty. Compact MIP reformulations are derived for both the Adjustable-Robust RCPSP and the Anchor-Robust RCPSP. Dedicated heuristics are designed based on the graph model. For both problems, the efficiency of the proposed MIP reformulations and heuristic approaches is assessed through numerical experiments on benchmark instances. [ABSTRACT FROM AUTHOR]

The disaster information collection mission should be executed after the disaster occurs to provide details for the decision-makers. During the execution of the information collection mission, some disruptions may occur and prevent the resource used for information collection from completing the mission as planned. It is difficult for decision-makers to make reactive resource scheduling plan that optimize the mission's execution time, quality, and cost at the same time under such circumstances. This article focuses on designing the reactive decision support algorithm for the disaster information collection resource scheduling, which aims to provide multi high-quality scheduling plans for decision-makers to choose. The problem studied in this article is modeled as an extension of Resource-Constrained Project Scheduling Problem (RCPSP). First, the basic problem formulation for a normal schedule and two disruption recovery models are presented. Second, a novel framework of a parallel pareto local search based on decomposition is designed to repair the schedule within the time limit. Third, two solution acceptance criteria based on constraint handling and negative correlation are specially designed to maintain high-quality population with diversity. The experiments show that the proposed method outperforms the other competitors with respect to Inverted Generational Distance, Spacing, and Hypervolume, which means that the proposed method can help decision-makers to make better decisions. [ABSTRACT FROM AUTHOR]

Abstract The disaster information collection mission should be executed after the disaster occurs to provide details for the decision-makers. During the execution of the information collection mission, some disruptions may occur and prevent the resource used for information collection from completing the mission as planned. It is difficult for decision-makers to make reactive resource scheduling plan that optimize the mission’s execution time, quality, and cost at the same time under such circumstances. This article focuses on designing the reactive decision support algorithm for the disaster information collection resource scheduling, which aims to provide multi high-quality scheduling plans for decision-makers to choose. The problem studied in this article is modeled as an extension of Resource-Constrained Project Scheduling Problem (RCPSP). First, the basic problem formulation for a normal schedule and two disruption recovery models are presented. Second, a novel framework of a parallel pareto local search based on decomposition is designed to repair the schedule within the time limit. Third, two solution acceptance criteria based on constraint handling and negative correlation are specially designed to maintain high-quality population with diversity. The experiments show that the proposed method outperforms the other competitors with respect to Inverted Generational Distance, Spacing, and Hypervolume, which means that the proposed method can help decision-makers to make better decisions.

The Test Laboratory Scheduling Problem (TLSP) is a real-world scheduling problem that extends the well-known Resource-Constrained Project Scheduling Problem (RCPSP) by several new constraints. Most importantly, the jobs have to be assembled out of several smaller tasks by the solver, before they can be scheduled. In this paper, we introduce different metaheuristic solution approaches for this problem. We propose four new neighborhoods that modify the grouping of tasks. In combination with neighborhoods for scheduling, they are used by our metaheuristics to produce high-quality solutions for both randomly generated and real-world instances. In particular, Simulated Annealing managed to find solutions that are competitive with the best known results and improve upon the state-of-the-art for larger instances. The algorithm is currently used for the daily planning of a large real-world laboratory. [ABSTRACT FROM AUTHOR]

Resource-constrained project scheduling problem(RCPSP) is the most representative scheduling problem,which is an abstract representation of many practical scheduling problems.It belongs to the NP-hard problem and is difficult to obtain the global optimal solution for large-scale problems.In this paper,an integer programming model is proposed.By decomposing the model into a constrained master problem and some subproblems,a column generation method is designed for the solving of the linear relaxation model,and then the integer solution of the problem is found through branch & price.In the process of solving,relaxation variables are introduced to solve the pseudo infeasibility of the model.Furthermore,pruning strategy,branch strategy,and two methods for reducing the solution space according to different situations are designed.On the PSPLIB data set,for the problems with 30 processes,the current optimal solutions can be obtained in 10 minutes for 301 out of 480 instances.For the problems with 60 processes,the current optimal solutions can be obtained in 20 minutes for 269 out of 480 instances.For the problem with 90 processes,the current optimal solutions can be obtained in 30 minutes for 263 out of 480 instances.At the same time,by using the strategies of reducing the solution space,the number of timeout instances decreases significantly,and the performance of the optimized initial solution is significantly improved.Experimental results show that the proposed algorithm is effective.

Effective project planning is crucial for the successful execution of complex industrial projects, as it can significantly reduce costs and enhance overall efficiency. However, applying precise methods for obtaining optimal project plans is often limited to small activity graphs, rendering them impractical for real-world scenarios. To address this issue, heuristic and metaheuristic algorithms have been the focus of extensive research over the past few decades. This study explores an extended problem formulation known as the Multiple Contractor-Resource Project Scheduling Problem (MC-MRCPSP). This formulation extends beyond the basic problem structure, incorporating various constraints typically encountered in industrial project scheduling. To tackle this challenging optimization problem, we propose a novel hybrid algorithm that combines a fine-tuned genetic algorithm with an advanced tabu search. This approach strikes an optimal balance between exploration and exploitation of the solution space, leading to enhanced project plan optimization. Through comprehensive experiments and evaluations, we demonstrate the effectiveness of our proposed approach. Compared to a purely genetic algorithm, our hybrid solution achieves a 38% improvement in project plan optimization. These results underscore our study's significant contribution to project planning and lay the groundwork for future advancements in MC-MRCPSP solutions. Ultimately, our research brings us closer to improved resource utilization, cost reduction, and enhanced efficiency in managing complex industrial projects. [ABSTRACT FROM AUTHOR]

In the environment of scientific and technological innovation, the human and material resources that can reach the project threshold are often limited. For enterprise projects that require high R&D and production level to produce rapid emergency resources, they often face the problem of difficult effective allocation of emergency resources, resulting in project delay. Therefore, in the process of high-tech projects, it is necessary to deal with the lack of emergency scientific and technological resources. Therefore, based on the particle swarm optimization algorithm which is easy to be realized by scientific and technological innovation enterprises, this study improves its two shortcomings of easy local optimization and low performance, constructs the CD-PSO project scheduling model, verifies the performance of the improvement points, and tests the performance of the model in the actual project case of enterprise rapid emergency resource scheduling. The results show that the optimal solution of CD-PSO model in the three sample sets is higher than that of D-PSO model in the same group, and the average scheduling duration is the shortest, which is 350 days, and the proportion of reaching the optimal duration is 100%. The operation effect is obviously better than other scheduling models. The CD-PSO project scheduling model designed in this study is easier to implement and can calculate the optimal solution of the first project more efficiently. It not only has excellent performance, but also has a strong popularization foundation. [ABSTRACT FROM AUTHOR]

Automated scheduling solutions are tremendously important for the efficient operation of industrial laboratories. The Test Laboratory Scheduling Problem (TLSP) is an extension of the well-known ResourceConstrained Project Scheduling Problem (RCPSP) and captures the specific requirements of such laboratories. In addition to several new scheduling constraints, it features a grouping phase, where the jobs to be scheduled are assembled from smaller units. In this work, we introduce an innovative scheduling system that allows the efficient and flexible generation of schedules for TLSP. It features a new Constraint Programming model that covers both the grouping and the scheduling aspect, as well as a hybrid Very Large Neighborhood Search that internally uses the CP model. Our experimental results on generated and real-world benchmark instances show that good results can be obtained even compared to settings which have a good grouping already provided, including several new best known solutions for these instances. Our algorithms for TLSP have been successfully implemented in a real-world industrial test laboratory. We provide a detailed description of the deployed system as well as additional useful soft constraints supported by the solvers and general lessons learned. This includes a discussion of the choice of soft constraint weights, with an analysis on the impact and relation of different objectives to each other. Our experiments show that some soft constraints complement each other well, while others require explicit trade-offs via their relative weights. [ABSTRACT FROM AUTHOR]

Resource constraint project scheduling problem (RCPSP) is one of the most important problems in the scheduling environment. This paper introduces a new framework to collect the activities' duration and resource requirement by group decision-making, solve the RCPSP with variable durations, and obtain the buffer to protect the schedule. Firstly, the duration and resources of the project's activities are determined by a new expert weighting method. In the group decision-making, hybrid projection measure is introduced to construct the aggregated decision about some RCPSP parameters. The hybrid projection includes the projection, normalized projection, and bi-directional projection. In the second step, a RCPSP model is presented where the duration of activities can change within certain intervals. Thus, the problem is called the RCPSP with variable durations. The intervals for activities' duration and resource requirements are obtained from the group decision-making in the first step. Genetic algorithm and vibration damping optimization are applied to solve the RCPSP with variable durations. In the third step, the project's buffer is determined to protect the schedule. In this step, the intervals for activities' duration are converted into interval-valued fuzzy (IVF) numbers and the buffer sizing method is extended using IVF numbers. Finally, the presented framework is solved for a practical example and the results are reported. [ABSTRACT FROM AUTHOR]

Constructive Heuristics for the Resource Constraint Project Scheduling Problems (RCPSP) are preferred scheduling methods when the project network broadens. Then, to generate a good schedule from these heuristics, the priority list used in the algorithm becomes crucial. This paper proposes a Cluster-Based Priority List (CB-PL) method for generating lists to improve makespans of schedules obtained from constructive heuristics. The method creates more intellectual priority lists that generate lower makespans. The approach is built and fine-tuned upon the existing relative literature. The performance of the method is measured by comparing the makespan results. The experiment for the comparison uses serial and parallel scheduling schemes with seven priority rules. Then the experiment is tested through a set of benchmark data. Finally, schedules obtained through the CB-PL showed significant makespan reductions and increases in an overall number of better solutions. [ABSTRACT FROM AUTHOR]

The scheduling process that aims to assign tasks tomembers is a difficult job in project management. It plays a prerequisite role in determining the project's quality and sometimes winning the bidding process. This study aims to propose an approach based on multi-objective combinatorial optimization to do this automatically. The generated schedule directs the project to be completed with the shortest critical path, at the minimum cost, while maintaining its quality. There are several real-world business constraints related to human resources, the similarity of the tasks added to the optimizationmodel, and the literature's traditional rules. To support the decision-maker to evaluate different decision strategies, we use compromise programming to transform multiobjective optimization (MOP) into a single-objective problem. We designed a genetic algorithm scheme to solve the transformed problem. The proposed method allows the incorporation of the model as a navigator for search agents in the optimal solution search process by transferring the objective function to the agents' fitness function. The optimizer can effectively find compromise solutions even if the user may or may not assign a priority to particular objectives. These are achieved through a combination of nonpreference and preference approaches. The experimental results show that the proposed method worked well on the tested dataset. [ABSTRACT FROM AUTHOR]

Due to complex sets of interrelated activities in aircraft heavy maintenance (AHM), many airlines have to deal with substantial aircraft maintenance downtime. The scheduling problem in AHM is regarded as an NP-hard problem. Using exact algorithms can be time-consuming or even infeasible. This article proposes genetic algorithms for solving the resource-constrained project scheduling problem (RCPSP) in AHM. The objective of the study was to minimise the makespan of the maintenance plan. The proposed algorithms applied five heuristic dispatching rules to generate an initial population based on activity list formation. Resource allocation methods for RCPSP - earliest start time (EST) and workgroup and earliest start time (WEST) - were used to evaluate the fitness value. The elitist and roulette wheel methods were applied in the selection process. The sequences of the activity lists were then iteratively improved by crossover and mutation operations. The results show that the proposed algorithms perform efficiently compared to the existing solutions in terms of computational time and resource allocation. [ABSTRACT FROM AUTHOR]

In this study, a mixed-integer mathematical model has been presented for the Multi-Skilled Resource-Constrained Multi-Project Scheduling Problem (MSRCMPSP), where the dexterity of workers can be improved via two ways: (1) Cooperating with more proficient co-workers, and (2) Practicing the possessed skills. The model aims to determine the start and finish times of activities considering the dexterity improvement of workforces. This research presents a Modified discrete variant of the Biogeography-Based Optimization (MBBO) algorithm to solve the model and to minimize the total required duration to complete all projects. The MBBO embraces two novel migration procedures, a new mutation process, and a new habitat selection operator. On several test instances and on a case study, the efficacy of the MBBO has been put to examination in comparison to four other meta-heuristics. The MBBO has overpowered other methodologies in terms of most of the assessment criteria. The obtained results have revealed that the dexterity improvement of workers significantly improves the total required duration to complete all projects. This research and its outputs can be helpful for the researchers who work on project scheduling models. Moreover, this study can inspire future project scheduling formulations, where the dexterity of human resources is affected by the learning phenomenon. • A formulation for multi-skill resource-constrained multi-project scheduling was proposed. • The workers' dexterity can evolve through two ways of learning. • A discrete biogeography-based optimization (BBO) algorithm was developed. • Two migration procedures have been proposed for BBO in order to generate new habitats. • A new habitat selection operator has been designed for BBO. [ABSTRACT FROM AUTHOR]

This paper addresses the multi-mode multi-skilled resource-constrained project scheduling problem. Activities of real world projects often require more than one skill to be accomplished. Besides, in many real-world situations, the resources are multi-skilled workforces. In presence of multi-skilled resources, it is required to determine the combination of workforces assigned to each activity. Hence, in this paper, a mixed-integer formulation called the MMSRCPSP is proposed to minimize the completion time of project. Since the MMSRCPSP is strongly NP-hard, a new genetic algorithm is developed to find optimal or near-optimal solutions in a reasonable computation time. The proposed genetic algorithm (PGA) employs two new strategies to explore the solution space in order to find diverse and high-quality individuals. Furthermore, the PGA uses a hybrid multi-attribute decision making (MADM) approach consisting of the Shannon’s entropy method and the VIKOR method to select the candidate individuals for reproduction. The effectiveness of the PGA is evaluated by conducting numerical experiments on several test instances. The outputs of the proposed algorithm is compared to the results obtained by the classical genetic algorithm, harmony search algorithm, and Neurogenetic algorithm. The results show the superiority of the PGA over the other three methods. To test the efficiency of the PGA in finding optimal solutions, the make-span of small size benchmark problems are compared to the optimal solutions obtained by the GAMS software. The outputs show that the proposed genetic algorithm has obtained optimal solutions for 70% of test problems.

In this paper we introduce a complex scheduling problem that arises in a real-world industrial test laboratory, where a large number of activities has to be performed using qualified personnel and specialized equipment, subject to time windows and several other constraints. The problem is an extension of the well-known Resource-Constrained Project Scheduling Problem and features multiple heterogeneous resources with very general availability restrictions, as well as a grouping phase, where the jobs have to be assembled from smaller units. We describe an instance generator for this problem and publicly available instance sets, both randomly generated and real-world data. Finally, we present and evaluate different metaheuristic approaches to solve the scheduling subproblem, where the assembled jobs are already provided. Our results show that Simulated Annealing can be used to achieve very good results, in particular for large instances, where it is able to consistently find better solutions than a state-of-the-art constraint programming solver within reasonable time. [ABSTRACT FROM AUTHOR]

Abstract We consider a novel generalization of the resource-constrained project scheduling problem (RCPSP). Unlike many established approaches for the RCPSP that aim to minimize the makespan of the project for given static capacity constraints, we consider the important real-life aspect that capacity constraints can often be systematically modified by temporarily assigning costly additional production resources or using overtime. We, furthermore, assume that the revenue of the project decreases as its makespan increases and try to find a schedule with a profit-maximizing makespan. Like the RCPSP, the problem is $$\mathcal {NP}$$ NP -hard, but unlike the RCPSP, it turns out that an optimal schedule does not have to be among the set of so-called active schedules. Scheduling such a project is a formidable task, both from a practical and a theoretical perspective. We develop, describe, and evaluate alternative solution encodings and schedule decoding mechanisms to solve this problem within a genetic algorithm framework and we compare the solutions obtained to both optimal reference values and the results of a commercial local search solver called LocalSolver.

Complex construction projects are prone to inherent uncertainty which stems from internal and external project factors. As a response to prevailing uncertainty, a new resource-constrained surrogate measure that considers appropriate time distribution of floats through the structure of a schedule is suggested. The proposed surrogate measure considers both the precedence and resource relations while maximising the resilience of baseline schedules for construction projects. Moreover, as the time dimension of uncertainty propagation through the project time is considered, floats distribution is properly adjusted to absorb perturbations in a schedule. This way, resource allocation is considered along with the scheduling phase, making the resilient construction planning more comprehensive. A bi-objective optimisation model is proposed in the form of Resource-Constrained Project Scheduling Problem (RCPSP) to enhance the resilience of a project schedule by maximising the surrogate measure through one of the objective functions, while the other objective function strives to minimise project duration. As the resilience in the context of project scheduling refers to maximised absorption of project perturbations, a schedule with improved resilience capacity is expected to be more stable when it comes to the project execution phase. [ABSTRACT FROM AUTHOR]

We study the problem to simultaneously decide on the structures and the schedules for an entire portfolio of flexible projects. The projects are flexible as alternative technologies and procedures can be used to achieve the respective project task. The choice between different technologies and procedures affects the activities to be implemented and thus the precedence relations, i.e., the structure of the project. The different projects have given due dates with specific delay payments and compete for scarce resources. In this situation, project structure decisions and scheduling decisions are highly intertwined and have to be made simultaneously in order to achieve the assumed objective of minimizing the delay payments for the entire project portfolio. The problem is formally stated and solved via novel and problem-specific genetic algorithms. The performance of the new algorithms is evaluated with respect to speed and accuracy in a systematic and comprehensive numerical study. [ABSTRACT FROM AUTHOR]

In recent years, the study of Resource Constrained Project Scheduling Problem RCPSP which as a well-known NP-hard problem in project management and operational research is taking substantial interest. The present work investigates a new RCPSP extension in multi-site environments with resource pooling between different sites. This extension considers two types of resources: fixed and mobile resources. New constraints are taken into account like transfer times of mobile resources and the decision on which site a task is carried out. We propose a new Particle Swarm Optimization-based solution to deal with this RCPSP variant aiming at minimizing the total project Makespan. The proposed algorithm uses a Valid Particle Generator to produce feasible schedules. As well, inertia weight is adaptively tuned to realize a trade-off between diversification and intensification. Our solution has been tested on a set of newly created benchmarks to reveal very promising results. [ABSTRACT FROM AUTHOR]

Uncertainty has become an inevitable aspect of project scheduling. We study the resource-constrained project scheduling problem with stochastic durations. One of the most studied approaches to deal with stochastic durations is that of proactive and reactive scheduling. Previous researches often studied proactive and reactive scheduling rather separately and ignored the fact that proactive scheduling and reactive scheduling are closely connected. In this paper, we address this ignored aspect by formulating an integrated proactive and reactive scheduling problem with a combined cost function which includes a baseline schedule cost as well as costs of a series of reactions. We introduce solutions to this integrated problem as proactive-and-reactive policies (PR-policies). We discuss that PR-policies are more powerful and informative than their traditional counterparts (i.e., a combination of a baseline schedule and a reactive policy), provide better stability and robustness, and are more flexible when extra constraints are added to the problem. We also propose four dynamic programming based models (Models 1–4) that solve the problem to optimality over different classes of PR-policies. We compare our models with each other and with a combination of a traditional proactive approach (namely, the starting time criticality heuristic) and a reactive approach (namely, the robust parallel schedule generation scheme). Computational results show that Model 2 outperforms the traditional solution only when reaction costs are greater than zero. Moreover, Model 3 and Model 4 clearly outperform Model 1 and Model 2 in all settings and the traditional solution in most of the settings. [ABSTRACT FROM AUTHOR]