Abstract It is known that the resource‐unconstrained project scheduling problem with generalized precedence constraints (RUPSP) and minimum completion time objective function can be solved in time O(n·m), where n is the number of activities and m is the number of precedence relations. In this article, we propose a new network formulation for RUPSP based on a transformation that maps the original problem into a standardized acyclic network where precedence relationships between each pair of activities are only of the finish‐to‐start type with zero time lags. With this network, we then associate a mathematical program that can be solved in O(m) time by means of dynamic programing. Exploiting the dual formulation of this mathematical program we further prove that the minimum completion time can also be computed, with the same computational complexity O(m), by finding an augmenting path of longest length in the proposed acyclic network by installing unit capacities on arcs. Computational results on benchmarks are presented. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010

Examination timetabling assigns examinations to a given number of time slots so that there are no conflicts. A conflict occurs if a student has to take more than one examination at the same time, or when the number of students that must take an exam exceeds the capacity of the classroom assigned. The objective is to minimize penalties from proximity constraints. We present new algorithms based on local search and report on an extensive experimental study. We consider also a variant where the concern is to produce conflict-free timetables minimizing the number of time slots, regardless of how close exams appear in the schedule. The algorithms proposed also manage the trade-off between the two objective functions and produce the best results on several standard benchmark instances, compared to the best existing algorithms.

Abstract In this article we design a truncated enumerative algorithm based on branch and bound rules embedded in a multistage scheme that allows iterative visits of subgraphs. The algorithm is designed to find lower bounds on the chromatic number of graphs, and, by means of simple coloring extension rules, it is often capable of finding optimal solutions. In this issue we obtain a very promising result: our algorithm was able to solve benchmarks DSJC125_5, DSJC125_9, DSJC250_1, DSJR500_1c, and DSJR500_5, which had not previously been solved. Furthermore, we show how our method can be employed in finding upper bounds on the chromatic number, and thus, we compare the upper bound–lower bound gaps so obtained with those achieved by known exact algorithms. The comparison highlights that in more than half of the tested benchmarks the gap obtained by our algorithm was lower than that obtained by a recent branch and cut method and by the well‐known DSATUR algorithm. To provide a deeper analysis we finally compare the upper bounds found by the proposed algorithm on the same benchmarks with the best heuristic solutions known in the open literature. Also, in this case, the proposed truncated branch and bound was often able to outperform these heuristic solutions. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 231–242 2004

Abstract The Grid computing paradigm is originated from a new computing infrastructure for scientific research and cooperation, and is becoming an established technology for large‐scale resource sharing and distributed integration. Two main problems arise: how to efficiently allocate resources to tasks and, after this, how to schedule them. In this article we propose to solve the scheduling phase by means of rectangle packing algorithms. In particular, two on‐line rectangle packing algorithms are proposed with the objective of maximizing the system efficiency. A wide computational analysis is provided. The performances of the proposed algorithms are first compared with those of known algorithms on benchmark instances for rectangle packing, and then are evaluated on different Grid scheduling scenarios associated with different processing and dataset environments. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol.44(2), 106–119 2004

Abstract Weighted coloring is a generalization of the well‐known vertex (unweighted) coloring for which a number of exact algorithms have been presented in the literature. We are not aware of any optimal method specifically designed for the minimum‐weighted coloring problem on arbitrary graphs. Only a few heuristics have been developed with the goal of finding tighter upper bounds for the maximum‐weighted clique problem. Moreover, as shown in the paper, a straightforward reduction of a weighted instance into an unweighted one permits us to solve only very small instances. In this paper, we present a branch‐and‐bound algorithm for the weighted case capable of solving random graphs of up to 90 vertices for any edge density with integer weights uniformly drawn from the range [1, …,10]. Likewise, we have used properly modified benchmark instances borrowed from vertex coloring as a further test bed for our algorithm. © 2001 John Wiley & Sons, Inc.