Use case: formula one pitstop¶

This example is based on the DailyMail blog entry https://www.dailymail.co.uk/sport/formulaone/article-4401632/Formula-One-pit-stop-does-crew-work.html where a nice image shows 21 people changing the 4 tires of a Formula 1 Ferrari. In this example, only 16 out 21 people are represented. This notebook can be tested online at mybinder.org

[1]:

from IPython.display import YouTubeVideo

[1]:


Imports¶

[2]:

import processscheduler as ps
%config InlineBackend.figure_formats = ['svg']


Create the scheduling problem¶

The total horizon is not knwown, leave it empty and only set the problem name.

[3]:

change_tires_problem = ps.SchedulingProblem('ChangeTires')


Create the 16 available resources¶

Each people in and around the car is represented as a worker.

[4]:

nb_lifters = 2
nb_gunners = 4
nb_tyre_handlers = 8
nb_stabilizers = 2

[5]:

# Lift tasks
lifters = [ps.Worker('JackOperator%i' % (i + 1)) for i in range(nb_lifters)]
gunners = [ps.Worker('Gunner%i' % (i + 1)) for i in range(nb_gunners)]
tyre_handlers = [ps.Worker('Handler%i' % (i + 1)) for i in range(nb_tyre_handlers)]
stabilizers = [ps.Worker('Stabilizer%i' % (i + 1)) for i in range(nb_stabilizers)]


One period is mapped to one second. For example, if lifting the rear take 2sec then the duration will be set to 2.

[6]:

# lift tasks and lifters
# both lift tasks can be processed by any one of the lifters

gunner_unscrew_front_left_tyre = ps.SelectWorkers(gunners, 1)

gunner_unscrew_front_right_tyre = ps.SelectWorkers(gunners, 1)

gunner_unscrew_rear_left_tyre = ps.SelectWorkers(gunners, 1)

gunner_unscrew_rear_right_tyre = ps.SelectWorkers(gunners, 1)

gunner_screw_front_left_tyre = ps.SelectWorkers(gunners)

gunner_screw_front_right_tyre = ps.SelectWorkers(gunners)

gunner_screw_rear_left_tyre = ps.SelectWorkers(gunners)

gunner_screw_rear_right_tyre = ps.SelectWorkers(gunners)

[7]:

# tires OFF and handlers

rear_left_tyre_off, rear_right_tyre_off]:

# tires ON and handlers, same as above

rear_left_tyre_on, rear_right_tyre_on]:


Stabilizers start their job as soon as the car is stopped until the end of the whole activity.

[8]:

stabilize_left = ps.VariableDurationTask('StabilizeLeft')


[8]:

TaskEndAt_16a5d204(<class 'processscheduler.task_constraint.TaskEndAt'>)
1 assertion(s):
StabilizeRight_end == horizon


[9]:

# front left tyre operations
fr_left = [unscrew_front_left_tyre, front_left_tyre_off, front_left_tyre_on,
screw_front_left_tyre]
for i in range(len(fr_left) - 1):
# front right tyre operations
fr_right = [unscrew_front_right_tyre, front_right_tyre_off, front_right_tyre_on,
screw_front_right_tyre]
for i in range(len(fr_right) - 1):
# rear left tyre operations
re_left = [unscrew_rear_left_tyre, rear_left_tyre_off, rear_left_tyre_on,
screw_rear_left_tyre]
for i in range(len(re_left) - 1):
# front left tyre operations
re_right = [unscrew_rear_right_tyre, rear_right_tyre_off, rear_right_tyre_on,
screw_rear_right_tyre]
for i in range(len(re_right) - 1):

# all un screw operations must start after the car is lift by both front and rear jacks
unscrew_rear_left_tyre, unscrew_rear_right_tyre]:

# lift down operations must occur after each screw task is completed
screw_rear_left_tyre, screw_rear_right_tyre]:


First solution, plot the schedule¶

[10]:

solver = ps.SchedulingSolver(change_tires_problem)
solution_1 = solver.solve()
solution_1.render_gantt_matplotlib(fig_size=(10,5), render_mode='Resource')

