textPtextanytextC_textmax

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

Scheduling.jl provides a few algorithms for the $\text{P}|\text{any}|\text{C}_\text{max}$ problem.

Scheduling.Algorithms.P2_any_Cmax_DL — Method.
P2_any_Cmax_DL(J::Vector{Job}, M::Vector{Machine})

This is an exact pseudopolynomial algorithm for the P2|any|Cmax problem.

References

  • Du, J., & Leung, J. (1989). Complexity of scheduling parallel task systems. SIAM Journal on Discrete Mathematics, 2(4), 473–487. http://doi.org/10.1137/0402042
source
Scheduling.Algorithms.P_any_Cmax_MRT — Method.
P_any_Cmax_MRT(J::Vector{Job}, M::Vector{Machine})

This is a 3/2-approximation algorithm for the P|any|Cmax problem.

References

  • Mounié, G., Rapine, C., & Trystram, D. (2007). A 3/2‐Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks. SIAM Journal on Computing, 37(2), 401–412. http://doi.org/10.1137/S0097539701385995
source
Scheduling.Algorithms.P_any_Cmax_TWY — Method.
P_any_Cmax_TWY(J::Vector{Job}, M::Vector{Machine})

References

  • J. Turek, J. L. Wolf, and P. S. Yu. Approximate Algorithms Scheduling Parallelizable Tasks. In: SPAA. ACM, 1992, pp. 323–332. DOI: 10.1145/140901.141909.
source