matyama / makespan Goto Github PK

Implement the more algorithms for parallel identical resources:

• List Scheduling approximation algorithm for P|prec|C_max
• Rothkopf's Dynamic Programming for P||C_max
• Muntz&Coffman's Level Algorithm for P|pmtn,prec|C_max

Add a unit test that hits the BRTP check in Bratley's Branch&Bound algorithm.

Currently the resulting Schedule is simply wrapped in an Option context regardless of what happened during scheduling. It would be nice to have better (read: more informative) error reporting.

For instance:

• Distinguish between invalid inputs (e.g. r=0 or empty p) and infeasible solutions
• Distinguish internal errors produced by the scheduling algorithms (e.g. BnB search encounters partial solution but there are no remaining tasks)

Note that the latter case (internal errors) might be relevant for algorithm debugging but probably are not relevant to users.

Consider re-introduction of linear sorting - e.g. using voracious_radix_sort.

Some algorithms would benefit from reduced asymptotic complexity but investigate the effect with benchmarks. One possibility would be to enable it only for large enough inputs or for certain T: Time types.

Re-introduce additional metadata in the scheduling result in addition to the Schedule.

For instance:

• search statistics
• approximation factor

Benchmarks currently do not compile and use unstable feature(test) macro. Rework them using for instance criterion.