Volume 7, Number 1, Spring 2012

EN:

This paper presents a generalization of the coupled-task sche-duling problem introduced by Shapiro [12], where considered tasks are subject to incompatibility constraints depicted by an undirected graph. The motivation of this problem comes from data acquisition and processing in a mono-processor torpedo used for underwater exploration. As we add the compatibility graph, we focus on complexity of the problem, and more precisely on the boundary between P and N P-completeness when some other input parameters are restricted (e.g. the ratio between the durations of the two sub-tasks composing a task): we adapt the global visualization of the complexity of scheduling problems with coupled-task given by Orman and Potts [11] to our model, determine new complexity results, and thus propose a new visualization including incompatibility constraints. In the end, we give a new polynomial-time approximation algorithm result which completes previous works.

EN:

The Boolean optimization problem (BOOP) is a highly useful formulation that embraces a variety of 0-1 integer programming problems, including weighted versions of covering, partitioning and maximum satisfiability problems. In 2006 an adaptive memory (tabu search) method for BOOP was introduced, and was proved to be effective compared to competing approaches. However, in the intervening years, major advances have taken place in exact solvers for integer programming problems, leading to widely publicized successes by the leading commercial solvers XPRESS, CPLEX and GUROBI. The implicit message is that an alternative methodology for any broad class of IP problems such as BOOPs would now be dominated by the newer versions of these leading solvers. We test this hypothesis by performing new computational experiments comparing the tabu search method for the BOOP class against XPRESS, CPLEX and GUROBI, and documenting improvements provided by the exact codes. The outcomes are somewhat surprising.

EN:

The Generalized Traveling Salesman Problem (GTSP) is an extension of the well-known Traveling Salesman Problem (TSP), where the node set is partitioned into clusters, and the objective is to find the shortest cycle visiting each cluster exactly once. In this paper, we present a new hybrid Ant Colony System (ACS) algorithm for the symmetric GTSP. The proposed algorithm is a modification of a simple ACS for the TSP improved by an efficient GTSP-specific local search procedure. Our extensive computational experiments show that the use of the local search procedure dramatically improves the performance of the ACS algorithm, making it one of the most successful GTSP metaheuristics to date.

EN:

In the paper we mainly study the makespan problem of scheduling n groups of jobs on n special-purpose processors and m general-purpose processors at different speeds. We first propose an improved LPT algorithm and investigate several properties of this algorithm. We then obtain an upper bound for the ratio of the approximate solution T to the optimal solution T^* under the improved LPT algorithm.