PROGRAM
SUNDAY, May 7, 1995
17.00-20.00 Registration
MONDAY, May 8, 1995
8.00-9.00 Registration
9.00-9.15 Opening
Chair: Jan Weglarz
9.15-10.15 Claude Berge, ON THE OPTIMAL TRANSVERSAL OF THE ODD CYCLES,
invited talk
coffee break
MA1 scheduling
Chair: Peter Brucker
10.30-11.00 Peter Brucker, Bernd Jurisch, Andreas Kr„mer, COMPLEXITY OF
SCHEDULING PROBLEMS WITH MULTI-PURPOSE MACHINES
11.00-11.30 Joanna Jozefowska, Rafal Rozycki, Jan Weglarz, SOLVING A DISCRETE-
CONTINUOUS SCHEDULING PROBLEM WITH A GENETIC ALGORITHM
11.30-12.00 Stanislaw Gawiejnowicz, ON TWO MODELS OF THE DISCRETE-CONTINUOUS
SCHEDULING
12.00-12.30 Eugeniusz Toczylowski, STRUCTURAL ANALYSIS OF COMPLEX TIMETABLING
PROBLEMS
MB1 general combinatorial optimization problems
Chair: Paulo Barcia
10.30-11.00 Matteo Fischetti, Juan Jose Salazar, Paolo Toth, SOLVING THE
ORIENTERRING PROBLEM THROUGH BRANCH-AND -CUT
11.00-11.30 Le Tu Quoc Hung, Maciej M. Syslo, PAGE NUMBER OF PARTIALLY ORDERED
SETS
11.30-12.00 Alberto Caprara, Juan Jose Salazar Gonzßlez, A BRANCH-AND-CUT
ALGORITHM FOR A GENERALIZATION OF THE UNCAPACITATED FACILITY
LOCATION PROBLEM
12.00-12.30 Krzysztof Pienkosz, ON NODE AGGREGATION ALGORITHMS FOR GRAPH
COLORING
MC1 TSP
Chair: Silvano Martello
10.30-11.00 Edo S. van der Poort, Gerard Sierksma, Jack A. A. van der Veen,
SIMULTANEOUS CHANGES OF DISTANCES IN THE SYMMETRIC TRAVELING
SALESMAN PROBLEM
11.00-11.30 Marek Libura, Edo S. van der Poort, ON k-BEST SOLUTIONS AND
SENSITIVITY ANALYSIS FOR THE TRAVELING SALESMAN PROBLEM
11.30-12.00 Victor Lepin, THE TRAVELLING SALESMAN PROBLEM FOR GRAPHS WITH
BOUNDED VERTEX SEPARATOR
12.00-12.30 Vitali Demidenko, AN EXTENSION OF THE SUPNIK CONDITIONS FOR
THE ASYMMETRIC TRAVELING SALESMAN PROBLEM AND ITS APPLICATION
lunch
MA2 scheduling
Chair: Eugeniusz Toczylowski
14.00-14.30 Marek Kubale, DEDICATED SCHEDULING OF PREEMPTABLE DUOPROCESSOR
TASKS WITH RELEASE TIMES TO MINIMIZE SCHEDULE LENGTH
14.30-15.00 Cezary Szwed, Eugeniusz Toczylowski, AN ALGORITHM FOR RESOURCE
DISAGGREGATION IN TIMETABLING PROBLEMS
15.00-15.30 Marek Cyzio, Eugeniusz Toczylowski, ON M-PROCESSOR BASED SCHEDULING
ALGORITHM FOR FMS CELLS
15.30-16.00 Valentina Turchina, PARALLEL SEQUENCING TASKS
MB2 graph theory
Chair: Claude Berge
14.00-14.30 Rainer E. Burkard, Tibor Dudas, Thomas Maier, CUT AND PATCH STEINER
TREES FOR LADDERS
14.30-15.00 Konrad Wala, A BOUNDED APPROXIMATION ALGORITHM FOR GRAPH
PARTITIONING
15.00-15.30 Harald Gropp, BISECTION WIDTH OF GRAPHS AND CONFIGURATIONS
15.30-16.00 Anand Srivastav, HYPERGRAPH MATCHING AND BIN LOCATION IN PRINTED
CIRCUIT BOARD ASSEMBLY
MC2 heuristics
Chair: Paolo Toth
14.00-14.30 Micheal O hEigeartaigh, EUROPEAN CENTRE FOR TEACHING COMPUTING
14.30-15.00 Soren Holm, AN OPTIMUM-CONVERGENT ALGORITHM EMBEDDING A
COMPUTATIONAL GUIDANCE RULE FOR HEURISTICS WHICH SOLVE
COMBINATORIAL PROBLEMS
15.00-15.30 Patrick Soriano, Michel Gendreau, IMPACT OF DIVERSIFICATION IN TABU
SEARCH ALGORITHMS: A STUDY ON THE MAXIMUM CLIQUE PROBLEM
15.30-16.00 Guntram Scheithauer, Johannes Terno, THE G4-HEURISTIC FOR THE
PALLET LOADING PROBLEM
coffee break
MA3 scheduling
Chair: Marek Kubale
16.15-16.45 Maciej Hapke, Roman Slowinski, FUZZY PRIORITY HEURISTICS FOR
PROJECT SCHEDULING
16.45-17.15 Krzysztof Maik, Eugeniusz Toczylowski, AN EFFICIENT ALGORITHM FOR
LOT-SIZE SCHEDULING WITH A SINGLE RESOURCE
17.15-17.45 Anatoly I. Kuksa, (COST, TIME) - LIKE OPTIMIZATION OF THE PROJECT
UNDER FUZZY ACTIVITY'S DATA
MB3 knapsack
Chair: Micheal O hEigeartaigh
16.15-16.45 Silvano Martello, Paolo Toth, EXACT AND APPROXIMATION ALGORITHMS
FOR THE TWO-CONSTRAINT ZERO-ONE KNAPSACK PROBLEM
16.45-17.15 Ligia Amado, Paulo Barcia, TIGHT POLYNOMIAL BOUNDS AND HEURISTICS
FOR MATROIDAL KNAPSACKS
17.15-17.45 Krzysztof Szkatula, ON THE GROWTH OF MULTI-CONSTRAINT BINARY RANDOM
KNAPSACKS
MC3 network flows
Chair: Leon Slominski
16.15-16.45 Grzegorz Ploszajski, A METHOD OF FINDING FEASIBLE MULTICOMMODITY
MULTIROUTE FLOW IN NETWORK BASED ON THE LAGRANGE RELAXATION AND
DECOMPOSITION OF THE PROBLEM
16.45-17.15 Mikolaj Lepieszynski, MAXIMUM STREAM ON SIMPLE NETWORK PATHS
17.15-17.45 Malika Hadjiat, Jean Fran‡ois Maurras, COMPATIBLE CUTS OF MINIMUM
COST AND MINIMUM MEAN COST
TUESDAY, May 9, 1995
Chair: Jacek Blazewicz
8.30-9.30 Gilbert Laporte, THE COVERING TOUR PROBLEM, invited talk
coffee break
TA1 scheduling
Chair: Klaus Ecker
9.45-10.15 Marcus Pattloch, Gunter Schmidt, APPROXIMATION ALGORITHMS FOR
LOTSIZE SCHEDULING
10.15-10.45 Sri V Sridharan, Zhuoqun Zhou, TACTICALLY DELAYED SCHEDULING IN
A DYNAMIC SINGLE MACHINE SYSTEM
10.45-11.15 Adam Janiak, Mikhail Y. Kovalyov, SINGLE MACHINE GROUP SCHEDULING
WITH ORDERED CRITERIA
11.15-11.45 Valery Gordon, MINIMIZING MAXIMUM TARDINESS WITH DUE-DATE ASSIGNING
IN A SINGLE MACHINE SCHEDULING
TB1 processor allocation
Chair: Gilbert Laporte
9.45-10.15 Jacek Blazewicz, Rafal Walkowiak, Pascal Bouvry, Denis Trystram,
A TABU SEARCH FOR THE MAPPING PROBLEM
10.15-10.45 Franciszek Seredynski, EVOLUTIONARY APPROACH TO SCHEDULING TASKS ON
MULTIPROCESSORS
10.45-11.15 Thierry Mautor, A COMPARISON OF DIFFERENT PARALLEL TABU SEARCHES
APPLIED TO THE TASK ALLOCATION PROBLEM
11.15-11.45 Grazyna Grygiel, ASYNCHRONOUS PARALLEL ALGORITHM FOR ALGEBRAIC
ASSIGNMENT PROBLEMS
TC1 assignment
Chair: Maciej M. Syslo
9.45-10.15 Eberhard Girlich, M.M.Kovalev, A.A.Zaporozhets, A POLYNOMIAL
ALGORITHM FOR RESOURCE ALLOCATION PROBLEMS
10.15-10.45 Ulrich Pferschy, COMPUTATIONAL ANALYSIS OF THE LINEAR BOTTLENECK
ASSIGNMENT PROBLEM
10.45-11.15 Jaroslaw Sikorski, SOLVING SET COVERING PROBLEMS WITH SURROGATE
CONSTRAINTS
11.15-11.45 Gennady G. Zabudsky, ON THE ONE-DIMENSIONAL SPACE ALLOCATION
PROBLEM
lunch
13.00 Vicinity of Poznan, excursion
19.00 Meeting of the ECCO board
WEDNESDAY, May 10, 1995
Chair: Catherine Roucairol
8.30-9.30 Gerd Finke, SCHEDULING MODELS WITH VARIABLE PROCESSING TIMES,
invited talk
WA1 scheduling
Chair: Gunter Schmidt
9.45-10.15 Klaus Ecker, Martina Kratzsch, TASK SCHEDULING UNDER CONSIDERATION
OF COMMUNICATION DELAYS
10.15-10.45 Frederic Guinand, SCHEDULING TREES ON TWO UNIFORM PROCESSORS
10.45-11.15 Jacek Blazewicz, Maciej Drozdowski, DISTRIBUTED PROCESSING OF
DIVISIBLE JOBS WITH COMMUNICATION STARTUP COSTS
WB1 polyhedra
Chair: Jerzy Nawrocki
9.45-10.15 Lorenzo Brunetta, Michele Conforti, Matteo Fischetti, A POLYHEDRAL
APPROACH TO AN INTEGER MULTICOMMODITY FLOW PROBLEM
10.15-10.45 Eberhard Girlich, G. Bolotashvili, M. M. Kovalev, THE POSET
POLYTOPE
10.45-11.15 Michael M. Sorensen, A POLYHEDRAL APPROACH TO GRAPH PARTITIONING
WC1 general combinatorial optimization problems
Chair: Roman Slowinski
9.45-10.15 Yuri N. Sotskov, STABILITY ANALYSIS IN COMBINATORIAL OPTIMIZATION
10.15-10.45 Vladimir Emelichev, Michail Kravtcov, Dmitriy Podkopaev, STABILITY,
PSEUDO-STABILITY AND QUASI-STABILITY OF MULTICRITERION PROBLEMS OF
DISCRETE OPTIMIZATION
10.45-11.15 Marian Chudy, COMBINATORIAL METHODS IN PLANNING SELECTED MILITARY
ACTIVITY
coffee break
WA2 scheduling
Chair: Sri V.Sridharan
11.30-12.00 Maciej Drozdowski, Wieslaw Kubiak, SCHEDULING MULTIPROCESSOR TASKS
WITH SEQUENTIAL HEADS AND TAILS
12.00-12.30 Tadeusz Nowicki, A STOCHASTIC PROBLEM OF CYCLIC MULTIPROCESSOR
SCHEDULING WITH FINITE NUMBER OF DEPENDENT JOBS
12.30-13.00 Vladimir Servakh, DYNAMIC PROGRAMMING ALGORITHMS FOR SOME
SCHEDULING PROBLEMS
WB2 polyhedra
Chair: Vitaly A.Strusevich
11.30-12.00 Jean Fran‡ois Maurras, SUPPORTING HYPERPLANES AND THE STRONG
SOLUTION PROBLEM
12.00-12.30 Eberhard Girlich, M. M. Kovalev, Dima. M. Vasilkov, GREEDINESS AND
PARTIAL ORDERS
12.30-13.00 Alexander A. Kolokolov, ON L-STRUCTURE OF SOME DISCRETE
OPTIMIZATION PROBLEMS
WC2 general combinatorial optimization problems
Chair: Eberhard Girlich
11.30-12.00 Hanna Pietkiewicz-Saldan, THE STRUCTURE OF A GEOGRAPHICALLY
DISTRIBUTED ORGANISATION
12.00-12.30 Nikolai Metelski, COMBINATORIAL OPTIMIZATION METHODS IN
COMPUTATIONAL GEOMETRY
12.30-13.00 Victor P. Il'ev, ON THE MATROIDAL APPROXIMATION PROBLEM
lunch
WA3 scheduling
Chair: Wieslaw Kubiak
14.30-15.00 Moshe Dror, Janny Leung, Paul A. Mullaseril, ROUTING AND SCHEDULING
FOR LIVESTOCK FEED DISTRIBUTION
15.00-15.30 Peter Cowling, AN ADAPTIVE TABU SEARCH HEURISTIC WITH MULTI-
CRITERIA ASPIRATION FOR SCHEDULING STEEL HOT ROLLING MILL
PRODUCTION
15.30-16.00 Alexander Uzdemir, DYNAMIC INTEGER PROBLEMS OF DISCRETE PRODUCTION
PLANNING
WB3 network design
Chair: Gerd Finke
14.30-15.00 Anne De Jongh, Michel Gendreau, Martine Labbe, MINIMUM COST
EXPANSION AND FINDING DISJOINT ROUTES IN TELECOMMUNICATION NETWORKS
WITH TWO TECHNOLOGIES
15.00-15.30 Bernard Fortz, Martine Labbe, Francesco Maffioli, MINIMUM-WEIGHT
TWO-CONNECTED NETWORKS WITH BOUNDED CYCLE LENGTHS
15.30-16.00 Christelle Wynants, Michel Gendreau, Martine Labbe, Rene Seguin,
OPTIMIZING RESERVE CAPACITIES OF A TELECOMMUNICATION NETWORK IN
THE PRESENCE OF CROSS-CONNECT
WC3 general combinatorial optimization problems
Chair: Valery Gordon
14.30-15.00 Leon Slominski, INTEGER VARIABLE TECHNIQUES IN MODELLING FINANCIAL
DECISIONS
15.00-15.30 Jurgen Schulze, MASSIVELY PARALLEL SPARSE CHOLESKY FACTORIZATION
15.30-16.00 Gabriele Schneidereit, THE CONE OF RANK FUNCTIONS OF POLYMATROIDS
coffee break
WA4 scheduling
Chair: Moshe Dror
16.15-16.45 Vitaly A. Strusevich, Djamal Rebaine, OPEN SCHOP SCHEDULING PROBLEMS
WITH TRANSPORTATION TIMES
16.45-17.15 Irene N. Lushchakova, OPEN SHOP PROBLEMS WITH RENEWABLE RESOURCE
CONSTRAINTS
17.15-17.45 Svetlana A. Kravchenko, ON THE TWO-MACHINE UNIT-TIME JOB-SHOP
SCHEDULING PROBLEM
WB4 graph theory
Chair: Jean Fran‡ois Maurras
16.15-16.45 Mario Lucertini, Gaia Nicosia, THE SHORTEST LINE PROBLEM:
THE SHORTEST COMMON SUPERSEQUENCE OF A SET OF COMBS
16.45-17.15 Matthias Ehrgott, Jorg Freitag, NUMERICAL RESULTS FOR THE
K-CARDINALITY TREE AND K-CARDINALITY SUBGRAPH PROBLEM
17.15-17.45 Natalya Efimchik, Dmitriy Podkopaev, STABILITY KERNEL OF
TRAJECTORIAL PROBLEM OF VECTOR DISCRETE OPTIMIZATION
WC4 general combinatorial optimization problems
Chair: Adam Janiak
16.15-16.45 Yakov M.Shafransky, Mikhail Y.Kovalyow, PARALLEL SCHEDULING OF
UNIT-TIME JOBS SUBJECT TO RESOURCE CONSTRAINTS
16.45-17.15 Eberhard Girlich, Michael Hoding, CONES OF SUBMODULAR AND
BISUBMODULAR FUNCTIONS
17.15-17.45 Hacene Ait Haddadene, Frederic Maffray, COLORING PERFECT
DEGENERATE GRAPHS
18.00 Closing
MM - Apr 26, 1995