1. CSPLib
  2. Problems
  3. prob013

013: Progressive Party Problem

Proposed by Toby Walsh

The problem is to timetable a party at a yacht club. Certain boats are to be designated hosts, and the crews of the remaining boats in turn visit the host boats for several successive half-hour periods. The crew of a host boat remains on board to act as hosts while the crew of a guest boat together visits several hosts. Every boat can only hold a limited number of people at a time (its capacity) and crew sizes are different. The total number of people aboard a boat, including the host crew and guest crews, must not exceed the capacity. A table with boat capacities and crew sizes can be found below; there were six time periods. A guest boat cannot not revisit a host and guest crews cannot meet more than once. The problem facing the rally organizer is that of minimizing the number of host boats.

boat number capacity crew size
1 6 2
2 8 2
3 12 2
4 12 2
5 12 4
6 12 4
7 12 4
8 10 1
9 10 2
10 10 2
11 10 2
12 10 3
13 8 4
14 8 2
15 8 3
16 12 6
17 8 2
18 8 2
19 8 4
20 8 2
21 8 4
22 8 5
23 7 4
24 7 4
25 7 2
26 7 2
27 7 4
28 7 5
29 6 2
30 6 4
31 6 2
32 6 2
33 6 2
34 6 2
35 6 2
36 6 2
37 6 4
38 6 5
39 9 7
40 0 2
41 0 3
42 0 4