Project Management And Scheduling

European Journal of Operational Research 165 (2005) 285–288 www.elsevier.com/locate/dsw

Editorial

Project management and scheduling

The EURO Working Group on Project Management and Scheduling (WG-PMS) was established in 1986, with the aim of assessing the stateof-the-art and stimulating progress in both theory and practice within the area. To achieve these goals, the decision was made to organize workshops every two years. The Eighth International Workshop on Project Management and Scheduling was held in Valencia (Spain), April 3–5, 2002, and was hosted by the Department of Financial and Mathematical Economics and the Department of Statistics and Operational Research of the University of Valencia. The proceedings book contains extended abstracts of all 94 papers accepted by the program committee. These papers were clustered for presentation into 26 sessions scheduled in three parallel streams. Broadly speaking, the streams correspond to Project Management, Machine Scheduling, and Applications. This feature issue contains 20 papers that were presented at the Workshop, and accepted for publication after a careful reviewing process. We would like to express our gratitude to all the reviewers for their invaluable efforts allowing us to select a set of high-quality contributions. The first three papers address the issue of scheduling under uncertainty. The project scheduling literature largely concentrates on the generation of an optimal (or near optimal) schedule for problems arising in project planning and control that assume complete information and a static deterministic environment within which the precomputed baseline schedule will be executed. However, uncertainty lies at the very heart of real-

life project management, and thus the literature on project scheduling under risk and uncertainty is witnessing a recent explosion. Herroelen and Leus in their invited review overview fundamental approaches for scheduling under uncertainty––many of which have been mainly or solely studied in a machine scheduling environment––and discuss the potentials of these approaches for scheduling under uncertainty projects with deterministic network evolution structure. Elmaghraby delivers a stimulating and insightful discussion on the issue of uncertainty in project management, especially when dealing with the risk inherent in the estimates relative to cost and time. Based on a project scheduling problem with stochastic activity work contents, the paper exemplifies the prejudicial consequences that are incurred in project control when random variables are substituted into their expected values. Introducing flexibility in the schedule determination phase is an approach proposed by Artigues, Billaut, and Esswein to cope with uncertainty in a general shop floor scheduling setting with release dates and deadlines. The flexibility is provided by generating a family of schedules instead of a unique one, so that the decision-maker can switch from one solution to another in case of disruptions. A family of schedules is represented by defining for each machine a sequence of groups of operations, where the operations within a group are totally permutable. The generation and evaluation of families of schedules, the maximization of flexibility criteria and the impact of grouping operations on the makespan value are some of the issues dealt with in the paper.

0377-2217/$ - see front matter Ó 2004 Elsevier B.V. All rights reserved. doi:10.1016/j.ejor.2004.04.001

286

Editorial / European Journal of Operational Research 165 (2005) 285–288

The next four papers are devoted to project management. In medium to large-scale projects, it is quite common for the project owner, lacking the technical skills in a number of areas that the project execution may call for, to subcontract some or all of the project activities to one or more specialists. Under these circumstances, a bidding mechanism is often the preferred price-setting mechanism. Paul and Gutierrez approach, from the point of view of the project owner, the process of price setting using sealed bids. They use a parsimonious stochastic model to compare the expected price fetched by three commonly used contract forms: Fixed Price, Cost Plus and an intermediate type of contract that they call a Menu contract. The impact of risk aversion and collusion on the average winning bid price is also analysed. In project management, the project duration can often be compressed by accelerating some of its activities at an additional expense. This is the so-called time-cost trade-off problem (TCTP). Next two papers consider different versions of this problem. The paper by Akkan, Drexl, and Kimms provides lower and upper bounds for the discrete version of the problem (DTCTP) using column generation techniques based on network decomposition. A computational study is provided to demonstrate that the presented bounds are tight and that large and hard instances can be solved in short run-time. Recently, time-switch constraints have been introduced into the discrete time/cost trade-off problem in order to cope with day, night and weekend shifts. Basically, these constraints impose a specified starting time on the project activities and force them to be inactive during specified time periods. Vanhoucke proposes a new branch-andbound algorithm for the DTCTP with time-switch constraints that outperforms previous results. In the context of the resource-constrained project scheduling problem (RCPSP), Valls, Ballest
ın, and Quintanilla propose the double justification as a technique able to improve the quality of solutions obtained by other methods. By incorporating double justification into 22 diverse heuristic algorithms, they show that justification is a simple technique that can be incorporated easily into di-

