A heuristic algorithm for project scheduling with splitting allowed

In this article, we analyze the precedence diagramming method, the only published algorithm for time-only project scheduling with activity splitting allowed. The criteria used in this method (forward and backward pass computations) for deciding when an activity has to be interrupted are shown to be invalid in some situations. We look into the causes of these failures and propose new formulae that always provide feasible solutions. The new algorithm has been tested on 240 randomly generated problems ranging up to 600 activities and 7,200 precedence relationships, resulting in an average deviation from optima of less than 1 percent.     

Single-machine scheduling problems with a learning effect

In many situations, the skills of workers continuously improve when repeating the same or similar tasks. This phenomenon is known as the “learning effect” in the literature. In most studies, the learning phenomenon is implemented by assuming the actual job processing time is a function of its scheduled position [D. Biskup, Single-machine scheduling with learning considerations, Eur. J. Oper. Res. 115 (1999) 173–178]. Recently, a new model is proposed where the actual job processing time depends on the sum of the processing times of jobs already processed [C. Koulamas, G.J. Kyparisis, Single-machine and two-machine flowshop scheduling with general learning functions, Eur. J. Oper. Res. 178 (2007) 402–407]. In this paper, we extend their models in which the actual job processing time not only depends on its scheduled position, but also depends on the sum of the processing times of jobs already processed. We then show that the single-machine makespan and the total completion time problems remain polynomially solvable under the proposed model. In addition, we show that the total weighted completion time has a polynomial optimal solution under certain agreeable solutions.     

Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting

This paper presents a priority rule-based heuristic for the multi-mode resource-constrained project scheduling problem with the splitting of activities around unavailable resources allowed. All resources considered are renewable and each resource unit may not be available at all times due to resource vacations, which are known in advance. A new concept called moving resource strength is developed to help identify project situations where activity splitting is likely to be beneficial during scheduling. The moving resource strength concept is implemented in priority rule-based heuristics to control activity splitting when scheduling. Multiple comparisons of the performance of combination of activity–mode priority rules used in the heuristics are provided. Computational experiments demonstrate the effectiveness of the heuristic in reducing project makespan, and minimizing activity splitting.     

Solving resource-constrained project scheduling problem with evolutionary programming

This paper presents an evolutionary programming (EP)-based approach to solving the resource-constrained project scheduling problem (RCPSP), a well-known NP-hard problem in scheduling, with minimization of project duration as the objective subject to precedence and resource constraints. The individual representation of EP for the problem is based on random keys. The serial generation scheme is used in the decoding scheme to generate the project plan. Experimental analyses are presented to investigate the performance of the proposed EP-based methodology, including comparison of the four variants of EP, namely, CEP, FEP, MCEP and IMCEP, with each other and GA to find the best variant of EP for the RCPSP, and comparison of this best variant of EP (MCEP) with other approaches using the J30 standard instances set in PSPLIB. The computational results validate the effectiveness of the proposed algorithm.     

Modeling of superscalar instruction scheduling and analysis of a heuristic scheduling algorithm

The problem of superscalar instruction scheduling is studied and an analysis of a heuristic scheduling algorithm is presented. First, a superscalar architecture is characterized byk, the number of types of functional units employed,m _i , the number of typei functional units,P _ij , thejth functional unit of typei, andz, the maximal number of delay cycles incurred by the execution of instructions. A program trace to be scheduled is modeled by a directed acyclic graph with delay on precedence relations. These two models reflect most of the flavor of the superscalar instruction scheduling problem. A heuristic scheduling algorithm called the ECG-algorithm is designed by compiling two scheduling guidelines. The performance of the ECG-algorithm is evaluated through worst-case analysis. Lettingw _ECG denote the length of an ECG-schedule andw _opt the length of an optimal schedule, we established the boundwv _ECG /w _opt k+1–2/[max{m _i }(z+1)], which is smaller than other known bounds.     

A simulated annealing algorithm for resource constrained project scheduling problems

This paper presents a simulated annealing algorithm for resource constrained project scheduling problems with the objective of minimising makespan. In the search algorithm, a solution is represented with a priority list, a vector of numbers each of which denotes the priority of each activity. In the algorithm, a priority scheduling method is used for making a complete schedule from a given priority list (and hence a project schedule is defined by a priority list). The search algorithm is applied to find a priority list which corresponds to a good project schedule. Unlike most of priority scheduling methods, in the suggested algorithm some activities are delayed on purpose so as to extend search space. Solutions can be further improved by delaying certain activities, since non-delay schedules are not dominant in the problem (the set of non-delay schedules does not always include an optimal solution). The suggested algorithm is flexible in that it can be easily applied to problems with an objective function of a general form and/or complex constraints. The performance of the simulated annealing algorithm is compared with existing heuristics on problems prepared by Patterson and randomly generated test problems. Computational results showed that the suggested algorithm outperformed existing ones.     