Solver type:
===========
-> Standard SAT/SMT solver
Total computation time:
=====================
ChangeTires satisfiability checked in 0.05s


Second solution: add a makespan objective¶

Obviously, the former solution is not the best solution, not sure Ferrari will win this race ! The whole “change tires” activity must be as short as possible, so let’s add a makespan objective, i.e. a constraint that minimizes the schedule horizon.

[11]:

# add makespan objective

solver_2 = ps.SchedulingSolver(change_tires_problem)
solution_2 = solver_2.solve()

Solver type:
===========
-> Standard SAT/SMT solver
Incremental optimizer:
======================
Found value: 24 elapsed time:0.048s
Checking better value < 24
Found value: 23 elapsed time:0.163s
Checking better value < 23
Found value: 22 elapsed time:0.171s
Checking better value < 22
Found value: 21 elapsed time:0.197s
Checking better value < 21
Found value: 20 elapsed time:0.202s
Checking better value < 20
Found value: 19 elapsed time:0.208s
Checking better value < 19
Found value: 18 elapsed time:0.213s
Checking better value < 18
Found value: 17 elapsed time:0.233s
Checking better value < 17
Found value: 16 elapsed time:0.239s
Checking better value < 16
Found value: 15 elapsed time:0.255s
Checking better value < 15
Found value: 14 elapsed time:0.260s
Checking better value < 14
Found value: 13 elapsed time:0.281s
Checking better value < 13
Found value: 12 elapsed time:0.286s
Checking better value < 12
Can't find a better solution for problem ChangeTires.

Found optimum 12. Stopping iteration.
total number of iterations: 14
value: 12
ChangeTires satisfiability checked in 0.29s


Third solution: constraint workers¶

This is not the best possible solution. Indeed, we can notice that the Gunner2 unscrews the RearRightTyre and screw the RearLeft tyre. We cannot imagine that a solution where gunners turn around the car is acceptable. There are two solutions to fix the schedule: - let the gunner be able to turn around the car, and add a “Move” task with a duration that represent the time necessary to move from one tyre to the other, - constraint the worker to screw the same tyre he unscrewed. Let’s go this way

[12]:

ps.SameWorkers(gunner_unscrew_front_left_tyre, gunner_screw_front_left_tyre)
ps.SameWorkers(gunner_unscrew_front_right_tyre, gunner_screw_front_right_tyre)
ps.SameWorkers(gunner_unscrew_rear_left_tyre, gunner_screw_rear_left_tyre)
ps.SameWorkers(gunner_unscrew_rear_right_tyre, gunner_screw_rear_right_tyre)

solver_3 = ps.SchedulingSolver(change_tires_problem)
solution_3 = solver_3.solve()

Solver type:
===========
-> Standard SAT/SMT solver
Incremental optimizer:
======================
Found value: 28 elapsed time:0.082s
Checking better value < 28
Found value: 24 elapsed time:0.089s
Checking better value < 24
Found value: 23 elapsed time:0.162s
Checking better value < 23
Found value: 22 elapsed time:0.165s
Checking better value < 22
Found value: 21 elapsed time:0.169s
Checking better value < 21
Found value: 20 elapsed time:0.173s
Checking better value < 20
Found value: 19 elapsed time:0.177s
Checking better value < 19
Found value: 18 elapsed time:0.180s
Checking better value < 18
Found value: 17 elapsed time:0.184s
Checking better value < 17
Found value: 16 elapsed time:0.188s
Checking better value < 16
Found value: 15 elapsed time:0.192s
Checking better value < 15
Found value: 14 elapsed time:0.195s
Checking better value < 14
Found value: 13 elapsed time:0.199s
Checking better value < 13
Found value: 12 elapsed time:0.203s
Checking better value < 12
Can't find a better solution for problem ChangeTires.

Found optimum 12. Stopping iteration.
total number of iterations: 15
value: 12
ChangeTires satisfiability checked in 0.20s


This is much better !