I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed and I need help defining some of the variables. 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). 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 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 so far are as follows:
$\sum_{w \in W} X_{p,w} = 1$
$D_w , S_{p,w} \ge 0$
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. In order to achieve this, I first need to just figure out how to come up with the decision variables which I am struggling because I don't know how to factor in 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 question on OR.SE link: https://or.stackexchange.com/questions/2734/how-to-formulate-scheduling-matrix-problem-with-mixed-integer-linear-programming