Parallel Machine sample

We start by importing the module corresponding to the problem we want to tackle

%load_ext autoreload
%autoreload 2
import pyscheduling.PMSP.RmSijkCmax as pmsp_sijk

The autoreload extension is already loaded. To reload it, use:
  %reload_ext autoreload

We have 2 options to generate an instance: 1. By importing it from a text file. 2. By randomly generating it.

random generation : 2 arguments are mandatory to pass to the function : - Number of jobs - Number of machines

We can customize the random generation by passing multiple other parameters such as : - Minimal and/or maximal processing time - Minimal and/or maximal setup time - Release time factor - Setup time factor - Generation protocol, by default we use VALLADA - Generation probabilistic law, by default we use the uniform law

instance = pmsp_sijk.RmSijkCmax_Instance.generate_random(20,4)

There are 2 methods to use to solve a given instance : - Heuristics : Usually greedy algorithms used to find an inital solution to the problem. They are found in the Heuristics class of the imported module.

• Metaheuristics : More complicated algorithm designed to find very good solutions if given enough time. They are found in the Metaheuristics class of the imported module

Heuristics

Heuristics of the concerned problem are found in the Heuristics class of the imported module.

As being static methods of the mentioned class, we can call heuristics as follows :

solve_result = pmsp_sijk.Heuristics.constructive(instance)
print(solve_result)

Search stopped with status : FEASIBLE
 Solution is :
 Objective : 678
Machine_ID | Job_schedule (job_id , start_time , completion_time) | Completion_time
1 | (13, 0, 35) : (11, 35, 172) : (19, 172, 313) : (0, 313, 458) : (6, 458, 622) | 622
2 | (14, 0, 37) : (18, 37, 184) : (2, 184, 335) : (15, 335, 487) : (17, 487, 640) | 640
3 | (4, 0, 35) : (7, 35, 175) : (12, 175, 323) : (3, 323, 474) : (1, 474, 636) | 636
4 | (9, 0, 35) : (16, 35, 171) : (10, 171, 310) : (5, 310, 475) : (8, 475, 678) | 678
Runtime is : 0.000600200000917539s
time to best is : -1s

Metaheuristics

Metaheuristics of the concerned problem are found in the Metaheuristics class of the imported module.

As being static methods of the mentioned class, we can call metaheuristics as follows :

solve_result = pmsp_sijk.Metaheuristics.antColony(instance)
print(solve_result)

Search stopped with status : FEASIBLE
 Solution is :
 Objective : 674
Machine_ID | Job_schedule (job_id , start_time , completion_time) | Completion_time
1 | (19, 0, 37) : (8, 37, 197) : (11, 197, 338) : (0, 338, 485) : (7, 485, 650) | 650
2 | (14, 0, 37) : (18, 37, 184) : (4, 184, 328) : (17, 328, 477) : (12, 477, 642) | 642
3 | (15, 0, 50) : (2, 50, 210) : (3, 210, 364) : (13, 364, 514) : (10, 514, 665) | 665
4 | (6, 0, 44) : (16, 44, 187) : (9, 187, 323) : (5, 323, 482) : (1, 482, 674) | 674
Runtime is : 8.8761697000009s
time to best is : -1s

We can pass any eventual arguments compatible to the metaheuristic used in order to customize the solving process.

In the following, we specify the number of iterations of the metaheuristic to limit its execution time :

solve_result = pmsp_sijk.Metaheuristics.lahc(instance,n_iterations=10)
print(solve_result)

Search stopped with status : FEASIBLE
 Solution is :
 Objective : 635
Machine_ID | Job_schedule (job_id , start_time , completion_time) | Completion_time
1 | (8, 0, 47) : (19, 47, 193) : (11, 193, 333) : (13, 333, 470) : (6, 470, 624) | 624
2 | (15, 0, 39) : (14, 39, 183) : (18, 183, 330) : (2, 330, 481) : (17, 481, 635) | 635
3 | (3, 0, 39) : (7, 39, 187) : (12, 187, 335) : (4, 335, 472) : (1, 472, 624) | 624
4 | (5, 0, 46) : (9, 46, 197) : (10, 197, 334) : (16, 334, 472) : (0, 472, 616) | 616
Runtime is : 0.013670499989530072s
time to best is : 0.0046264999837148935s

General solver

There is a more general way to use the heuristics and metaheuristics without distinction by using the Solver class.

We pass the wanted method as a parameter to create a Solver instance which works with this given method. Then, to use the solver, we call its solve() method which takes an instance of the problem as a parameter and any eventual arguments compatible to the method used in order to customize the solving process

The above code can transform into the following :

solver = pmsp_sijk.Solver(pmsp_sijk.Heuristics.constructive)
solve_result = solver.solve(instance)
print(solve_result)

Search stopped with status : FEASIBLE
 Solution is :
 Objective : 678
Machine_ID | Job_schedule (job_id , start_time , completion_time) | Completion_time
1 | (13, 0, 35) : (11, 35, 172) : (19, 172, 313) : (0, 313, 458) : (6, 458, 622) | 622
2 | (14, 0, 37) : (18, 37, 184) : (2, 184, 335) : (15, 335, 487) : (17, 487, 640) | 640
3 | (4, 0, 35) : (7, 35, 175) : (12, 175, 323) : (3, 323, 474) : (1, 474, 636) | 636
4 | (9, 0, 35) : (16, 35, 171) : (10, 171, 310) : (5, 310, 475) : (8, 475, 678) | 678
Runtime is : 0.00028119998751208186s
time to best is : -1s

solver = pmsp_sijk.Solver(pmsp_sijk.Metaheuristics.lahc)
solve_result = solver.solve(instance,n_iterations=10)
print(solve_result)

Search stopped with status : FEASIBLE
 Solution is :
 Objective : 635
Machine_ID | Job_schedule (job_id , start_time , completion_time) | Completion_time
1 | (8, 0, 47) : (11, 47, 188) : (19, 188, 329) : (13, 329, 470) : (6, 470, 624) | 624
2 | (2, 0, 39) : (15, 39, 191) : (14, 191, 335) : (18, 335, 482) : (17, 482, 635) | 635
3 | (10, 0, 41) : (3, 41, 195) : (12, 195, 345) : (4, 345, 482) : (1, 482, 634) | 634
4 | (7, 0, 37) : (9, 37, 174) : (16, 174, 310) : (0, 310, 454) : (5, 454, 624) | 624
Runtime is : 0.012436999997589737s
time to best is : 0.004275000013876706s