Thomas Sjoland

The Swedish Institute of Computer Science is a non-profit research organisation funded by FDF, a group of major companies and organisations containing Ericsson, Telia, CelsiusTech, Sun, IBM, SJ and FMV. SICS is also supported by a group of smaller companies and by the Swedish government through the agency NUTEK. Apart from the frame-program funded thus, our projects are funded from external sources to a large extent, e.g. by participating in the European research and development programs such as ESPRIT, or with direct projects with industrial funding.

The research activities at SICS are mostly driven by expressed needs of the industrial sponsors and other outside partners (companies, government agencies etc.). Our task is, apart from participating in the research, also to find ways in which relevant research in modern information technology and also practical experiences of utilizing it can be tested and perhaps implemented in the information environments of those partners. The research should fit the activity profile of the partners, and be interesting and promising enough to attract funding.

The use of constraints, especially constraint logic programming, is strongly founded in the European research community [Colmerauer] and the strongest toolmaking companies are also based in Europe. The areas of planning and scheduling are highly interesting for many companies, since they are instrumental to successful business process re-engineering activities, by providing a practical route to success for many new ideas in economic control of the activities of a company/organisation.

The main partners with which we are currently actively using constraint logic programming are Ovako Steel, a part of SKF, one of the world-leading companies in steel production, and SJ, the Swedish state railway company, dominating the Swedish railway market. Anything we say here are our interpretations of the situation and may or may not coincide with the judgments of representatives of these companies. Of course we benefit also from research done in other projects at SICS, for instance the PERDIO project [Haridi] on distributed Oz run in cooperation between SICS and DFKI [Smolka].

Constraint Based Business Modeling Support Tools

In a more and more competitive world it becomes increasingly importantfor managers to have an objective and correct valuation of the activities under their jurisdiction. Business modelling is therefore increasingly turning towards the use of IT-support to enable and monitor the implementation of strategies and tactics of business process re-engineering projects. By using decision support systems, the different human actors in e.g. a company gets help in orienting their behaviours and judgments based on clearly defined procedures, rather than relying on subjective and unformalized measures. Apart from mere algorithmic efficiency of proposed systems, it is also essential thatthe modelling used in such tools is transparent, so that the user can understand what is going on behind the computer screen. The rapidly changing environments of many companies creates a requirement to alter the economic models,and thereby perhaps the tools used, ever more frequently. Constraint logic programming with its basis in rapid prototyping and logical semantics has a potential to be a powerful enabling technology in the constructions of such models and tools, and in fact is already used thus in many cases [Simonis].

Distributed systems for decision support in planning/scheduling/economy

The developments in network software technology allows a company to have a distributed but still connected system as the basis of its economic activities. For some companies this is indeed an enabling factor, since the speed and accuracy with which the work can be performed is drastically increased while a large amount of the travel costs can be reduced.

Production planning in the steel factory at Ovako,

the ESPRIT trial application project TACIT

In the project TACIT, a trial application of constraints we utilize SICStus Prolog to implement a realistic model of the production in a steel plant as a basis for support tools in both planning and scheduling. The tools might be integrated in the IT-infrastructure of Ovako, which in fact will be the litmus test for the choices made. FD-constraints are essential for this work. More details can be found in http://www.sics.se/col/projects/tacit

Distributed decision support for transport planning/scheduling at SJ

In an effort to study the use of modern information technology in the planning/scheduling activities of a major railway company we have identified some important areas where constraint techniques might be

beneficial as a complement to OR-techniques [Bussieck]. In a prototype implemented in Oz2 [Kreuger et al] we have attacked the problems of generating safe timetables for a set of ordered transports. The transport orders are expressed with FD-constraints. One main problem is complexity. By allowing the output of the timetabling algorithm be of exactly the same format as the input we allow partitioning the set of transport orders and also iterative planning where new transport orders are added to a schedule. Ongoing experiments show that this enables a flexible tool, that can be used interactively to test various combinations of transport orders with the same size as those problems solved by the railroad company's own planners. In this scenario constraint relaxation is treated manually, i.e. via a GUI controlled by the user. Another problem is choosing a realistic level of detail for the modeling. We have the choice of whether to model the exact transactions that occur in a station. E.g. we model the amount of tracks that can maximally be allocated to a train at any time interval. This resource constraint is efficiently modelled with a cumulative constraint [Simonis2].