A Lagrangean heuristic algorithm for disassembly scheduling with capacity constraints

This paper considers the problem of determining the disassembly schedule (quantity and timing) of products in order to satisfy the demand of their parts or components over a finite planning horizon. The objective is to minimize the sum of set-up, disassembly operation, and inventory holding costs. As an extension of the uncapacitated versions of the problem, we consider the resource capacity restrictions over the planning horizon. An integer program is suggested to describe the problem mathematically, and to solve the problem, a heuristic is developed using a Lagrangean relaxation technique together with a method to find a good feasible solution while considering the trade-offs among different costs. The effectiveness of the algorithm is tested on a number of randomly generated problems and the test results show that the heuristic suggested in this paper can give near optimal solutions within a short amount of computation time.     

Solving large scale crew scheduling problems

The crew pairing problem is posed as a set partitioning zero-one integer program. Variables are generated as legal pairings meeting all work rules. Dual values obtained from solving successive large linear program relaxations are used to prune the search tree. In this paper we present a graph based branching heuristic applied to a restricted set partitioning problem representing a collection of ‘best’ pairings. The algorithm exploits the natural integer properties of the crew pairing problem. Computational results are presented to show realized crew cost savings.     

Solving scheduling problems from high-level models

This is the summary of the author??s PhD thesis supervised by Yves Deville and Pascal Van Hentenryck, and defended on 25 May 2010?at the Université catholique de Louvain in Louvain-la-Neuve. The thesis is written in English and is available from the author, or downloadable from http://becool.info.ucl.ac.be/files2/thesis-monette.pdf. This work is about the gap between high-level modelling of scheduling problems and its efficient resolution. We propose to automatically classify models of scheduling problems, and to apply an appropriate search algorithm. Thanks to the strong separation between model and search, we propose also a simple way to create hybrid algorithms. A second part of the thesis deals with Constraint Programming approaches for two scheduling problems: The one-machine non-preemptive problem and the Just-In-Time Job-Shop problem. All parts are accompanied by experimental results showing their practicality.     

A heuristic for scheduling problems,especially for scheduling farm operations

Scheduling problems in agriculture are often solved using techniques such as linear programming (the multi-period formulation) and dynamic programming. But it is difficult to obtain an optimal schedule with these techniques for any but the smallest problems, because the model is unwieldly and much time is needed to solve the problem. Therefore, a new algorithm, a heuristic, has been developed to handle scheduling problems in agriculture. It is based on a search technique (i.e. hill-climbing) supported by a strong heuristic evaluation function. In this paper the heuristic performance is compared with dynamic programming. The heuristic offers near-optimal solutions and is much faster than the dynamic programming model. When tested against dynamic programming the difference in results was about 3%. This heuristic could probably also be applied in an industrial environment (e.g. agribusiness or road construction).     

Solving multi-objective production scheduling problems using metaheuristics

Most of research in production scheduling is concerned with the optimization of a single criterion. However the analysis of the performance of a schedule often involves more than one aspect and therefore requires a multi-objective treatment. In this paper we first present (Section 1) the general context of multi-objective production scheduling, analyze briefly the different possible approaches and define the aim of this study i.e. to design a general method able to approximate the set of all the efficient schedules for a large set of scheduling models. Then we introduce (Section 2) the models we want to treat––one machine, parallel machines and permutation flow shops––and the corresponding notations. The method used––called multi-objective simulated annealing––is described in Section 3. Section 4 is devoted to extensive numerical experiments and their analysis. Conclusions and further directions of research are discussed in the last section.     

A partial enumeration heuristic for multi-objective flowshop scheduling problems

This paper addresses the flowshop scheduling problem with multiple performance objectives in such a way as to provide the decision maker with approximate Pareto optimal solutions. It is well known that the partial enumeration constructive heuristic NEH and its adaptations perform well for single objectives such as makespan, total tardiness and flowtime. In this paper, we develop a similar heuristic using the concept of Pareto dominance when comparing partial and complete schedules. The heuristic is tested on problems involving combinations of the above criteria. For the two-machine case, and the pairs of objectives: (i) makespan and maximum tardiness, (ii) makespan and total tardiness, the heuristic is compared with branch-and-bound algorithms proposed in the literature. For two and more than two machines, and the criteria combinations considered in this article, the heuristic performance is tested against constructive heuristics reported in the literature. By means of an illustrative example, it is shown that a genetic algorithm from the literature performs better when starting from heuristic solutions rather than random solutions.     

