2
$\begingroup$

I am considering a scheduling problem in which the events are officiated, likely as a MILP problem. I'm getting hung up on how best to model a particular requirement of how the judged events are scheduled. Any advice would be most welcome.

Here is a small description with the salient details:

$E = \{1, 2, ..., n_e\}$ : set of events to be judged

$D_e$ : anticipated duration of event $e$ in minutes, $\forall e \in E$

$J = \{1, 2, ..., n_j\}$ : set of judges

A judge from $J$ is pre-assigned to officiate one or more events from $E$.

$V = \{1, 2, ..., n_v\}$ : set of venues for the events

The day's activity in each venue commences at the same start time.

A judge's assignments are to be partitioned into "blocks" of events of no more than 60 minutes. If an event $e$'s duration $D_e >= 60$ minutes, then it is to be in a block on its own.

Then, these blocks are to be scheduled in venues from $V$, to start on a 5-minute marker (e.g. 8:00, 8:05, 8:10, ...). For example, suppose from the table below that we choose a block [1, 2, 3] for a judge, and choose to schedule it at 8:00 a.m. in venue 6. Then event 1 will begin at 8:00 a.m., event 2 at roughly 8:20 a.m., and event 3 at 8:34 a.m.; and the next block of events at venue 6 could begin no sooner than 8:45 a.m. (the nearest 5-minute marker past 8:42 a.m., the putative end time of the [1, 2, 3] block).

There are constraints and penalties for certain characteristics of these block schedulings:

  • use all venues
  • prevent overlap of blocks in same venue
  • prevent overlap of a judge's blocks scheduled in different venues
  • afford some time gap between blocks in same venue
  • afford some time for each judge to have lunch
  • encourage finishing all events as soon as possible
  • encourage solutions that minimize:
    • the number of times a judge must switch venues
    • the number of equipment changes needed between events
    • overlaps between multiple events in which a participant is entered

For a given judge, there are potentially lots of possibilities for blocks of their judging assignments. I'm getting hung up on how best to represent these possibilities and the choices thereof.

Suppose a judge is pre-assigned to officiate these events:

event number (e) D_e
1 20
2 14
3 8
4 30
5 36
6 18

