Robust scheduling and robustness measures for the discrete time/cost trade-off problem

Projects are often subject to various sources of uncertainties that have a negative impact on activity durations and costs. Therefore, it is crucial to develop effective approaches to generate robust project schedules that are less vulnerable to disruptions caused by uncontrollable factors. In this paper, we investigate the robust discrete time/cost trade-off problem, which is a multi-mode project scheduling problem with important practical relevance. We introduce surrogate measures that aim at providing an accurate estimate of the schedule robustness. The pertinence of each proposed measure is assessed through computational experiments. Using the insights revealed by the computational study, we propose a two-stage robust scheduling algorithm. Finally, we provide evidence that the proposed approach can be extended to solve a complex robust problem with tardiness penalties and earliness revenues.     

A scatter search algorithm for project scheduling under partially renewable resources

In this paper we develop a heuristic algorithm, based on Scatter Search, for project scheduling problems under partially renewable resources. This new type of resource can be viewed as a generalization of renewable and non-renewable resources, and is very helpful in modelling conditions that do no fit into classical models, but which appear in real timetabling and labor scheduling problems. The Scatter Search algorithm is tested on existing test instances and obtains the best results known so far.     

A scatter search algorithm for the distributed permutation flowshop scheduling problem

The distributed permutation flowshop problem has been recently proposed as a generalization of the regular flowshop setting where more than one factory is available to process jobs. Distributed manufacturing is a common situation for large enterprises that compete in a globalized market. The problem has two dimensions: assigning jobs to factories and scheduling the jobs assigned to each factory. Despite being recently introduced, this interesting scheduling problem has attracted attention and several heuristic and metaheuristic methods have been proposed in the literature. In this paper we present a scatter search (SS) method for this problem to optimize makespan. SS has seldom been explored for flowshop settings. In the proposed algorithm we employ some advanced techniques like a reference set made up of complete and partial solutions along with other features like restarts and local search. A comprehensive computational campaign including 10 existing algorithms, together with statistical analyses, shows that the proposed scatter search algorithm produces better results than existing algorithms by a significant margin. Moreover all 720 known best solutions for this problem are improved.     

Optimal procedures for the discrete time/cost trade-off problem in project networks

We describe two algorithms, based on dynamic programming logic, for optimally solving the discrete time/cost trade-off problem (DTCTP) in deterministic activity-on-arc networks of the CPM type, where the duration of each activity is a discrete, nonincreasing function of the amount of a single nonrenewable resource committed to it. The first algorithm is based on a procedure proposed by Bein, Kamburowski and Stallmann for finding the minimal number of reductions necessary to transform a general network to a series-parallel network. The second algorithm minimizes the estimated number of possibilities that need to be considered during the solution procedure. Both procedures have been programmed in C and tested on a large set of representative networks to give a good indication of their performance, and indicate the circumstances in which either algorithm performs best.     

A hybrid single and dual population search procedure for the job shop scheduling problem

This paper presents a genetic algorithm and a scatter search procedure to solve the well-known job shop scheduling problem. In contrast to the single population search performed by the genetic algorithm, the scatter search algorithm splits the population of solutions in a diverse and high-quality set to exchange information between individuals in a controlled way. The extension from a single to a dual population, by taking problem specific characteristics into account, can be seen as a stimulator to add diversity in the search process. This has a positive influence on the important balance between intensification and diversification. Computational experiments verify the benefit of this diversity on the effectiveness of the meta-heuristic search process. Various algorithmic parameters from literature are embedded in both procedures and a detailed comparison is made. A set of standard instances is used to compare the different approaches and the best obtained results are benchmarked against heuristic solutions found in literature.     

A solution procedure for the discrete time, cost and quality tradeoff problem using electromagnetic scatter search

