torkin1 / bnb_vs_gurobi Goto Github PK

A perfomance comparison about a Branch and Bound implementation and Gurobi using a Single Machine Scheduling problem as Use Case.

Python 58.04% Jupyter Notebook 41.96%

bnb_vs_gurobi's Introduction

bnb_vs_gurobi's People

Contributors

Stargazers

Watchers

bnb_vs_gurobi's Issues

Implement BnB proof with pareto distributed weights

Move dynamic Job params in a ScheduledJob subclass

Machine instance will retain a list of ScheduledJob instances. Solvers must work with ScheduledJob Instances. Solution must be calculated using ScheduledJob instances in Machine objects.

Adapt SPTF to non-zero wheigts case

wheights must be equal to 1 when calculating a LB for B&B using SPTF scheduler

implement input dimension proof

Implement Bnb vs Gurobi execution times proof

Sometimes objective function is calculated with None value as completion times

fixed bug in sptf rule: when there are no released job to process, shortest job must not be processed if it was completed in the previous round

Add pretty formatted sms problem linear formulation

cBnB scheduler doesn't account for weights > 1

bnb algorithm does not use preemption

When choosing a subschedule for the subproblems, it happens always that the jobs in that schedule does not preempt each other. This results in the final schedule not having preemption, thus leading to a final value always worst than the one obtained, for instance, from SPTF.

Maybe subproblems must be created when a job is released too?

implement Gurobi solver

Fix some bugs

trasnformed attributes from class attributes to instance attributes
now a job can have multiple starting times (because of preemption)
jobs track completion time too
schedule is represented with starting times saved in Job objects (no need to use LP vars anymore)