Proposed by Uri Shapen, Roie Zivan, Amnon Meisels
Meeting scheduling is a well-known, recurrent and easily described problem. The meeting scheduling problem (MSP) will be described below as a centralistic constraints satisfaction problem (CSP).
However, one of its most interesting features is the fact that it is a Distributed CSP. Informally, a set of agents want to meet and they search for a feasible meeting time that satisfies the private constraints of each of the agents and in addition satisfies arrival-time constraints (among different meetings of the same agent).
The general definition of the MSP family is as follows:
A group S of m agents A set T of n meetings The duration of each meeting mi is durationi Each meeting mi is associated with a set si of agents in S, that attend it Consequently, each agent has a set of meetings that it must attend Each meeting is associated with a location The scheduled time-slots for meetings in T must enable the participating agents to travel among their meetings The table below presents an example of a MSP, including the traveling time in time-units (say, hours) between different meeting locations.
Meeting Location Attending agents m1 L1 A1,A3 m2 L2 A2,A3,A4 m3 L3 A1,A4 m4 L4 A1,A2
The 27 instances in cspLib have been reformatted and are in the problem directory with one file for each problem. The format of the files can be explained using the problem below. We have 10 meetings (n=10), 5 agents (m=5) and 18 time slots to schedule the meetings. We then have an m by n array X where X[i][j] = 1 iff agent_i attends meeting_j. There is then an n by n distance array where distance[i][j] is the time to travel from meeting_i to meeting_j. All meetings take one unit of time and the first time slot is 0 (zero).
10 5 18
0: 0 0 0 0 0 0 0 1 0 1 1: 0 1 1 0 1 1 1 1 0 1 2: 0 0 0 0 0 1 0 1 1 0 3: 0 1 0 0 1 0 0 1 0 0 4: 1 0 1 0 0 0 1 1 1 0
0: 0 1 2 1 1 2 1 2 2 2 1: 1 0 2 2 1 1 1 1 1 2 2: 2 2 0 2 1 2 1 1 1 2 3: 1 2 2 0 1 2 1 2 2 1 4: 1 1 1 1 0 2 1 2 1 2 5: 2 1 2 2 2 0 2 1 2 2 6: 1 1 1 1 1 2 0 1 2 1 7: 2 1 1 2 2 1 1 0 2 2 8: 2 1 1 2 1 2 2 2 0 2 9: 2 2 2 1 2 2 1 2 2 0
The problem is then to schedule the meetings in the given amount of time (0 to timeSlots-1). Below is a solution to the above problem (rProblems/10-5-30-2-00.txt) where meeting_0 starts at time 12, meeting_1 starts at time 15, ..., meeting_9 starts at time 12. This took 24 milliseconds to solve and 11 nodes.
java Solve rProblems/10-5-30-2-00.txt 0 12 1 15 2 0 3 0 4 9 5 6 6 2 7 4 8 9 9 12 24[+0] millis. 11[+0] nodes
We can validate that this is a solution using the program Validate that produces a small gantt chart and checks if the schedule is valid. NOTE: it does NOT check that the schedule is within the time window given.
java Validate rProblems/10-5-30-2-00.txt rProblems/solve-10-5-30-2-00.txt 0: ------------X (12) 1: ---------------X (15) 2: X (0) 3: X (0) 4: ---------X (9) 5: ------X (6) 6: --X (2) 7: ----X (4) 8: ---------X (9) 9: ------------X (12) true
Also note that the above schedule is NOT optimal! Below is an optimal schedule that uses only 13 time slots, and program Optimize took 202 millisecond to run and explored 227 nodes.
java Optimize rProblems/10-5-30-2-00.txt 0 12 1 6 2 0 3 0 4 8 5 4 6 10 7 2 8 7 9 12 202[+0] millis. 227[+0] nodes
-
Code up Solve.java and test it on the cspLib instances in problems/* and the new instances in rProblems/*. Use the Validate program to validate your results. NOTE: there are insolvable cspLib instances, and there are meetings that no one goes to!!!!
-
Code up Optimize.java and run this on the cspLib problems and the instances rProblems/*. NOTE: some of these are extremely hard. Therefore modify Optimize so that it takes an optional second parameter, a cpu time limit in milliseconds, such that you can report best-found-so-far within a given amount of time, i.e.
java Optimize rProblems/40-10-20-9-00.txt 10000
will terminate after 10 seconds cpu time and report the best result found so far, and
java Optimize rProblems/40-10-20-9-00.txt
will terminate (eventually, but maybe not in your lifetime) with the optimum solution.
-
Investigate alternative variable ordering heuristics for the optimization problem
-
Produce a report, no more than 3 pages that includes the following
- a description of your model for Solve and how you modified this for Optimize
- a description of the heuristics used and what they mean in the context of this problem
- computational results for Solve and Optimize over the problems/* and rProblems/* possibly taking into consideration different heuristics and various cpu time limits
- a discussion on an alternative model (that you should not implement, only discuss)
-
Email me Solve.java, Optimize.java and your report.
-
Your programs MUST be named as above and MUST run on the command line as above and MUST produce output in the format as above. This is essential otherwise your submission may be rejected and no marks will be awarded
Patrick Prosser