Schedule Optimization Question - Variant of Job Shop
I am looking to build code on python for a variant of the job shop problem.
The differences are:
The goal is to combine as many tasks to the fewest number of machines without overlap while ensure the most efficient outcome
The machines have a capacity to run all day and will be measured in minutes 0-1440 minutes
there are multiple jobs, there is no order to the jobs, but each job has its own defined schedule
e.g. job 1: starts at 02:00 (140 minutes) and ends at 08:00 (480 minutes)
e.g. job 2: starts at 07:00 (420 minutes) and ends at 19:00 (1140 minutes)
e.g. job 3: starts at 08:00 (480 minutes) and ends at 20:00 (1200 minutes)
e.g. job 4: starts at 02:00 (140 minutes) and ends at 05:00 (300 minutes)
Can you help with the ideation / or code variation of the job shop problem to combine the jobs on the fewest number of machines?
Additionally as an extra request if possible (not too complex) would it be possible to incorporate jobs with different schedules during the week?
e.g.
Job 1: runs daily 02:00 - 08:00
job 2: runs Monday and Thursday only 07:00 - 19:00 etc.
In essence - assume I have a weekly Gannt chart / schedule with 50 machines - each with a single job, i want to compress the Gantt chart to reduce number of machines if they have space to run more than one job (simple illustration going from A to the more efficient B)
Have tried the job shop problem, and researching other problems but couldn't find a similar problem statement
Solution
This is not a super difficult problem to solve.
Instead of talking about jobs (which may repeat during the week), it may be easier to talk about individual sub-jobs. The first thing to do is to find out if two sub-jobs k and k' overlap. If this is the case, they cannot run on the same machine. The data structure to hold the overlap information can be calculated in advance (before the model runs).
The best thing is to first write down on a piece of paper the mathematical model of the problem. I propose something like:
The objective is to minimize the number of machines we use (i.e. to which we assign sub-jobs to). The first constraint says: assign each sub-job to exactly one machine. The second constraint: if sub-jobs k and k' overlap, they can't run on the same machine. The third constraint: if a machine is not used, we can't assign any sub-jobs to it. The whole model is expressed in terms of individual sub-jobs instead of (job,day) combinations.
This model can be implemented using any reasonable MIP solver. It is not very difficult to implement (it is rather simple: most of the work is to get the data in shape and calculate the overlap data) and not very difficult to solve (at least for the data set I used). The mathematical model above is sufficiently detailed and precise that you are advised to follow it as closely as possible.
I tried it out with the following random data:
---- 24 PARAMETER start start time
job1 206.000, job2 1012.000, job3 661.000, job4 361.000, job5 350.000, job6 269.000, job7 420.000
job8 1028.000, job9 80.000, job10 600.000, job11 1198.000, job12 695.000, job13 1190.000, job14 915.000
job15 156.000, job16 768.000, job17 191.000, job18 300.000, job19 803.000, job20 522.000, job21 432.000
job22 422.000, job23 157.000, job24 180.000, job25 707.000, job26 997.000, job27 277.000, job28 799.000
job29 931.000, job30 364.000, job31 132.000, job32 603.000, job33 192.000, job34 1047.000, job35 318.000
job36 343.000, job37 713.000, job38 867.000, job39 754.000, job40 557.000, job41 496.000, job42 141.000
job43 377.000, job44 55.000, job45 406.000, job46 218.000, job47 775.000, job48 673.000, job49 924.000
job50 357.000
---- 24 PARAMETER end finish time
job1 841.663, job2 1721.541, job3 1270.409, job4 702.414, job5 537.411, job6 468.961, job7 1040.176
job8 1573.341, job9 224.589, job10 1338.041, job11 1374.758, job12 952.016, job13 1719.993, job14 1620.162
job15 414.936, job16 914.630, job17 767.402, job18 904.559, job19 1226.702, job20 921.797, job21 741.567
job22 734.209, job23 378.792, job24 1028.091, job25 1123.352, job26 1728.052, job27 631.027, job28 1016.877
job29 1635.122, job30 538.001, job31 409.572, job32 726.951, job33 522.298, job34 1556.884, job35 556.003
job36 598.852, job37 1090.897, job38 1234.187, job39 1125.228, job40 1428.902, job41 1391.010, job42 549.524
job43 787.853, job44 777.143, job45 835.414, job46 1050.215, job47 988.271, job48 1366.674, job49 1087.226
job50 926.514
---- 24 PARAMETER length length of job (minutes)
job1 635.663, job2 709.541, job3 609.409, job4 341.414, job5 187.411, job6 199.961, job7 620.176
job8 545.341, job9 144.589, job10 738.041, job11 176.758, job12 257.016, job13 529.993, job14 705.162
job15 258.936, job16 146.630, job17 576.402, job18 604.559, job19 423.702, job20 399.797, job21 309.567
job22 312.209, job23 221.792, job24 848.091, job25 416.352, job26 731.052, job27 354.027, job28 217.877
job29 704.122, job30 174.001, job31 277.572, job32 123.951, job33 330.298, job34 509.884, job35 238.003
job36 255.852, job37 377.897, job38 367.187, job39 371.228, job40 871.902, job41 895.010, job42 408.524
job43 410.853, job44 722.143, job45 429.414, job46 832.215, job47 213.271, job48 693.674, job49 163.226
job50 569.514
---- 24 SET jd jobs need to run on certain days
day1 day2 day3 day4 day5 day6 day7
job1 YES YES YES
job2 YES YES
job3 YES YES YES
job4 YES YES YES
job6 YES YES YES
job7 YES YES YES
job8 YES YES YES
job9 YES
job10 YES YES YES YES YES
job11 YES
job12 YES YES YES YES YES YES
job13 YES YES
job14 YES
job15 YES
job16 YES YES
job17 YES
job18 YES
job19 YES YES
job21 YES YES YES
job22 YES YES
job23 YES YES
job24 YES YES
job25 YES
job26 YES YES
job27 YES YES
job28 YES YES
job30 YES YES
job31 YES
job32 YES YES
job33 YES YES YES
job34 YES YES YES
job35 YES YES
job36 YES YES
job37 YES YES
job38 YES YES YES
job39 YES YES
job40 YES YES
job42 YES YES YES
job44 YES
job45 YES
job46 YES
job48 YES YES
job49 YES YES
---- 29 PARAMETER counts
jobs 43.000, subjobs 93.000
---- 49 SET k subjobs
subjob1 , subjob2 , subjob3 , subjob4 , subjob5 , subjob6 , subjob7 , subjob8 , subjob9 , subjob10
subjob11, subjob12, subjob13, subjob14, subjob15, subjob16, subjob17, subjob18, subjob19, subjob20
subjob21, subjob22, subjob23, subjob24, subjob25, subjob26, subjob27, subjob28, subjob29, subjob30
subjob31, subjob32, subjob33, subjob34, subjob35, subjob36, subjob37, subjob38, subjob39, subjob40
subjob41, subjob42, subjob43, subjob44, subjob45, subjob46, subjob47, subjob48, subjob49, subjob50
subjob51, subjob52, subjob53, subjob54, subjob55, subjob56, subjob57, subjob58, subjob59, subjob60
subjob61, subjob62, subjob63, subjob64, subjob65, subjob66, subjob67, subjob68, subjob69, subjob70
subjob71, subjob72, subjob73, subjob74, subjob75, subjob76, subjob77, subjob78, subjob79, subjob80
subjob81, subjob82, subjob83, subjob84, subjob85, subjob86, subjob87, subjob88, subjob89, subjob90
subjob91, subjob92, subjob93
---- 49 SET map mapping between jobs/days and subjobs
job1 .day1.subjob1 , job1 .day2.subjob2 , job1 .day6.subjob3 , job2 .day2.subjob4 , job2 .day5.subjob5
job3 .day3.subjob6 , job3 .day5.subjob7 , job3 .day7.subjob8 , job4 .day3.subjob9 , job4 .day4.subjob10
job4 .day7.subjob11, job6 .day2.subjob12, job6 .day5.subjob13, job6 .day7.subjob14, job7 .day4.subjob15
job7 .day6.subjob16, job7 .day7.subjob17, job8 .day3.subjob18, job8 .day4.subjob19, job8 .day6.subjob20
job9 .day2.subjob21, job10.day1.subjob22, job10.day2.subjob23, job10.day3.subjob24, job10.day5.subjob25
job10.day7.subjob26, job11.day5.subjob27, job12.day2.subjob28, job12.day3.subjob29, job12.day4.subjob30
job12.day5.subjob31, job12.day6.subjob32, job12.day7.subjob33, job13.day3.subjob34, job13.day4.subjob35
job14.day3.subjob36, job15.day5.subjob37, job16.day4.subjob38, job16.day7.subjob39, job17.day5.subjob40
job18.day2.subjob41, job19.day1.subjob42, job19.day7.subjob43, job21.day3.subjob44, job21.day5.subjob45
job21.day7.subjob46, job22.day1.subjob47, job22.day6.subjob48, job23.day4.subjob49, job23.day6.subjob50
job24.day3.subjob51, job24.day6.subjob52, job25.day3.subjob53, job26.day3.subjob54, job26.day5.subjob55
job27.day1.subjob56, job27.day5.subjob57, job28.day1.subjob58, job28.day5.subjob59, job30.day1.subjob60
job30.day5.subjob61, job31.day3.subjob62, job32.day2.subjob63, job32.day5.subjob64, job33.day1.subjob65
job33.day6.subjob66, job33.day7.subjob67, job34.day1.subjob68, job34.day6.subjob69, job34.day7.subjob70
job35.day2.subjob71, job35.day6.subjob72, job36.day2.subjob73, job36.day7.subjob74, job37.day1.subjob75
job37.day5.subjob76, job38.day1.subjob77, job38.day3.subjob78, job38.day5.subjob79, job39.day4.subjob80
job39.day5.subjob81, job40.day2.subjob82, job40.day7.subjob83, job42.day1.subjob84, job42.day4.subjob85
job42.day6.subjob86, job44.day1.subjob87, job45.day5.subjob88, job46.day2.subjob89, job48.day4.subjob90
job48.day5.subjob91, job49.day5.subjob92, job49.day7.subjob93
---- 64 PARAMETER start2 start time of subjob
subjob1 206.000, subjob2 1646.000, subjob3 7406.000, subjob4 2452.000, subjob5 6772.000, subjob6 3541.000
subjob7 6421.000, subjob8 9301.000, subjob9 3241.000, subjob10 4681.000, subjob11 9001.000, subjob12 1709.000
subjob13 6029.000, subjob14 8909.000, subjob15 4740.000, subjob16 7620.000, subjob17 9060.000, subjob18 3908.000
subjob19 5348.000, subjob20 8228.000, subjob21 1520.000, subjob22 600.000, subjob23 2040.000, subjob24 3480.000
subjob25 6360.000, subjob26 9240.000, subjob27 6958.000, subjob28 2135.000, subjob29 3575.000, subjob30 5015.000
subjob31 6455.000, subjob32 7895.000, subjob33 9335.000, subjob34 4070.000, subjob35 5510.000, subjob36 3795.000
subjob37 5916.000, subjob38 5088.000, subjob39 9408.000, subjob40 5951.000, subjob41 1740.000, subjob42 803.000
subjob43 9443.000, subjob44 3312.000, subjob45 6192.000, subjob46 9072.000, subjob47 422.000, subjob48 7622.000
subjob49 4477.000, subjob50 7357.000, subjob51 3060.000, subjob52 7380.000, subjob53 3587.000, subjob54 3877.000
subjob55 6757.000, subjob56 277.000, subjob57 6037.000, subjob58 799.000, subjob59 6559.000, subjob60 364.000
subjob61 6124.000, subjob62 3012.000, subjob63 2043.000, subjob64 6363.000, subjob65 192.000, subjob66 7392.000
subjob67 8832.000, subjob68 1047.000, subjob69 8247.000, subjob70 9687.000, subjob71 1758.000, subjob72 7518.000
subjob73 1783.000, subjob74 8983.000, subjob75 713.000, subjob76 6473.000, subjob77 867.000, subjob78 3747.000
subjob79 6627.000, subjob80 5074.000, subjob81 6514.000, subjob82 1997.000, subjob83 9197.000, subjob84 141.000
subjob85 4461.000, subjob86 7341.000, subjob87 55.000, subjob88 6166.000, subjob89 1658.000, subjob90 4993.000
subjob91 6433.000, subjob92 6684.000, subjob93 9564.000
---- 64 PARAMETER end2 end time of subjob
subjob1 841.663, subjob2 2281.663, subjob3 8041.663, subjob4 3161.541, subjob5 7481.541
subjob6 4150.409, subjob7 7030.409, subjob8 9910.409, subjob9 3582.414, subjob10 5022.414
subjob11 9342.414, subjob12 1908.961, subjob13 6228.961, subjob14 9108.961, subjob15 5360.176
subjob16 8240.176, subjob17 9680.176, subjob18 4453.341, subjob19 5893.341, subjob20 8773.341
subjob21 1664.589, subjob22 1338.041, subjob23 2778.041, subjob24 4218.041, subjob25 7098.041
subjob26 9978.041, subjob27 7134.758, subjob28 2392.016, subjob29 3832.016, subjob30 5272.016
subjob31 6712.016, subjob32 8152.016, subjob33 9592.016, subjob34 4599.993, subjob35 6039.993
subjob36 4500.162, subjob37 6174.936, subjob38 5234.630, subjob39 9554.630, subjob40 6527.402
subjob41 2344.559, subjob42 1226.702, subjob43 9866.702, subjob44 3621.567, subjob45 6501.567
subjob46 9381.567, subjob47 734.209, subjob48 7934.209, subjob49 4698.792, subjob50 7578.792
subjob51 3908.091, subjob52 8228.091, subjob53 4003.352, subjob54 4608.052, subjob55 7488.052
subjob56 631.027, subjob57 6391.027, subjob58 1016.877, subjob59 6776.877, subjob60 538.001
subjob61 6298.001, subjob62 3289.572, subjob63 2166.951, subjob64 6486.951, subjob65 522.298
subjob66 7722.298, subjob67 9162.298, subjob68 1556.884, subjob69 8756.884, subjob70 10196.884
subjob71 1996.003, subjob72 7756.003, subjob73 2038.852, subjob74 9238.852, subjob75 1090.897
subjob76 6850.897, subjob77 1234.187, subjob78 4114.187, subjob79 6994.187, subjob80 5445.228
subjob81 6885.228, subjob82 2868.902, subjob83 10068.902, subjob84 549.524, subjob85 4869.524
subjob86 7749.524, subjob87 777.143, subjob88 6595.414, subjob89 2490.215, subjob90 5686.674
subjob91 7126.674, subjob92 6847.226, subjob93 9727.226
Some jobs, due to my random data, don't appear in any of the days. So we don't have 50 jobs here, but just 43. The number of subjobs is 93.
This model solves very fast: 0.06 seconds. Here is the solution:
---- 106 VARIABLE x.L assign job to machine
machine1 machine2 machine3 machine4 machine5 machine6 machine7 machine8 machine9 machine10
subjob1 1.000
subjob2 1.000
subjob3 1.000
subjob4 1.000
subjob5 1.000
subjob6 1.000
subjob7 1.000
subjob8 1.000
subjob9 1.000
subjob10 1.000
subjob11 1.000
subjob12 1.000
subjob13 1.000
subjob14 1.000
subjob15 1.000
subjob16 1.000
subjob17 1.000
subjob18 1.000
subjob19 1.000
subjob20 1.000
subjob21 1.000
subjob22 1.000
subjob23 1.000
subjob24 1.000
subjob25 1.000
subjob26 1.000
subjob27 1.000
subjob28 1.000
subjob29 1.000
subjob30 1.000
subjob31 1.000
subjob32 1.000
subjob33 1.000
subjob34 1.000
subjob35 1.000
subjob36 1.000
subjob37 1.000
subjob38 1.000
subjob39 1.000
subjob40 1.000
subjob41 1.000
subjob42 1.000
subjob43 1.000
subjob44 1.000
subjob45 1.000
subjob46 1.000
subjob47 1.000
subjob48 1.000
subjob49 1.000
subjob50 1.000
subjob51 1.000
subjob52 1.000
subjob53 1.000
subjob54 1.000
subjob55 1.000
subjob56 1.000
subjob57 1.000
subjob58 1.000
subjob59 1.000
subjob60 1.000
subjob61 1.000
subjob62 1.000
subjob63 1.000
subjob64 1.000
subjob65 1.000
subjob66 1.000
subjob67 1.000
subjob68 1.000
subjob69 1.000
subjob70 1.000
subjob71 1.000
subjob72 1.000
subjob73 1.000
subjob74 1.000
subjob75 1.000
subjob76 1.000
subjob77 1.000
subjob78 1.000
subjob79 1.000
subjob80 1.000
subjob81 1.000
subjob82 1.000
subjob83 1.000
subjob84 1.000
subjob85 1.000
subjob86 1.000
subjob87 1.000
subjob88 1.000
subjob89 1.000
subjob90 1.000
subjob91 1.000
subjob92 1.000
subjob93 1.000
---- 106 VARIABLE used.L
machine1 1.000, machine2 1.000, machine3 1.000, machine4 1.000, machine5 1.000, machine6 1.000
machine7 1.000, machine8 1.000, machine9 1.000, machine10 1.000
---- 106 VARIABLE num.L = 10.000 number of machines needed
---- 110 PARAMETER assignments
machine1 machine2 machine3 machine4 machine5 machine6 machine7 machine8 machine9 machine10
job1 .day1 1.000
job1 .day2 1.000
job1 .day6 1.000
job2 .day2 1.000
job2 .day5 1.000
job3 .day3 1.000
job3 .day5 1.000
job3 .day7 1.000
job4 .day3 1.000
job4 .day4 1.000
job4 .day7 1.000
job6 .day2 1.000
job6 .day5 1.000
job6 .day7 1.000
job7 .day4 1.000
job7 .day6 1.000
job7 .day7 1.000
job8 .day3 1.000
job8 .day4 1.000
job8 .day6 1.000
job9 .day2 1.000
job10.day1 1.000
job10.day2 1.000
job10.day3 1.000
job10.day5 1.000
job10.day7 1.000
job11.day5 1.000
job12.day2 1.000
job12.day3 1.000
job12.day4 1.000
job12.day5 1.000
job12.day6 1.000
job12.day7 1.000
job13.day3 1.000
job13.day4 1.000
job14.day3 1.000
job15.day5 1.000
job16.day4 1.000
job16.day7 1.000
job17.day5 1.000
job18.day2 1.000
job19.day1 1.000
job19.day7 1.000
job21.day3 1.000
job21.day5 1.000
job21.day7 1.000
job22.day1 1.000
job22.day6 1.000
job23.day4 1.000
job23.day6 1.000
job24.day3 1.000
job24.day6 1.000
job25.day3 1.000
job26.day3 1.000
job26.day5 1.000
job27.day1 1.000
job27.day5 1.000
job28.day1 1.000
job28.day5 1.000
job30.day1 1.000
job30.day5 1.000
job31.day3 1.000
job32.day2 1.000
job32.day5 1.000
job33.day1 1.000
job33.day6 1.000
job33.day7 1.000
job34.day1 1.000
job34.day6 1.000
job34.day7 1.000
job35.day2 1.000
job35.day6 1.000
job36.day2 1.000
job36.day7 1.000
job37.day1 1.000
job37.day5 1.000
job38.day1 1.000
job38.day3 1.000
job38.day5 1.000
job39.day4 1.000
job39.day5 1.000
job40.day2 1.000
job40.day7 1.000
job42.day1 1.000
job42.day4 1.000
job42.day6 1.000
job44.day1 1.000
job45.day5 1.000
job46.day2 1.000
job48.day4 1.000
job48.day5 1.000
job49.day5 1.000
job49.day7 1.000
We need 10 machines for the assignments to be non-overlapping. The number of sub-jobs for some of the machines is very small. Machine 10 has only one sub-job. The results look fine at first sight:
The numbers are the job numbers. E.g. job 1 appears in day 1, 2 and 6 all on machine 1.
- AttributeError: install_layout when attempting to install a package in a virtual environment
- Python list comprehension - want to avoid repeated evaluation
- Hash algorithm for dynamic growing/streaming data?
- matplotlib - making labels for violin plots
- Python How to I check if last element has been reached in iterator tool chain?
- Polars and the Lazy API: How to drop columns that contain only null values?
- Why are my Mean, Var, and Std outputs from NumPy different from what the online grader expects?
- Correlation dataframe convertion from results from pl.corr
- Polars DataFrame transformation
- Discord rate limiting while only sending 1 request per minute
- Check if column contains (/,-,_, *or~) and split in another column - Pandas
- How to draw a rectangle at (x,y) in a PyQt GraphicsView?
- how to calculate correlation between ten columns with polars
- How to set class attribute with await in __init__
- Detect hindi encoding, response received from Facebook API in Python
- Is it possible to write a horizontal if statement with a multi-line body?
- Max length of items in list
- Cannot subclass multiprocessing Queue in Python 3.5
- How can I get notified of updates to Python packages in a unified way?
- Using python AST to traverse code and extract return statements
- merge groups of columns in a polars dataframe to single columns
- Group Pandas DataFrame by Continuous Date Ranges
- Flask login @login_required not working
- Odoo: one2many and many2one? KeyError:'___'
- merge some columns in a Polars dataframe and duplicate the others
- Python: Create table from string mixed with separators using FOR loops
- How do I type hint a method with the type of the enclosing class?
- How can I verify an emails DKIM signature in Python?
- Writing a class that accepts a callback in Python?
- Python Paramiko channel.exec_command not returning output intermittently