Scheduling multiple concurrent tasks on a linear project to ensure no overlap

I have a problem where I have several events that are occurring in a project, the events happen semi-concurrently, where they do not start at the same time but multiple can still be occurring at once. Each event is a team of people working on a linear task, starting at the beginning and then working their way to the end. Their progress is based on a physical distance. I essentially need to figure out each events start time in order for no teams to be at the same location, nor passing eachother, at any point.

I am trying to program this in MATLAB so that the output would be the start and end time for each event. The idea would be to optimize the total time taken for the project.

I am not sure where to begin with something like this so any advice would be greatly appreciated.

[Walter Roberson]

Does each time proceed at the same rate as each other team? Or is the rate of progress specific to a team but differs between teams?

If there are multiple events and no team can "pass" another team, then that could lead to some odd allocation strategies. For example, if there were four potholes to fill, and the third was the largest, then... ummm, I'm not sure it is even always possible without having a team be idle.

For example, suppose the pot holes were size 1, 2, 7, 3, and you had two teams. Suppose you have Team 1 start on 7. If you have Team 2 start on 1 or 2, then they can also do the other of those without passing Team 1, but at the end of 3 units, Team 2 will have completed 1 and 2 and be looking for work. The pothole at size 3 is available, but you restricted that the teams are not allowed to pass each other, so Team 2 cannot pass Team 1 that is still working on 7 in order to do 3. So Team 2 has to sit idle after finishing 1 and 2 and Team 1 has to do 3 after doing 7, or else a different approach needs to be used. If you assign Team 1 to the 3 first instead of the 7, then Team 2 could start on either 1 or 2, but at the end of 3 units, they would have finished 1 and 2 and Team 1 would have finished 3, and you now have two teams available to work on 7, but only one piece of work to do.

Unless.. your definition of "pass" does not include in the reverse direction? If you start Team 1 doing 7, and Team 2 doing 3, and then it is not "passing" if Team 2 afterwards goes back towards the beginning to do the 1 and 2 ?

Or unless work can be split?? If Team 1 starts 4 units into the 7, then Team 1 can do 3 of 7 plus the following 3 (total 6 units), and Team 2 would do 1 + 2 + first 4 of of 7 (total 7 units); or equivalently, Team 1 could maybe start 3 units into the 7 and do the 4 + the following 3 (total 7 units) while Team 2 does 1 + 2 + the first 3 of 7 (total 6 units) ?

[Jadon Latta]

@Walter Roberson So, the issue with this task specifically, is it is regarding a pipeline, and the teams cannot jump around. They must all start at the beginning of the line, and move towards the end. Each team is doing an entirely seperate task, and proceeds at a different rate. They will end up starting on different days, and the goal would be to have the minimize the total time, from the start date of group 1 to the end date of group x, where x is however many groups I end up needing.

So the the term "passing" is just as much literal as figurative, team 2 physically cannot work on any point further than where team 1 has gotten to, hence they need to start at different times to ensure they never catch eachother.

[Jadon Latta]

As an example, if there are 3 teams, a, b and c, that all have different tasks. Team A places the pipeline down, Team B welds them together, and Team C cleans the pipeline. Each team has different speeds of work. A goes 100m/day, B goes 80m/day and C goes 90m/day, they have a total of 1470m to do. Assuming Team A starts on "Day 1", I would want to determine the start date of Team B and Team C respectively in order to minimize the total time taken for the entire distance. I can do this easily through basic math on a chart, but I'm not sure where to start doing it programatically, while having it be scaleable and variable

[Walter Roberson]

To confirm, they have different classes of task, and team 2 will need to do their task on the same sections that team 1 already worked on?

Are the teams each able to handle either task? Even if restricted so that any given day they can only handle one particular kind of task?

Does Team 1 need to process the entire continuous pipeline? Or do they work on a section, then move on to a further section? For example if Team 1 installed the pipeline itself, Team 2 installed the pump stations, Team 3 did the testing and burying, then Team 1 would have to cover the entire distance, but Team 2 would only have to go to the places where the pump stations are to be installed ?

Are there other considerations? For example, if Team 2 works twice as fast as Team 1, then you could schedule

Day 1: Team 1, unit 1, Team 2 not started yet
Day 2: Team 1, unit 2, Team 2 not started yet
Day 3: Team 1, unit 3, Team 2 unit 1 and 2
Day 4: Team 1, unit 4, Team 2 idle
Day 5: Team 1, unit 5, Team 2 unit 3 and 4

and so on, with Team 2 being idle every second day, and the overall project would finish 1 day after Team 1 finished its last unit.

But you could also schedule

Day 1 to 51, Team 1 working alone on unit 1 to 51, 
Day 52, Team 1 on unit 52, Team 2 on unit 1, 2
Day 53, Team 1 on unit 53, Team 2 on unit 3, 4
...
Day 97, Team 1 on unit 97, Team 2 on unit 91, 92
Day 98, Team 1 on unit 98, Team 2 on unit 93, 94
Day 99, Team 1 on unit 99, Team 2 on unit 95, 96
Day 100, Team 1 on unit 100, Team 2 on unit 97, 98
Day 101, Team 1 idle, Team 2 on unit 99, 100

Same total time, but probably less expensive since no team would be idle.

[Jadon Latta]

@Walter Roberson Yes, each team each has a different task, but each team can only complete the task they were assigned. Technically, it is correct that certain teams don't process the entire continuous pipeline, but in terms of how we have productivity represented it is simply a meter/day coverage regardless of whether they only hit a specific area every x amount metres, due to the fact we have travel time considered within our productivity rates.

We also would be doing something more similar to the second option, where we aim to have 0 idling time to reduce costs.

Answer 1

[Walter Roberson]

Let the rates of work be R1, R2, R3, and the total distance be D.

Team 1 should always start immediately and work continuously.

If team 2 is slower than team 1, then team 2 should start after a delay equal to the minimum separation between the two teams (and team 1 will then pull further and further ahead)

If team 2 is faster than team 1, then team 2 should start later, such that

delay2 + D/R2 == (D+minsep12)/R1

where minsep12 is the minimum physical separation distance between teams 1 and 2. You might need a ceil() or two to get the proper separation semantics.

... and knowing the rates and minimum separation, that allows you to calculate the delay.

Then team 3 just has the same logic, except with respect to team 2, so by knowing the rates and minimum separation, you can calculate the delay between them and team 2 fairly easily.

What becomes more difficult is the case where the production rates are not constant. For example it would be expected that the rate of laying down pipeline would be less where there was blasting to be done, compared to loam; the rate of laying down pipeline in wetlands would perhaps be faster than areas where you had to blast, but slower than loam.

Then there are contingencies, especially in the part about laying down the pipeline. For example, you might discover an Artesian well that leads to a section of ground being unacceptably subject to slip-faults, so you might have to re-route.

Or there might have been problems leading to a leak...

[Jadon Latta]

Thank you! That works great. We are defintely aware of all of the uncertainties and contigincies, but this program is supposed to be a proof-of-concept so as long as we can produce something, we can deal with those then. I appreciate the help!