verse algorithms and produces notable improvements in the quality of the schedules with a small, and generally favourable, change in computing time. Their main conclusion is that double justification should always be considered when designing an algorithm for the RCPSP. A group of five papers are clustered around the study of the computational complexity of different machine scheduling problems. Sevastianov proposes a novel complexity analysis of discrete problems, multi-parameter complexity analysis, which consists in establishing the complexity of the various sub-problems of a given problem whose intractability has been determined. The sub-problems are specified by combinations of constraints on key problem parameters. Since the number of sub-problems may be infinite, the author introduces and studies the concept of a basis system of sub-problems, a minimum cardinality set of subproblems such that the determination of their complexities would be sufficient to determine the complexity of any other sub-problem. The new ideas and theoretical results presented in the paper are illustrated with the application of multi-parameter complexity analysis to two discrete problems: the open shop scheduling problem and the connected list colouring problem. This final problem allows a natural interpretation as a scheduling problem on parallel machines. Flow-shop problems with a single server are generalizations of classical flow-shop problems where setup times are assumed to be separable from the processing times and all setups have to be done by a single server. Brucker and Knust derive new complexity results for special cases where restrictions on processing and or setup times are specified. Blazewicz, Pesch, Sterna, and Werner consider another version of the flow-shop scheduling problem––the two-machine non-preemptive flowshop scheduling problem with the total weighted late work criterion and a common due date. This criterion takes into account the duration of task late parts while ignoring the quantity of this delay. They have proved the binary NP-hardness of the problem mentioned and propose a dynamic programming approach of pseudo-polynomial time complexity proving in this way the ordinary NPhardness of this problem.

Editorial / European Journal of Operational Research 165 (2005) 285–288

Janiak, Kovalyov, Kubiak, and Werner study the single machine scheduling problem with controllable job processing times to minimize a linear combination of the total weighted job completion time and the total weighted processing time compression. They show that this scheduling problem is polynomially equivalent to the problem of maximizing a special subclass of half-products, namely, positive half-products. This equivalence immediately proves that the former problem is NP-hard in the ordinary sense and that it can be solved in pseudo-polynomial time by dynamic programs proposed earlier for the half-product minimization. They also present two fast fully polynomial time approximation schemes for any positive half-product––including the problem with controllable job processing times. The paper by Cheng, Ng, Yuan, and Liu studies the one machine total weighted tardiness scheduling problem. The authors describe an Oðn2 Þ approximation algorithm for the general problem without release dates. As the general problem is NP-hard in the strong sense, the authors also investigate the NP-hardness of two special cases of the problem––the case where all job due dates have equal slacks and the case where job due dates are affine-linear functions of their processing times and the job tardiness weights are proportional to their processing times––and provide algorithms for their resolution. The polyhedral aspects of scheduling problems have been extensively studied since the pioneering work by Balas. Most of the research in this area, however, concentrates on the single machine problem. Cheng and Shakhlevich consider the preemptive identical parallel machine problem with identical jobs and both the non-preemptive and preemptive versions of the unit-time open shop scheduling problem. They construct a linear description of the scheduling polyhedron for these problems which consists of simultaneous linear inequalities that specify the convex hull of the job completion time vectors associated with the feasible schedules. The study of the properties of the scheduling polyhedron enables the demonstration that these problems are solvable in polynomial time in the case of an arbitrary non-decreasing separable objective function of job completion times.

287

