Vol. 26 - Year 2001 Abstracts

J. Błażewicz, P. Formanowicz, M. Kasprzak, K. Michalak, P. Wierzejewski:

Clustal W algorithm for multiple sequence alignment revisited

Abstract

Multiple sequence alignment is one of the most important problems arising in DNA and protein recognition. Clustal W is a well known and practically applied method used for solving the problem. In the paper, a modification of the algorithm is described which shortens considerably its mean running time. The modification uses graphs of partial alignments and operations on resulting semi cliques. As shown by an extensive computational experiments running time is reduced up to 50%, as compared with the original approach.

M. Caramia , P. Dell'Olmo , A. Iovanella:

On-Line Algorithms for Multiprocessor Task Scheduling with Ready Times

Abstract

In this paper we deal with multiprocessor task scheduling with ready times and prespecified processor allocation. In the studied problem tasks are not initially all available in the scheduler and can be executed only by a given ready time. Moreover, a task can be examined in order to be processed only when it enters the scheduler. For this class of problems we developed some algorithms which schedule tasks in the attempt to minimize the makespan. We provide experiments on various scenarios, computing also the mean flow time spent by each task in the system.

M. Haouari:

On the effectiveness of column generation for time constrained routing problems

Abstract

This paper describes how column generation techniques can be used to solve to optimality the Fleet Size and Mix Vehicle Routing Problem with Time Windows (FSMVRPTW). This problem is practically important and computationally challenging. It involves the joint optimization of the fleet mix and the set of delivery routes. The main contribution of this paper is to show, by an appropriate graph transformation, that the approach previously developed for the classical VRPTW, and based upon the use of the set partitioning formulation and the column generation techniques yields very good results for the FSMVRPTW. The proposed approach is the first optimization algorithm developed so far for the FSMVRPTW. Computational results are reported on a set of test problems with up to 80 customers.

M. Sh. Levin:

Digraph description of k-interchange technique for optimization over permutations and adaptive algorithm system

Abstract

The paper describes a general glance to the use of element exchange techniques for optimization over permutations. A multi-level description of problems is proposed which is a fundamental to understand nature and complexity of optimization problems over permutations (e.g., ordering, scheduling, traveling salesman problem). The description is based on permutation neighborhoods of several kinds (e.g., by improvement of an objective function). Our proposed operational digraph and its kinds can be considered as a way to understand convexity and polynomial solvability for combinatorial optimization problems over permutations. Issues of an analysis of problems and a design of hierarchical heuristics are discussed. The discussion leads to a multi-level adaptive algorithm system which analyzes an individual problem and selects / designs a solving strategy (trajectory).