Nazli Naraghi
Institut fuer Informationssysteme, Technische Universitaet Wien
E184/2, Paniglg. 16, A-1040 Vienna, Austria
On February 11, 1997 a workshop on Approximate Reasoning on Scheduling
was held at Swiss Federal Institute of Technology (ETH)
Zurich. Organiser of the workshop was Wolfgang Slany of Technical
University of Vienna, Austria. All presentations were given in
English. Twenty researchers from fourteen countries attended the
workshop.
1 Presentations
Approximate Scheduling for Real-time Multimedia Applications:
Wynne Hsu (http://www.dbai.tuwien.ac.at/ftp/ars/ars97/photos/p013.jpg) of
National University of Singapore presented an approximate scheduling
algorithm for multimedia applications that attempts to derive a good
schedule for multimedia processes even under overload condition and a
model which is able to quantify the trade off between conflicting
goals in multimedia applications.
Employing Interactivity and Visualisation to Augment the Process
of Machine-Based Rescheduling:
George Melissargos (http://www.dbai.tuwien.ac.at/ftp/ars/ars97/photos/p012.jpg)
of Swiss Federal Institute of Technology at Lausanne argued about the
advisability of interactive visualisation as a means to increase the
effectiveness of an intelligent system and presented a generic
framework for solving rescheduling problems.
Optimal Polynomial Schedules: An Approach via Non-Smooth Optimisation:
Wolfgang Achtziger (http://www.dbai.tuwien.ac.at/ftp/ars/ars97/photos/p011.jpg)
of University of Erlangen-Nuerenberg, Germany presented a theoretical
and numerical approach to the problem of automatically constructing
optimal polynomial schedules for recurrence equations by employing
methods from non-smooth optimisation.
The GST Load Balancing Algorithm for Parallel and Distributed
Systems:
David Sinclair (http://www.dbai.tuwien.ac.at/ftp/ars/ars97/photos/p010.jpg)
of Dublin City University presented a new dynamic algorithm for the
generalised load balancing problem. The algorithm, the GST algorithm,
is a novel and efficient method for dynamically partitioning a set of
N interdependent, intercommunicating tasks that form the parallel or
distributed program among M processing nodes connected in a given
topology.
Mathematical Modeling of Material and Information Flow:
Kurt Hingerl (http://www.dbai.tuwien.ac.at/ftp/ars/ars97/photos/p009.jpg)
of Profactor GesmbH, Steyr, Austria presented a model of a multilevel
production process where complicated interdependencies and precedence
relations exist between end-products and components.
Models for Interactive Scheduling:
Guenther Schmidt (http://www.dbai.tuwien.ac.at/ftp/ars/ars97/photos/p007.jpg)
of Universitaet des Saarlandes, Germany presented a solution to find a
conflict-free set of constraints using ideas from soft computing and
applied this approach within an interactive scheduling framework.
Sequencing with Neighbourhood Preferences:
Claudia Leopold (http://www.dbai.tuwien.ac.at/ftp/ars/ars97/photos/p005.jpg)
of Friedrich-Schiller-Universitaet Jena, Germany presented the problem
of bringing N operations into sequence, with the aim of realizing
neighbourhood preferences.
A Genetic Multi-Criteria Approach to Job Shop Scheduling:
David Naso (http://www.dbai.tuwien.ac.at/ftp/ars/ars97/photos/p004.jpg)
of Politecnico di Bari presented a combination of fuzzy set theory and
genetic algorithms to face scheduling problems in the job shop
environment.
Configuration, Mapping and Sequencing by Genetic Algorithm:
Klaudia Dussa-Zieger (http://www.dbai.tuwien.ac.at/ftp/ars/ars97/photos/p003.jpg)
from University of Erlangen-Nuernberg, Germany presented an optimal
configuration method for parallel hardware. An approach for the
simultaneous optimisation of all components using genetic algorithms
was presented and its performance was evaluated in comparison with an
exact reference method based on a branch-and-bound-with-underestimates
algorithm.
2 Panel Discussion
After the evening break a forum with sandwiches was held as a panel
discussion.
A remark from many participants was that it would be very useful to
define some common ground of what exactly is meant by approximation
and approximate reasoning in scheduling. One aspect was seen in the
approximate modelling of a concrete problem, i.e., trying to model
those aspects of a problem most relevant to the solution one looks
for. Another aspect was seen as lying in the approximative search for
a solution given a mathematical model that is assumed to be correct,
because the exact solution is too difficult to find for complexity
reasons. So the first aspect focuses on approximating reality, whereas
the second one focuses on approximating the exact solution of the
model. Both aspects are equally important when trying to solve
real-world scheduling problems. In order to increase awareness
regarding those two aspects, this report includes some references
covering both aspects that might help clarify some of the issues
addressed during the forum.
3 Conclusion
The workshop was well organised and the organisers were successful in
bringing together many researchers in the field of approximate
scheduling problems. It was especially productive due to the amount of
interaction between the participants.
References
[1] J. Blazewicz, K. H. Ecker, E. Pesch, G. Schmidt, and J. Weglarz: 1996,
Scheduling Computer and Manufacturing Processes. Springer Verlag.
[2] M. Dell'Amico, F. Maffioli, and S. Martello (ed.): due June 1997,
Annotated bibliographies in combinatorial optimization. John Wiley &
Sons Ltd, UK. Preliminary version available through
mailto:maffioli@elet.polimi.it
[3] M. Fox and M. Zweben: 1994, Intelligent Scheduling. Morgan Kaufmann.
[4] D. S. Hochbaum (ed.): 1996, Approximation algorithms for NP-hard
problems. PWS Publishing Company, Boston, MA. The first chapter covers
approximation of scheduling problems.
[5] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and
D. B. Shmoys: 1993, Sequencing and Scheduling: Algorithms and
Complexity. In: Logistics of Production and Inventory, Handbooks in OR
& MS Vol. 4, pp. 445-522.
[6] W. Slany: 1996, Scheduling as a Fuzzy Multiple Criteria
Optimization Problem. Fuzzy Sets and Systems 78: 197-222.
http://www.dbai.tuwien.ac.at/ftp/papers/slany/fss96.ps.gz
#####################################################################
Information service for ARS'97, Approximate Reasoning in Scheduling.
See also http://www.dbai.tuwien.ac.at/events/ars97.html