Constrained graph transformation in scheduling applications

Question

I'm working on an interactive job scheduling application. Given a set of resources with corresponding capacity/availabilty profiles, a set of jobs to be executed on these resources and a set of constraints that determine job sequence and earliest/latest start/end times for jobs I want to enable the user to manually move jobs around. Essentially I want the user to be able to "grab" a node of the job network and drag that forwards/backwards in time without violating any of the constraints.

The image shows a simple example configuration. The triangular job at the end denotes the latest finish time for all jobs, the connecting lines between jobs impose an order on the jobs and the gray/green bars denote resource availabilty and load.

You can drag any of the jobs to compress the schedule. Note that jobs will change in length due to different capacity profiles.

I have implemented an ad-hock algorithm that kinda works. However there are still cases where it'll fail and violate some constraints. However, since job-shop-scheduling is a well researched field with lots of algorithms and heuristics for finding an optimal (or rather good) solution to the general NP-hard problem - I'm thinking solutions ought to exist for my easier subset. I have looked into constraint programming topics and even physics based solutions (rigid bodies connected via static joints) but so far couldn't find anything suitable. Any pointers/hints/tips/search key words for me?

Answer 1

You could probably alter the Waltz constraint propagation algorithm to deal with changing constraints to quickly find out if a given solution is valid. I don't have a reference to hand, but this might point you in the right direction: http://www.sciencedirect.com/science?%5Fob=ArticleURL&%5Fudi=B6TYF-41C30BN-5&%5Fuser=809099&%5Frdoc=1&%5Ffmt=&%5Forig=search&%5Fsort=d&%5Fdocanchor=&view=c&%5FsearchStrId=1102030809&%5FrerunOrigin=google&%5Facct=C000043939&%5Fversion=1&%5FurlVersion=0&%5Fuserid=809099&md5=696143716f0d363581a1805b34ae32d9

Answer 2

I highly recommend you take a look at Mozart Oz, if your problem deals only with integers. Oz has excellent support for finite domain constraint specification, inference, and optimization. In your case typically you would do the following:

1. Specify your constraints in a declarative manner. In this, you would specify all the variables and their domains (say V1: 1#100, means V1 variable can take values in the range of 1--100). Some variables might have values directly, say V1: 99. In addition you would specify all the constraints on the variables.

2. Ask the system for a solution: either any solution which satisfies the constraints or an optimal solution. Then you would display this solution on the UI.

3. Lets say the user changes the value of a variable, may be the start time of a task. Now you can go to step 1 to post the problem to the Oz solver. This time, solving the problem most probably will not take as much time as earlier, as all the variables are already instantiated.

   It may be the case that the user chose a inconsistent value. In that case, the solver returns null. Then, you can take the UI to the earlier solution.

If Oz suits your need and you like the language, then you may want to write a constraint solver as a server which listens on a socket. This way, you can keep the constraint solver separate from the rest of your code, including the UI.

Hope this helps.

Answer 3

Have you considered using an Integer Linear Programming engine (like lp_solve)? It's quite a good fit for scheduling applications.

Answer 4

I would vote in favor of constraint programming for several reasons:

1) CP will quickly tell you if there is no schedule that satifies your constraints

2) It would appear that you want to give you users a feasible solution to start with but allow them to manipulate jobs in order to improve the solution. CP is good at this too.

3) An MILP approach is usually complex and hard to formulate and you have to artificially create an objective function.

4) CP is not that difficult to learn especially for experienced programmers - it really comes more from the computer science community than the operations researchers (like me).

Good luck.