The two subsequent papers propose solution procedures for variants of the parallel machine scheduling problem. Ghirardi and Potts consider the problem of scheduling jobs on unrelated parallel machines to minimize the maximum completion time. The paper presents an application of the Recovering Beam Search method to this problem that requires polynomial time. The Recovering Beam Search differs from the traditional Beam Search approach in that it allows the possibility of correcting wrong decisions by replacing partial solutions with others. The algorithm produces good results on large instances within a reasonable time limit. Singh considers a machine scheduling problem with parallel processors, precedence constraints, unit execution time tasks, unit communication delays, and the criterion of maximum lateness. In the case when the graph representing the partially ordered set of tasks is an outforest, it is shown that if the number of processors is restricted then the generalization of the Brucker–Garey–Johnson algorithm previously presented by the same author is a 2-approximation algorithm, and produces an optimal schedule if the number of processors is sufficiently large. Another polynomial time algorithm, which enables us to obtain an optimal schedule when the number of processors is two and precedence constraints are given in the form of an outforest, is also presented. The flow-shop scheduling problem has been the subject of extensive research in recent years. Ruiz and Maroto present a review and comparative evaluation of heuristics and metaheuristics for this problem. The computational comparison is made against Taillard’s benchmarks and includes 25 methods, ranging from the classical Johnson’s algorithm or dispatching rules to the most recent metaheuristics. The last group of papers focuses on proposing new models and solution approaches to various practical applications. Two papers deal with a subject of major importance to production scheduling in process industries, the management of storage systems. The paper by Neumann, Schwindt, and Trautmann deals with scheduling continuous, discontinuous, and semi-continuous material flows in process industries, where scarce

288

Editorial / European Journal of Operational Research 165 (2005) 285–288

production resources and intermediate storage facilities with different configurations and limited capacity have to be taken into account. The authors formulate a basic production scheduling problem in process industries where a convex objective function is to be minimized subject to (renewable and cumulative) resource and temporal constraints. They propose a branch-and-bound algorithm for its resolution. Additional features which frequently occur in practice can be included without difficulty. In the context of an implementation in a constrained-based system, Sourd and Rogerie introduce the continuous reservoir model in which the activity fills or empties the reservoir at a constant rate from its start time to end time. By introducing the concept of function variables, the model is generalized to deal with additional constraints, such as leaks or overflows, that cannot be modelled by filling and emptying activities. Other distinguishing features of the generalized model are that the durations and the depletion or replenishment rates of the activities are assumed to be decision variables and secondly, the depletion and replenishment rates may depend on the current inventory level. Timetabling is adapted and extended to this new model. Alvarez-Vald
es, Fuertes, Tamarit, Gim
enez, and Ramos deal with the design and implementation of a scheduling system in a glass factory. The problem can be considered as a generalization of the flexible job-shop problem with both single and parallel machines, job batches, setup times, release dates, and due dates. The goal is to obtain feasible schedules by minimizing the makespan if the problem is feasible, or to obtain a ‘‘best compromise’’ schedule if a full solution is not possible. Lacomme, Prins, and Ramdane-Cherif consider the Periodic Capacitated Arc Routing Problem (PCARP) which involves the routing of vehicles to

treat a set of arcs in a network where the trips must be planned over a multi-period horizon. Solving the PCARP implies the simultaneous determination of planning (the assignment of street services to periods) and scheduling (the detailed solution of the resulting CARP for one period) decisions over the whole horizon. The promising results shown in the paper demonstrate the value of integrating tactical and operational decisions in longterm planning problems not only in arc routing but also in manufacturing. Notice that the PCARP may be viewed as a multi-period production problem when vehicles are considered as machines, street services as tasks, and service costs as durations. Acknowledgements We wish to express our gratitude to the sponsors who made the Workshop possible: The City of Valencia, The University of Valencia, Fundaci
o Universitat-Empresa de Valencia (ADEIT), Instituto Valenciano de Investigaciones Econ
omicas (IVIE), Ministerio de Educaci
on, Cultura y Deporte de Espa~ na, The Associaton of European Operational Research Societies (EURO). Vicente Valls Facultad de Matematicas Departamento de Estad. e Investig. Operat. Universidad de Valencia Dr. Moliner 50, 46100 Burjassot, Valencia, Spain E-mail address: vicente:valls@uv:es Jan Weglarz Technical University of Poznan Poland Available online 1 June 2004