Then $\{[1, 2], [3, 4], [5, 6]\}$ is a legitimate judging assignment (I'm using square brackets here to represent sequences: event 1 is followed immediately by event 2). So is $\{[2, 1], [4, 3], [6, 5]\}$...or any other set of permutations of $\{1, 2\}$, $\{3, 4\}$, and $\{5, 6\}$. It's as though we can find any partition of $\{1, 2, 3, 4, 5, 6\}$ in which each of the subsets obeys the 60-minute duration limit ... and then any of those subsets can be permuted to give a different sequencing for the block it represents.

One possibility might be to pre-enumerate such block partitions/permutations for each judge, then have decision variables $PP_{ij} \in \{0, 1\}$ where 1 = that partition/permutation possibility is used, so that $\sum_{i \in B} PP_{ij} = 1, \forall j \in J$. Then choose start times for each block in the partition/permutation possibilities chosen. This yields possibly way too many variables.

Another possibility I've considered: Suppose a judge $j$'s assignment is $\{e_1, e_2, ..., e_{m_j}\}$. Then let each judge $j$ have a maximum of $m_j$ blocks available. Then let $b_{ijk} = 1$ if event $i$ occupies position $j$ in block $k$, else 0. Constrain $b_{ijk}$ appropriately so that every event occupies exactly one position in exactly one block; and for every block $b$, if it's unused, then so is block $b + 1$; and that the sum of the durations of the events in each block is acceptable.

$\endgroup$
6
  • 1
    $\begingroup$ Welcome to OR.SE. Would you please, give more details about the problem description? What does set $J$ mean? what you mean by these blocks are to be scheduled in a venue, to start on a 5-minute marker (e.g. 8:00, 8:05, 8:10, ...). If the duration is pre-determined, what is $D_e \leq 60$? $\endgroup$
    – A.Omidi
    Commented Nov 21, 2022 at 19:59
  • $\begingroup$ @A.Omidi Thanks for responding. I'll make edits to clarify. $\endgroup$
    – pholser
    Commented Nov 22, 2022 at 16:04
  • $\begingroup$ In the industry hundreds of thousands of variables/constraints exist but mostly will be within a limited number of possibilities. In your case something needs to be parameterized like schedule of blocks; block 1 begin at 8 at venues in V, block 2 at 8:20 and so on. Also it may be simpler to schedule events or assign to blocks as a new model. Then add assignment of judges as an update or new model. $\endgroup$ Commented Nov 22, 2022 at 17:29
  • $\begingroup$ It's like in ML, any variable with high cardinality or high variance is too random to be a good predictor and so is often factored out. $\endgroup$ Commented Nov 22, 2022 at 17:37
  • 1
    $\begingroup$ Thanks that clarifies it a bit, judge-event assignment is fixed. I will try to put something in the answer today/tomorrow/Thanksgiving holidays but no promises. $\endgroup$ Commented Nov 22, 2022 at 17:47

1 Answer 1

3
$\begingroup$

Pre-define nB number of blocks where $n \le \lvert E \rvert$ where E is set of events, e. Blocks could be set as time slots alternatively.
$B =\{b_1,b_2,..b_n \}$ Combinations already available: judge pre-assigned to events. $JE =\{je_{1,1},je_{2,1},..je_{j,e} \}$ Venue, $V = \{v_1,v_2,..v_n \}$ Define more combinations of events, E with Venue, V. Instead of adding constraints latter better to define combinations of possible events with venues along with blocks.
$EBV =\{ebv_{1,1,1},ebv_{2,1,1},..ebv_{e,b,v} \}$
Also assuming every venue will have total time, $T_v$ available
Define DVs:
$x_{e,b,v}, \ y_{j,v} \ and \ z_{j,b} $ as binary.
$bigM = \lvert E \rvert*\lvert V \rvert*\lvert B \rvert$

Constraints:
$\sum_{b}\sum_{v} x_{e,b,v} = 1\quad \forall\ e \in E$: $\quad$Event can be assigned to one block in one venue.

$\sum_{e} x_{e,b,v}*D_e \le 60\quad \forall\ b \in B \quad \forall\ v \in V$: $\quad$ Total duration of blocks.

$\sum_{b}(\sum_{e} x_{e,b,v}*D_e + \sum_{e} x_{e,b,v}*D_e\pmod 5) = T_v \quad \forall\ v \in V$: This ensures blocks are sequenced in a way that takes care of 5 minute marker.

$bigM*y_{j,v} \ge \sum_{e \in\ JE}\sum_{b \in B} X_{e,b,v} \quad \forall\ v \in V \quad\ \forall\ j \in J$: Counts number of venues a judge is assigned

$bigM*z_{j,b} \ge \sum_{e \in\ EJ}\sum_{v \in JV} X_{e,b,v} \quad \forall b \in B \quad \forall J \in J$: Counts number of blocks a judge is assigned

$\sum_e x_{e,b+1,v} \le bigM*\sum_{e} x_{e,b,v} \ \forall b \in B \quad \forall v \in V$: Condition for b+1 to be empty if b is empty at a venue, v

totalDuration = $\sum_{e,b,v \in EBV} x_{e,b,v}$
venueChange = $\sum_{j}\sum_{v} y_{j,v}$
NblockJudge = $\sum_{j}\sum_{b} z_{j,b}$
$Minimize \ \{venueChange+ NblockJudge + totalDuration\}$

$\endgroup$
1
  • $\begingroup$ Thanks, this is helpful. It lends some legitimacy to my thoughts about modeling blocks of events. I appreciate you taking the time to post a possible solution. $\endgroup$
    – pholser
    Commented Nov 25, 2022 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.