In decision support systems, human-machine interaction is essential. With no interaction, such a system is only a black box that can only take into account internal data, decide and inform the outside operator. Interaction really allow a real dialog between the system and the user: the operator drives the system which takes into account that outside information, makes a decision and wait from some other input from the operator.

In online scheduling system, user input is crucial. Indeed, computing an optimal resource allocation once and for all is not sufficient. A feasible scheduling is to be maintained while outside input is taken into account: machine breakdown, priority changes, ...

Classical shop problems (Open Shop, Flow Shop and Job Shop) are widely present in real-world applications (telecommunications, hospital planning, ... ). No commercial system is available for solving such problems in an interactive environment.

DynSPS (Dynamic Scheduling Problem Solver) is a demonstration tool ¹  of the DECorum explanation-based constraint solver. It can solve dynamic shop-scheduling problem (constraints can be added dynamically) up to 10 jobs and 10 machines. Moreover, explanations are also used for providing information about failures to obtain a feasible schedule after an alteration.

DynSPS features include:

• Definition, loading, saving of job-shop, flow-shop and open-shop instances up to 10 machines and 10 jobs.

• Computation of heuristic solutions to those problems: a list heuristic and a matching heuristic (both from [Guéret and Prins, 1998]).

• Computation of the optimal makespan of a given problem using an algorithm based on MAC-DBT i.e. a classical branch and bound tree search improved with repair techniques (see [Jussien and Guéret, 1999]).

• Dynamic addition of new constraints (precedence, release date or due date) with an automatic computation of a new feasible solution. Note that this computation does not start from scratch and uses as much as possible previous work done during solving.

• Explanations upon failures.

DynSPS is available here: DynSPS.zip [269 Kb]. DynSPS is freeware but is no longer maintained and is provided as is. Beware, the software is in French (sorry !).

Contents

• dynsps.exe : a Windows (95,98,2000,NT) application
• os.dsp : an open-shop (4x4) scheduling problem example file
• js.dsp : a job-shop (3x3) scheduling problem example file

• Installation Just unpack the archive ... see the download instructions for contents.

• Launch the dynsps.exe file. The first thing to do is to either load (using CTRL+0 or Fichier|Ouvrir commands) or create (using CRTL+D or Problème|Données commands) a problem.

• You can review and edit the current data by using the CTRL+D or or Problème|Données commands

• You can solve the current problem using:
  • CTRL+M or Problème|Résolution|Couplages for a maching-based heuristic
  • CTRL+L or Problème|Résolution|Static List Repeat for a list-based heuristic
  • CTRL+B or Problème|Résolution|Optimisation for an optimal solution

• Once solved, two GANTTs are displayed with the current solution. The color code is quite simple: on the upper part (the machine GANTT), the color of the tasks are the one of their associated job (legended in the lower part) and vice versa for the lower part. It looks like this (of course it does not appear with the incrusted legend):
  

• Dynamic information is added by right clicking on a task, choosing one of the three options (setting a lower due date - avancer, setting a higher release date - repousser or adding a precedence constraint séquencer). For the last option, a tracking window confirming the choice ... just click on the task you would like to see after the one you selected at first. Note that the option menu offers a fourth option: accessing information about the task.

• After adding a few random constraints, a contradiction should occur. The system provides you a list of responsible constraints (hopefully not all the added constraints thanks to precise explanations). Just choose one to relax and the system will try to find another solution. If you do not want to relax any solution, you need to let the system find a worse solution. Use CTRL+U or Problème|Modifications|Borne supérieure to modify the upper bound of acceptable solutions and try adding your constraint (the list is modified letting you removing the constraint on the makespan (fin).

• One last feature: you can freeze some part of the schedule to prevent modifications on already executed parts of the schedule. Use CTRL+G or Problème|Modifications|Geler to set the part that will not get modified (its representation changes).