**Subject: **Conference Report on ARS97 (Approximate Reasoning in Scheduling)

**From: **Wolfgang Slany (*wsi@dbai.tuwien.ac.at*)

**Date: **Tue Mar 25 1997 - 18:40:27 MET

**sorted by:**[ date ] [ thread ] [ subject ] [ author ]**Next message:**Chris Beck: "Research Position: Constraint-Directed Scheduling"**Previous message:**Steel S W D: "CFP: Fourth European Conference on Planning ECP '97 (EWSP '97)"

Conference Report on the First International Workshop on

Approximate Reasoning in Scheduling

ARS'97

Nazli Naraghi

Institut fuer Informationssysteme, Technische Universitaet Wien

E184/2, Paniglg. 16, A-1040 Vienna, Austria

http://www.dbai.tuwien.ac.at/events/ars97.html

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. The workshop was sponsored by Swiss

Federal Institute of Technology (ETH), Zurich, Switzerland, ICSC,

International Computer Science Conventions, Canada, Christian Doppler

Laboratory for Expert Systems, Vienna, Austria, and ERUDIT Special

Interest Group (SIG) on Fuzzy Information Engineering. 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. Revised versions of the papers

will be invited for a special issue of the International Journal of

Approximate Reasoning.

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

**Next message:**Chris Beck: "Research Position: Constraint-Directed Scheduling"**Previous message:**Steel S W D: "CFP: Fourth European Conference on Planning ECP '97 (EWSP '97)"

*
This archive was generated by hypermail 2b25
: Fri Mar 03 2000 - 16:17:12 MET
*