9
$\begingroup$

I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed. To keep the information confidential, I will refer to my tasks as papers that need to be written. Here is the premise of my problem.

  • There are 320 papers to be written. (All writers can write these papers and can all work at the same time). Each paper takes a different amount of time to complete.

  • We have 2 types of workers available to complete this set of papers.

  • We have 150 writers, whose responsibility it is to actually write the paper.

  • We have 25 movers, whose responsibility it is to take the completed papers and go and grab a new paper for the writers to work on. For the sake of simplicity, I am assuming that the time to take a completed paper and deliver a new one is constant for each move.

The goal of this problem will be to minimize the total length of time it takes to write all of these papers with my staff. We are restricted by the following:

  • How many writers we have to write papers at the same time
  • How many movers are available to move papers at the same time
  • Each mover takes 25 minutes to move a paper for the writer
  • Movers cannot move papers for writers that are within 2 writers of each other at the same time (If writer 3 has completed his paper and a mover begins moving a paper for them, then writers 1,2,4, and 5 will have to wait until the mover for writer 3 has finished their move). This constraint is meant to represent a physical limitation we have at our facility.

My Approach:

It has been some time since I've properly done LP so I am rusty(I'm also still a student so my skills were never good to begin with). I have defined the following variables but am not sure if these are good or not. I don't know whether to consider time $t$ as a parameter for these variables or as its own variable and this is what I'm mainly struggling with.

$D_p$: The length of time for paper $p$ to be completed.

$S_{p,w}$: The point in time when writer $w$ begins writing paper $p$.

$X_{p,w}$: Binary variable representing whether or not a paper $p$ is being written by writer $w$.

$M_{m,w}$: Whether or not mover $m$ moves a paper for writer $w$

Constraints that I have come up with are as follows:

  • $\sum_{w \in W} X_{p,w} = 1$

  • $S_{p,w} \ge 0$

I am struggling with how to wrap my head around how to factor in a timeline as either a variable or some set or whatever.

Edit: I've spent some more time and discovered that this is a common difficulty with this type of problem(yay!). The two routes to be taken are to consider time as either a discrete or a continuous variable. Though the precision would be nice, the data I have at the facility is available per minute so I think treating time as a discrete variable with one-minute intervals is reasonable.

I would like to be able to get an output that gives me an optimal schedule for the papers to be written and for the output to tell me which papers are being completed by which writers at what time. I will be as active as I can in the comments if there needs any clarification.

Note: I have also posted this question on SO link: https://stackoverflow.com/questions/58223716/how-to-formulate-scheduling-matrix-problem-with-mixed-integer-linear-programming

I have also posted this on Math.SE link: https://math.stackexchange.com/questions/3384542/should-i-factor-in-time-as-a-parameter-or-a-variable-in-a-scheduling-problem-wit

|improve this question
$\endgroup$
  • $\begingroup$ Isn't $D_j$ a parameter rather than a variable? $\endgroup$ – prubin Oct 4 '19 at 20:50
  • $\begingroup$ Regarding the congestion constraint, if your time unit is one minute, can you assume that one minute after a mover moves a paper from writer 3, another mover can snatch a paper from writer 4? As a side note, you might want to edit the question to assign a symbol to the time to move a paper. You said that was constant. After that amount of time, is the mover available to instantly help any author, or do you need to account for transit time to reach an author? (It would take me more than a minute to get from author 1 to author 150, I suspect.) $\endgroup$ – prubin Oct 4 '19 at 20:55
  • $\begingroup$ Regarding the Dj, these are actually set values. Each paper has a given amount of time to complete based on the input data so I think that means it's variable? I could definitely be wrong. $\endgroup$ – Dom Oct 6 '19 at 5:17
  • $\begingroup$ Regarding the movers, because our facility does not at the moment accurately track how long it takes for these moves to happen I am using a 25 minute estimate for these moves. I failed to clarify this in the original post so that has been updated. This 25 minute estimate includes the transit time it takes for a mover to take a paper, drop it off where it needed next at our facility, grab a new paper, and then drop it off at the writer for the writer to work on. Hopefully that makes sense. $\endgroup$ – Dom Oct 6 '19 at 5:24
4
$\begingroup$

My advice is to use discrete variables for time. Modelling time as a continuous variable in scheduling problems tends to make the problem unsolvable, even though the continuous formulation results in a smaller problem. I don't know if anyone knows why that is the case, but everyone I've discussed this with over the last 5 years has found that to be true in practice.

The way this is typically modelled is that we create a matrix of binary variables, each representing a time chunk: $t_{ij}$ would be a discrete chunk of time spent by person $i$ writing paper $j$ and $t_{jk}$ would be the a chunk of time spent by mover $k$ moving paper $j$. If the value is of a chunk is 1, then that person performs that activity for that amount of time, otherwise they don't.

You can then use those time building blocks to build your problem logic. For instance, if each time chunk represents an hour, you may want the sum of all chunks per paper to not exceed some time limit, and so on.

|improve this answer
$\endgroup$
  • $\begingroup$ So these times are already given in the data input(Moves are 25 minutes long and there is a time to complete defined for all papers $p$). Are these variables you are referring to meant to act as an indicator variable? And then wouldn't the sum of these time chunks instead give me the total displaced time by all of the workers as opposed to an optimal schedule? Since these writers are all working at the same time, at least to how I understand this, this matrix doesn't account for writers writing at the same time. $\endgroup$ – Dom Oct 8 '19 at 14:10
  • $\begingroup$ Yes they are indicator variables that match points in time to tasks and people. So for each pair of worker and task you would have e.g. 100 time variables modelling 100 time chunks one after the other (from t=0 to t=step*100). The solution tells you what each person is doing at any point in your total time window. $\endgroup$ – nikaza Oct 8 '19 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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