Rostering of engines [Drott]

Another essential problem in railroad planning is the allocation of (types of) engines to transports. This turns out to be a variant of the set-partitioning problem. It is also well known and is traditionally attacked with OR techniques [Bussieck]. Using constraint for this problem have been tested, but comparative results are not all that encouraging [Simonis1]. A novel approach to guaranteeing location continuity has been tried out in the essentially isomorphic context of fleet scheduling for an airline company, using exclusion constraints [Simonis3], but even there the approach assumes that a timetable exists before the allocation of transport vehicles can occur. The reported problem sizes are rather limited. We currently experiment with an integration of the rostering problem with the timetabling problem, where the ordering of the transports incurred by the rostering model limit the constraints of the timetabling. A similar problem is that of allocating crew to transports. This problem is complicated by various constraints e.g. based on legal aspects of working hours etc. and is not attacked in our current project.

How to relate to OR-techniques

There are today advanced OR-based tools in operation which e.g. can minimize the utilisation of engines for a given batch of transportation orders. The CARMEN system to be used by the Swedish railroad is an OR-based tool described in http://www.carmen.se/. According to recent experiments [Drott] such tools can perform even better than the human experts on the same realistic data sets. A challenge for the constraint community is to find methods and tools that show a similar efficiency and at the same time can attack realistic problem sizes. Currently we see the strongest advantage of constraint techniques in the possibility of constructing interactive tools with a significant part of domain knowledge incorporated, and also in the relatively natural formulation of the problems encouraged by the constraint technology. For the time being we suggest using OR-tools for optimization, while constraint based tools are suitable for interactive support systems that generate any feasible model, and for rapid prototyping. This does not mean that OR is "better" than constraints, just that we should focus our interest on applications in areas where constraints promise to give a competitive advantage.

Conclusion

We have discussed the activities relating to constraints in the COL group of SICS. The area is healthy and growing, since we are able to identify industrial interests in the technology and get concrete problems by our industrial partners to use in our research efforts. We are also greatly helped by the vast amount of expertise that have already elaborated the fundamentals of this area before we focused our attention in this direction. Without the efforts in fundamental research and the efforts in making practical tools out of those efforts, constraint logic programming would still be a largely academic endeavor for a minor group of researchers. Given that the constraint area continues to position itself properly in the marketplace, it has the chance of becoming one of the leading software technologies of the near future.

References

Bronnlund U., Lindberg P.O., Nuu A., Nilsson J.E. Railway timetabling using Lagrangian relaxation, November 1996

Bussieck M.R.., Winter T., Zimmermann U.T., Discrete optimization in public rail transport. In Mathematical Programming 79 (1997) 415-444

Christodoulou N., Stefanitsis E., Kaltsas E., Assimakopoulos V., A Constraint Logic Programming Approach to the Vehicle-Fleet Scheduling Problem. In Practical Applications of Prolog PAP'94

Colmerauer,A., and Benhamou,F., Eds. Readings in Constraint Logic Programming. MIT Press 1993

Crabtree I.B., Resource Scheduling - comparing simulated annealing with constraint programming. In Practical Applications of Constraint Technology PACT 95

Dalfiume A., Lamma E., Mello P., Milano M., A Constraint Logic Programming Application to a Distributed Train Scheduling Problem. In Practical Applications of Prolog PAP'95

David J.-M., Chew T.-L., Constraint-based applications in production planning; examples from the automotive industry. In Practical Applications of Constraint Technology PACT 95

Davis R., Smith R.G, Negotiation as a Metaphor for Distributed Problem Solving. Journal of Artificial Intelligence 20 (1983) 63--109