Decisions concerning a project’s expedition, traditionally involved considerations regarding time and cost tradeoff. It was recently suggested that the quality of a project should also be taken into considerations. In this paper, we propose a meta-heuristic solution procedure for the discrete time, cost and quality tradeoff problem. This problem involves the scheduling of project activities in order to minimize the total cost of the project while maximizing the quality of the project and also meeting a given deadline. We apply a so called electromagnetic scatter search to solve this problem. In this process, we initially generate a population of feasible solutions. In so doing, we use frequency memory to well sample the feasible region. A number of these solutions are then selected and improved locally. The improved solutions are then combined to generate new set of solutions. The combination process utilizes attraction–repulsion mechanisms borrowed from the electromagnetism theory. The whole process is stopped when no significant improvement in the set of solutions are observed. The validity of the proposed solution procedure is demonstrated, and its applicability is tested on a randomly generated large and complex problem having 19,900 activities.     

A hybrid scatter search heuristic for personalized crew rostering in the airline industry

The crew scheduling problem in the airline industry is extensively investigated in the operations research literature since efficient crew employment can drastically reduce operational costs of airline companies. Given the flight schedule of an airline company, crew scheduling is the process of assigning all necessary crew members in such a way that the airline is able to operate all its flights and constructing a roster line for each employee minimizing the corresponding overall cost for personnel. In this paper, we present a scatter search algorithm for the airline crew rostering problem. The objective is to assign a personalized roster to each crew member minimizing the overall operational costs while ensuring the social quality of the schedule. We combine different complementary meta-heuristic crew scheduling combination and improvement principles. Detailed computational experiments in a real-life problem environment are presented investigating all characteristics of the procedure. Moreover, we compare the proposed scatter search algorithm with optimal solutions obtained by an exact branch-and-price procedure and a steepest descent variable neighbourhood search.     

GRASP and path relinking for project scheduling under partially renewable resources

Recently, in the field of project scheduling problems the concept of partially renewable resources has been introduced. Theoretically, it is a generalization of both renewable and non-renewable resources. From an applied point of view, partially renewable resources allow us to model a large variety of situations that do not fit into classical models, but can be found in real problems in timetabling and labor scheduling. In this paper, we develop some preprocessing techniques and several heuristic algorithms for the problem. Preprocessing significantly reduces the dimension of the problems, therefore improving the efficiency of solution procedures. Heuristic algorithms based on GRASP and Path relinking are then developed and tested on existing test instances, obtaining excellent results.     

Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times

In this paper, a multi-mode resource-constrained project scheduling problem with schedule-dependent setup times is considered. A schedule-dependent setup time is defined as a setup time dependent on the assignment of resources to activities over time, when resources are, e.g., placed in different locations. In such a case, the time necessary to prepare the required resource for processing an activity depends not only on the sequence of activities but, more generally, on the locations in which successive activities are executed. Activities are non-preemptable, resources are renewable, and the objective is to minimize the project duration. A local search metaheuristic—tabu search is proposed to solve this strongly NP-hard problem, and it is compared with the multi-start iterative improvement method as well as with random sampling. A computational experiment is described, performed on a set of instances based on standard test problems constructed by the ProGen project generator. The algorithms are computationally compared, the results are analyzed and discussed, and some conclusions are given.     

Scatter search for the fleet size and mix vehicle routing problem with time windows

This work proposes a scatter search (SS) approach to solve the fleet size and mix vehicle routing problem with time windows (FSMVRPTW). In the FSMVRPTW the customers need to be serviced in their time windows at minimal costs by a heterogeneous fleet. Computational results on 168 benchmark problems are reported. Computational testing revealed that our algorithm presented better results compared to other methods published in the literature.     

A genetic algorithm for resource investment project scheduling problem,tardiness permitted with penalty

In this paper a genetic algorithm for solving a class of project scheduling problems, called Resource Investment Problem, is presented. Tardiness of project is permitted with defined penalty. Elements of algorithm such as chromosome structure, unfitness function, crossover, mutation, immigration and local search operations are explained.     

Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem

This paper focuses on introducing a concept of diversified local search strategy under the scatter search framework for the probabilistic traveling salesman problem (PTSP). Different combinations of three commonly used local search methods in the PTSP, i.e., 1-shift, 2-opt, and 3-opt, were used to investigate its effects. A set of numerical experiments were conducted to test the validity of the proposed strategy based on randomly generated test instances. The numerical results and the permutation test showed that the diversified local search strategy, especially by combining 1-shift and 2-opt algorithms, can most effectively solve the homogeneous and heterogeneous PTSP in most of the tested instances in comparison with the single local search strategy under scatter search framework.     