Solving symmetric mixed-model multi-level just-in-time scheduling problems

The generation of leveled production schedules is of high importance for mixed-model assembly lines whose parts and materials are supplied just-in-time by multi-level production processes. The Output Rate Variation problem is the standard mathematical representation of this complex level scheduling problem and has been extensively studied by research thus far. This work identifies novel symmetries in solution sequences of this problem class and shows how these insights can be used to improve exact solution procedures presented in the literature. The effectiveness of the modifications is evaluated by a computational study.     

Several single-machine scheduling problems with general learning effects

In this paper we consider several single-machine scheduling problems with general learning effects. By general learning effects, we mean that the processing time of a job depends not only on its scheduled position, but also on the total normal processing time of the jobs already processed. We show that the scheduling problems of minimization of the makespan, the total completion time and the sum of the θ  th (θ?0$\theta ?0$) power of job completion times can be solved in polynomial time under the proposed models. We also prove that some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time.     

A revision of machine scheduling problems with a general learning effect

In this paper, we show that the main results in a recent paper by Zhang and Yan [X. Zhang and G. Yan, Machine scheduling problems with a general learning effect, Mathematical and Computer Modelling 51 (2010) 84–90] are incorrect as an important reason is missing, that is, the processing time of a job is variable according to a general learning effect. Here we point out these wrong results by a counter-example. In addition, we give a revised model with a general learning effect. We show that some single machine scheduling problems are still polynomially solvable under the revised model. We also show that some special cases of the flowshop scheduling problems can be solved in polynomial time under the revised model.     

Solving project scheduling problem with the philosophy of fuzzy random programming

Project scheduling problem is to determine the schedule of allocating resources to achieve the trade-off between the project cost and the completion time. In real projects, the trade-off between the project cost and the completion time, and the uncertainty of the environment are both considerable aspects for managers. Due to the complex external environment, this paper considers project scheduling problem with coexisted uncertainty of randomness and fuzziness, in which the philosophy of fuzzy random programming is introduced. Based on different ranking criteria of fuzzy random variables, three types of fuzzy random models are built. Besides, a searching approach by integrating fuzzy random simulations and genetic algorithm is designed for searching the optimal schedules. The goal of the paper is to provide a new method for solving project scheduling problem in hybrid uncertain environments.     

Solving dual problems using a coevolutionary optimization algorithm

In solving certain optimization problems, the corresponding Lagrangian dual problem is often solved simply because in these problems the dual problem is easier to solve than the original primal problem. Another reason for their solution is the implication of the weak duality theorem which suggests that under certain conditions the optimal dual function value is smaller than or equal to the optimal primal objective value. The dual problem is a special case of a bilevel programming problem involving Lagrange multipliers as upper-level variables and decision variables as lower-level variables. Another interesting aspect of dual problems is that both lower and upper-level optimization problems involve only box constraints and no other equality of inequality constraints. In this paper, we propose a coevolutionary dual optimization (CEDO) algorithm for co-evolving two populations—one involving Lagrange multipliers and other involving decision variables—to find the dual solution. On 11 test problems taken from the optimization literature, we demonstrate the efficacy of CEDO algorithm by comparing it with a couple of nested smooth and nonsmooth algorithms and a couple of previously suggested coevolutionary algorithms. The performance of CEDO algorithm is also compared with two classical methods involving nonsmooth (bundle) optimization methods. As a by-product, we analyze the test problems to find their associated duality gap and classify them into three categories having zero, finite or infinite duality gaps. The development of a coevolutionary approach, revealing the presence or absence of duality gap in a number of commonly-used test problems, and efficacy of the proposed coevolutionary algorithm compared to usual nested smooth and nonsmooth algorithms and other existing coevolutionary approaches remain as the hallmark of the current study.     

Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm

When solving the one-dimensional cutting stock problem (1D CSP) as an integer linear programming problem one has to overcome computational difficulties arising from the integrality condition and a huge number of variables. In the Gilmore–Gomory approach the corresponding continuous relaxation is solved via column generation techniques followed by an appropriate rounding of the in general non-integer solution. Obviously, there is no guarantee of obtaining an optimal solution in this way but it is extremely effective in practice. However, in two- and three-dimensional cutting stock problems the heuristics are not so good which necessitates the research of effective exact methods. In this paper we present an exact solution approach for the 1D CSP which is based on a combination of the cutting plane method and the column generation technique. Results of extensive computational experiments are reported.     

Proactive heuristic procedures for robust project scheduling: An experimental analysis

Solution-robust project scheduling is a growing research field aiming at constructing proactive schedules to cope with multiple disruptions during project execution. When stochastic activity durations are considered, including time buffers between activities is a proven method to improve the stability of a baseline schedule.