Catálogo de publicaciones - libros

In recent years, scheduling research has had an increasing impact on practical problems, and a range of scheduling techniques have made their way into real-world application development. Constraint-based models now couple rich representational flexibility with highly scalable constraint management and search procedures. Similarly, mathematical programming tools are now capable of addressing problems of unprecedented scale, and meta-heuristics provide robust capabilities for schedule optimisation. With these mounting successes and advances, it might be tempting to conclude that the chief technical hurdles underlying the scheduling problem have been overcome. However, such a conclusion (at best) presumes a rather narrow and specialised interpretation of scheduling, and (at worst) ignores much of the process and broader context of scheduling in most practical environments. In this note, I argue against this conclusion and outline several outstanding challenges for scheduling research.

We discuss a number of polynomial time approximation results for scheduling problems. All presented results are based on the technique of rounding the optimal solution of an underlying linear programming relaxation. We analyse these relaxations, their integrality gaps, and the resulting approximation algorithms, and we derive matching worst-case instances.

Order scheduling models can be described as follows: A machine environment with a number of non-identical machines in parallel can produce a fixed variety of different products. Any one machine can process a given set of the different product types. If it can process only one type of product it is referred to as a dedicated machine, otherwise it is referred to as a flexible machine. A flexible machine may be subject to a setup when it switches from one product type to another product type. Each product type has certain specific processing requirements on the various machines. There are customers, each one sending in one order. An order requests specific quantities of the various different products and has a release date as well as a due date (committed shipping date). After the processing of all the different products for an order has been completed, the order can be shipped to the customer. This paper is organised as follows. We first introduce a notation for this class of models. We then focus on various different conditions on the machine environment as well as on several objective functions, including the total weighted completion time, the maximum lateness, the number of orders shipped late, and so on. We present polynomial time algorithms for the easier problems, complexity proofs for NP-hard problems and worst case performance analyses as well as empirical analyses of heuristics.

We consider the problem of planning inspections and other tasks within a software development (SD) project with respect to the objectives quality (no. of defects), project duration, and costs. The considered model of SD processes comprises the phases of coding, inspection, test, and rework and includes assigning tasks to persons and generating a project schedule. Based on this model we discuss a multiobjective optimisation problem. For solving the problem (i.e., finding an approximation of the efficient set) we develop a multiobjective evolutionary algorithm. Details of the algorithm are discussed as well as results of its application to sample problems.

Two extensions of the classical scheduling model with two parallel identical machines and a partially ordered set of unit execution time tasks are considered. It is well known that the Coffman—Graham algorithm constructs for this model a so-called ideal schedule: that is, a schedule which is optimal for both makespan and total completion time criteria simultaneously. The question of the existence of such a schedule for the extension of this model, where each task has a release time, has remained open over several decades. The paper gives a positive answer to this question and presents the corresponding polynomial-time algorithm. Another straightforward generalization of the considered classical model is obtained by the introduction of multiprocessor tasks. It is shown that, despite the fact that a slightly modified Coffman-Graham algorithm solves the makespan problem with multiprocessor tasks for arbitrary precedence constraints, generally an ideal schedule does not exist and the problem with the criterion of total completion time turns out to be NP-hard in the strong sense even for in-trees.

In this paper, a short-term manpower planning problem is considered where workers are grouped into gangs to support reliable and efficient operations. The goal is to minimise the total number of workers required by determining an appropriate gang structure, assignment of tasks to gangs, and schedule for each gang. We model such a problem as a multi-mode task scheduling problem with time windows and precedence constraints. While the gang structure and assignment of tasks is optimised by a tabu search heuristic, each gang's schedule is generated by solving the corresponding one-machine scheduling problem by an iterated Schrage heuristic. Because the evaluation of a tabu search move is computationally expensive, we propose a number of ways to estimate a move's impact on the solution quality.

This paper introduces a combinatorial optimisation problem called the Memory Dumping Problem (), which arises in the European Space Agency programme . The domain is characterized by complex constraints concerning bounded on-board memory capacities, limited communication windows over the downlink channels, deadlines and ready times imposed by the scientists using the spacecraft instruments. This paper lays out the problem and analyses its computational complexity showing that is . Then the problem is modelled as a Constraint Satisfaction Problem and two different heuristic strategies for its solution are presented: a core greedy constraint-based procedure and an iterative sampling strategy based on . The algorithms are evaluated both against a benchmark set created on the basis of ESA documentation and a of the minimised objective function. Experimental results show the overall effectiveness of the approach.

A variety of approaches have been developed by researchers to solve different instances of timetabling problems. In these studies different data formats are used to represent a timetabling problem instance and its solution, causing difficulties in the evaluation and comparison of approaches and sharing of data. In this paper, a model for timetabling problems and a new XML data format for them based on MathML is proposed.

This paper describes a web system for supporting manufacturing scheduling in practice. Within this system scheduling concepts like problems and solving methods are modelled through XML. Furthermore, the Internet remote methods' invocation is also based on the XML language and performed using the XML-RPC communication protocol. The architecture and underlying approach of the web system is oriented for solving a large variety of manufacturing scheduling problems based on a continuously updatable distributed knowledge base, which allows a network of peers to provide the scheduling service to users and the dynamic enlargement of the number of methods that can be accessed. This is done in an easy and interactive way.

Using local operations within branch-and-bound methods for job-shop scheduling problems has been proved to be very effective. In this paper, we present an efficient algorithm that applies ascendant set-like adjustments for the immediate selections. This procedure is given within an original framework that guarantees a good convergence process and an easy integration of other classical disjunctive elimination rules.