A hybrid genetic algorithm for the resource-constrained project scheduling problem

In this paper we propose a Hybrid Genetic Algorithm (HGA) for the Resource-Constrained Project Scheduling Problem (RCPSP). HGA introduces several changes in the GA paradigm: a crossover operator specific for the RCPSP; a local improvement operator that is applied to all generated schedules; a new way to select the parents to be combined; and a two-phase strategy by which the second phase re-starts the evolution from a neighbour’s population of the best schedule found in the first phase. The computational results show that HGA is a fast and high quality algorithm that outperforms all state-of-the-art algorithms for the RCPSP known by the authors of this paper for the instance sets j60 and j120. And that it is competitive with other state-of-the-art heuristics for the instance set j30.     

Simulated annealing and tabu search for multi-mode project payment scheduling

This paper involves the multi-mode project payment scheduling problem where the activities can be performed with one of several discrete modes and the objective is to assign activities’ modes and progress payments so as to maximize the net present value of the contractor under the constraint of project deadline. Using the event-based method the basic model of the problem is constructed and in terms of the different payment rules it is extended as the progress based, expense based, and time based models further. For the strong NP-hardness of the problem which is proven by simplifying it to the deadline subproblem of the discrete time–cost tradeoff problem, we develop two heuristic algorithms, namely simulated annealing and tabu search, to solve the problem. The two heuristic algorithms are compared with the multi-start iterative improvement method as well as random sampling on the basis of a computational experiment performed on a data set constructed by ProGen project generator. The results show that the proposed simulated annealing heuristic algorithm seems to be the most promising algorithm for solving the defined problem especially when the instances become larger. In addition, the effects of several key parameters on the net present value of the contractor are analyzed and some conclusions are given based on the results of the computational experiment.     

A note on the modelling of project networks with time constraints

In this note we show how to manage, by means of Generalized Precedence Relationships, some kinds of temporal constraints introduced by Chen et al. (1997) in project networks.     

Proactive policies for the stochastic resource-constrained project scheduling problem

The resource-constrained project scheduling problem involves the determination of a schedule of the project activities, satisfying the precedence and resource constraints while minimizing the project duration. In practice, activity durations may be subject to variability. We propose a stochastic methodology for the determination of a project execution policy and a vector of predictive activity starting times with the objective of minimizing a cost function that consists of the weighted expected activity starting time deviations and the penalties or bonuses associated with late or early project completion. In a computational experiment, we show that our procedure greatly outperforms existing algorithms described in the literature.     

A tabu search algorithm for solving economic lot scheduling problem

The economic lot scheduling problem has driven considerable amount of research. The problem is NP-hard and recent research is focused on finding heuristic solutions rather than searching for optimal solutions. This paper introduces a heuristic method using a tabu search algorithm to solve the economic lot scheduling problem. Diversification and intensification schemes are employed to improve the efficiency of the proposed Tabu search algorithm. Experimental design is conducted to determine the best operating parameters for the Tabu search. Results show that the tabu search algorithm proposed in this paper outperforms two well known benchmark algorithms.     

A local search using solution fragments for the 2-machine bicriteria scheduling problem

In this work, we introduce a local search strategy for combinatorial optimization problems which explores neighborhoods obtained using fragments of current solutions. We apply the approach to the well-known -hard 2-machine bicriteria flowshop scheduling problem. Computational experiments using benchmark data show the approach to be effective when compared to other algorithms available for the problem.     

A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem

We consider the multi-mode resource-constrained project scheduling problem (MRCPSP), where a task has different execution modes characterized by different resource requirements. Due to the nonrenewable resources and the multiple modes, this problem is NP-hard; therefore, we implement an evolutionary algorithm looking for a feasible solution minimizing the makespan.     

Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil

In this paper, we consider a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries that occurs in a major Brazilian retail group. A single depot attends 519 stores of the group distributed in 11 Brazilian states. To find good solutions to this problem, we propose heuristics as initial solutions and a scatter search (SS) approach. Next, the produced solutions are compared with the routes actually covered by the company. Our results show that the total distribution cost can be reduced significantly when such methods are used. Experimental testing with benchmark instances is used to assess the merit of our proposed procedure.