oates@jupiter.rtp.dg.com (Tim Oates) (06/10/91)
I'm currently writing a PC based application that will schedule meetings between resources. The task is very similar to the process of scheduling students for classes in high school - students and teachers cannot be in more than one class at a time, a room cannot have more than one class in it at a time, etc. The problem which leads to the question I have is that there are also a great number of constraints that I need to take into account that are non-linear. By non-linear I mean that they do not fall neatly into the linear programming model. For example, if A has a meeting with B, C, or D followed by a meeting with someone other than B, C, or D then there must be a Z minute block of free time between those meetings. The question is, is there a standard way of dealing with this? Can someone point me to references? I'm looking into some search algorithms that apply to contraint satisfaction problems but I'm afraid that they will be much too slow on a PC. Any help would be greatly appreciated. -tim email -- oates@dg-rtp.dg.com #include <std-disclaimer>
ahlenius@motcid.UUCP (Mark Ahlenius) (06/12/91)
oates@jupiter.rtp.dg.com (Tim Oates) writes: >I'm currently writing a PC based application that will schedule >meetings between resources. The task is very similar to the process of >scheduling students for classes in high school - students and teachers >cannot be in more than one class at a time, a room cannot have more than one >class in it at a time, etc. The problem which leads to the question I have >is that there are also a great number of constraints that I need to take into >account that are non-linear. By non-linear I mean that they do not fall >neatly into the linear programming model. For example, if A has a meeting >with B, C, or D followed by a meeting with someone other than B, C, or D then >there must be a Z minute block of free time between those meetings. >The question is, is there a standard way of dealing with this? Can someone >point me to references? I'm looking into some search algorithms that apply >to contraint satisfaction problems but I'm afraid that they will be much too >slow on a PC. Any help would be greatly appreciated. > -tim Several books come to mind on this. 1). "Constraint-Directed Search, A case study of job-shop scheduling" by Mark Fox. Pitman/Morgan Kaufmann 2). Constraint Satisfaction in Logic Programming by Can Hentenryck mit press 1989 3). CONSAT: A System for COnstraint Satisfaction, by Hans Werner Gusgen also from Pitman/Morgan Kaufmann 4). Handbook of Genetic Algorithms edited by Lawrence Davis, Van Nostrand Reinhold 1991 These are just a few of ones that I am aware of. Be somewhat wary of scheduling problems as you might know they can easily become np-complete and can thus get too constrained by your constraints unless they can be relaxed somehow. The last reference on Genetic Algorithms has an interested chapter about a scheduling system for creating schedules for a specific laboratory (complex). It is a completely different approach (fresh idea) to this problem hope this helps 'mark -- =============== regards 'mark ============================================= Mark Ahlenius voice:(708)-632-5346 email: uunet!motcid!ahleniusm Motorola Inc. fax: (708)-632-2413 Arlington, Hts. IL, USA 60004