# Modeling advice: scheduling problem with judged events and "blocks" of judging assignments

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.

• 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$? Commented Nov 21, 2022 at 19:59
• @A.Omidi Thanks for responding. I'll make edits to clarify. Commented Nov 22, 2022 at 16:04
• 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. Commented Nov 22, 2022 at 17:29
• 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. Commented Nov 22, 2022 at 17:37
• 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. Commented Nov 22, 2022 at 17:47

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\}$$

• 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. Commented Nov 25, 2022 at 22:41