CODEWITHSUNDEEP
algorithmlanguage-agnostictheorygreedy
user3713712
user3713712

Reputation: 105

Trying to gain intuition for work scheduling greedy algorithm

I have the following scenario: (since I don't know of a way to show LaTeX, here's a screenshot)

enter image description here

I'm having some trouble conceptualizing what's going on here. If I were to program this, I would probably attempt to structure this as some kind of heap where each node represents a worker, from earliest-to-latest, then run Prim's/Kruskal's algorithm on it. I don't know if I'm on the right track with that idea, but I need to flesh out my understanding of this problem so I can do the following:

So where should I be going with this idea?

Upvotes: 3

Views: 484

Answers (1)

Ram Narasimhan
Ram Narasimhan

Reputation: 22496

This problem is very similar in nature to "Roster Scheduling problems." Think of the committee as say a set of 'supervisors' and you want to have a supervisor present, whenever a worker is present. In this case, the supervisor comes from the same set as the workers.

Here are some modeling ideas, and an Integer Programming formulation.

Time Slicing Idea

This sounds like a bad idea initially, but works really well in practice. We are going to create a lot of "time instants" T i from the start time of the first shift, to the end time of the very last shift. It sometimes helps to think of T1, T2, T3....TN as being time instants (say) five minutes apart. For every Ti at least one worker is working on a shift. Therefore, that time instant has be be covered (Coverage means there has to be at least one member of the committee also working at time Ti.)

We really need to only worry about 2n Time instants: The start and finish times of each of the n workers.

Coverage Property Requirement

For every time instant Ti, we want a worker from the Committee present.

Let w1, w2...wn be the workers, sorted by their start times s_i. (Worker w1 starts the earliest shift, and worker wn starts the very last shift.)

Introduce a new Indicator variable (boolean):

Y_i = 1 if worker i is part of the committeee
Y_i = 0 otherwise.

Visualization

Now think of a 0-1 matrix, where the rows are the SORTED workers, and the columns are the time instants...

Construct a Time-Worker Matrix (0/1)

    t1 t2 t3 t4 t5 t6 ...          tN
------------------------------------------- 
w1   1  1
w2   1  1
w3      1  1  1
w4         1  1  1  
...
...
wn                               1 1 1 1
------------------------------------------- 
Total 2 4 3 ...              ... 1 2 4 5

So the problem is to make sure that for each column, at least 1 worker is Selected to be part of the committee. The Total shows the number of candidates for the committee at each Time instant.

An Integer Programming based formulation

Objective: Minimize Sum(Y_i)

Subject to:

Y1 + Y2       >= 1 # coverage for time t1
Y1 + Y2 + Y3  >= 1 # coverage for time t2
...

More generally, the constraints are:

# Set Covering constraint for time T_i
Sum over all worker i's that are working at time t_i (Y_i) >= 1 

Y_i Binary for all i's

Preprocessing

This Integer program, if attempted without preprocessing can be very difficult, and end up choking the solvers. But in practice there are quite a number of preprocessing ideas that can help immensely.

  1. Make any forced assignments. (If ever there is a time instant with only one worker working, that worker has to be in the committee ∈ C)
  2. Separate into nice subproblems. Look at the time-worker Matrix. If there are nice 'rectangles' in it that can be cut out without impacting any other time instant, then that is a wholly separate sub-problem to solve. Makes the solver go much, much faster.
  3. Identical shifts - If lots of workers have the exact same start and end times, then you can simply choose ANY one of them (say, the lexicographically first worker, WLOG) and remove all the other workers from consideration. (Makes a ton of difference in real life situations.)
  4. Dominating shifts: If one worker starts before and stays later than any other worker, the 'dominating' worker can stay, all the 'dominated' workers can be removed from consideration for C.
  5. All the identical rows (and columns) in the time-worker Matrix can be fused. You need to only keep one of them. (De-duping)

You could throw this into an IP solver (CPLEX, Excel, lp_solve etc.) and you will get a solution, if the problem size is not an issue.

Hope some of these ideas help.

Upvotes: 3

Related Questions