$\text{P}||\text{C}_\text{max}$

The $\text{P}||\text{C}_\text{max}$ problem is one of the most popular scheduling problems known. There exist plenty of different algorithms and approaches to solving it or approximating an exact solution, as the problem itself is strongly NP-hard. Scheduling.jl provides a few algorithms for the $\text{P}||\text{C}_\text{max}$ problem which state a base for extending the package by new ones.

Scheduling.Algorithms.P__Cmax_IP! — Method.

P__Cmax_IP!(J::Vector{Job}, M::Vector{Machine}; optimizer = GLPK.Optimizer)

Solves the P||Cmax problem by applying the simple IP proposed by Drozdowski (2009, p. 23). By default, the open source GLPK optimizer together with JuMP is used. This algorithm works on original J and M vectors which are also returned with the resulting schedule. In order to use copies, see P__Cmax_IP.

This algorithm is based on the following job parameters: p (processing time).

References

M.Drozdowski, Scheduling for Parallel Processing, Springer-Verlag, London, 2009, ISBN: 978-1-84882-309-9.

source

Scheduling.Algorithms.P__Cmax_IP — Method.

P__Cmax_IP(J::Vector{Job}, M::Vector{Machine}; optimizer = GLPK.Optimizer)

The same as P__Cmax_IP!, but it copies the input vectors before the algorithm starts.

source

Scheduling.Algorithms.P__Cmax_HS! — Method.

P__Cmax_HS!(J::Vector{Job}, M::Vector{Machine}; eps = 1//10, verbose = false)

Finds an approximation solution of the P||Cmax problem based on the algorithms proposed by Hochbaum and Shmoys (1987). This algorithm works on original J and M vectors which are also returned with the resulting schedule. In order to use copies, see P__Cmax_HS.

This algorithm is based on the following job parameters: p (processing time).

References

D.S. Hochbaum and D.B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM, 34(1):144–162 (1987), doi: 10.1145/7531.7535

source

Scheduling.Algorithms.P__Cmax_HS — Method.

P__Cmax_HS(J::Vector{Job}, M::Vector{Machine}; eps = 1//10, verbose = false)

The same as P__Cmax_HS!, but it copies the input vectors before the algorithm starts.

source

Scheduling.Algorithms.P__Cmax_MR! — Method.

P__Cmax_MR!(J::Vector{Job}, M::Vector{Machine})

An approximation approach to the online version of the P||Cmax problem proposed by Fleischer and Wahl (2000, p. 345). This algorithm works on original J and M vectors which are also returned with the resulting schedule. In order to use copies, see P__Cmax_MR.

This algorithm is based on the following job parameters: p (processing time).

References

R. Fleischer and M. Wahl, On-line scheduling revisited, Journal of Scheduling, 3:343–353 (2000), doi: 10.1002/1099-1425(200011/12)3:6<343::AID-JOS54>3.0.CO;2-2

source

Scheduling.Algorithms.P__Cmax_MR — Method.

P__Cmax_MR(J::Vector{Job}, M::Vector{Machine})

The same as P__Cmax_MR!, but it copies the input vectors before the algorithm starts.

source