Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!paperboy!think.com!zaphod.mps.ohio-state.edu!casbah.acns.nwu.edu!ftpbox!white!motcid!ahlenius
From: ahlenius@motcid.UUCP (Mark Ahlenius)
Newsgroups: comp.ai
Subject: Re: scheduling question
Message-ID: <6585@turquoise.UUCP>
Date: 12 Jun 91 15:14:26 GMT
References: <1991Jun10.130741.20086@dg-rtp.dg.com>
Organization: Motorola Inc., Cellular Infrastructure Div., Arlington Heights, IL
Lines: 51

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