Drott J., Hasselberg E., Kohl N., Kremer M., A Planning System for Locomotive Scheduling., Carmen Systems AB.

Fischer K., Muller J.P., Pischel M., Schier D. A Model For Cooperative Transportation Scheduling, German Center for Artificial Intelligence (DFKI), Saarbrucken, Germany. (1995)

Hammer M. Champy J., Reengineering the Corporation, Harper Business, 1993

Haridi S., Smolka G., Van Roy P., An Overview of the Design of Distributed Oz, ACM International Symposium of Parallel Symbolic Computation,1997.

Herold A., Experiences in Constraint Programming from the CHIC User Group. In Practical Applications of Constraint Technology PACT 95

Joborn M., Empty Freight Car Distribution at Swedish Railways - Analysis and Optimization Modeling. Division of Optimization, Lic. Thesis, Dept. of Mathematics, Linkoping University, 1995.

Kaplan R. S., Norton D. P., Using the Balanced Scorecard as a Strategic Management System, Harvard Business Review, January-February 1996, pp 75-85

Kreuger P., Carlsson M., Olsson J., Sjoland T., Estrom E., The TUFF Train Scheduler. At Workshop on Constraint Environments of International Logic Programming Symposium 1997, NY, USA. G. Puebla (coord.)

Kreuger P., Carlsson M., Olsson J., Sjoland T., Estrom E., The TUFF Train Scheduler - Two Duration Trip Scheduling on Single Track Networks. At Workshop on Industrial Constraint-Directed Scheduling at Third International Conference on Principles and Practice of Constraint Programming 1997, Linz, Austria. A. Davenport (ed.)

Martin C., Logistics and Supply Chain Management, Financial Times Pitman Publishing, 1992

Muller, Popov, Schulte, Wurtz, Constraint Programming in Oz, DFKI, Saarbrucken, Germany, 1995

Muller, Wurtz, Finite Domain Programming in Oz. DFKI, Saarbrucken, Germany, 1995.

Olve N.-G., Roy J., Wetter M., Balanced Scorecard, Liber Ekonomi, 1997

Schulte C., Open Programming in Oz, DFKI , Saarbrucken, Germany, 1996.

Smith R.G., The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver. Readings In Artificial Intelligence, pp357--366. (1980)

Simonis H., A Problem Classification Scheme for Finite Domain Constraint Solving. CP'96 applications workshop, COSYTEC SA, Orsay, France.

Simonis H., Calculating Lower Bounds on a Resource Scheduling Problem. COSYTEC SA, Orsay, France.

Simonis H., and Cornelissens T.,Modelling Producer/Consumer Constraints. COSYTEC SA, Orsay, France and Beyers & Partners, Brasschaat, Belgium.

Simonis H., The Use of Exclusion Constraints to Handle Location Continuity Conditions. COSYTEC SA, Orsay, France.

Simonis H., Modeling Machine Set-up Time in CHIP., COSYTEC SA, Orsay, France.

Smolka G., A Survey of Oz, DFKI , Saarbrucken, Germany, 1995

Toth P., Vigo D., "Exact Algorithms for the Vehicle Routing Problem with Backhauls", to appear in Transportation Science.

Caprara A., Fischetti M., Toth P., Vigo D., "Modeling and Solving the Crew Rostering Problem", to appear in Operations Research.

Wallace M., Introducing the Practical Applications of Constraints. In Practical Applications of Constraint Technology PACT 95

Van Marcke K. and Tubbax B., SKAI: A Knowledge Based Environment for Scheduling Traction Equipment and Personnel, KT Memo 94-2

Van Marcke K., Knowledge Based Scheduling with the SKAI Environment KT Memo 94-01

Van Marcke K., Knowledge Based Scheduling: A Case Study, KT Memo 93-3, Knowledge Technologies n.v.

Wurtz, J. Oz Scheduler: A workbench for Scheduling Problems In IEEE International conference on Tools with Artificial Intelligence (ICTAI'96), 1996.