Scheduling Problems

johnsons(times::Matrix)

Given a matrix of times, returns a JohnsonResult with the permutation of the jobs. If number of machines is 2, it uses the Johnson's algorithm for 2 machines. If number of machines is greater than 2, it uses the Johnson's algorithm by transforming the problem into a 2-machine problem. In order to reduce the original problem to a 2-machine problem, the algorithm checks if the minimum time of the first machine is greater or equal than the maximum time of the other machines and/or if the minimum time of the last machine is greater or equal than the maximum time of the other machines.

For example if we have 4 machines, namely, A, B, C, and D at least one of the following conditions must be satisfied:

• min(A) >= max(B, C)
• min(D) >= max(B, C)

The function throws a JohnsonException if the problem cannot be reduced to a 2-machine problem.

Arguments

• times::Matrix: a matrix of times

Returns

• JohnsonResult: a custom data type that holds the permutation of the jobs

Example

times = Float64[
    3.1 2.8;
    4.0 7.0;
    8.0 3.0;
    5.0 8.0;
    6.0 4.0;
    8.0 5.0;
    7.0 4.0
]

result = johnsons(times)

println(result.permutation)

johnsons_ga(times::Matrix; popsize = 100, ngen = 1000, pcross = 0.8, pmutate = 0.01, nelites = 1)::JohnsonResult

Given a matrix of times, returns a JohnsonResult with the permutation of the jobs. The function uses a genetic algorithm to find the best permutation of the jobs. The genetic algorithm is implemented in the RandomKeyGA module.

Arguments

• times::Matrix: a matrix of times
• popsize::Int: the population size. Default is 100
• ngen::Int: the number of generations. Default is 1000
• pcross::Float64: the crossover probability. Default is 0.8
• pmutate::Float64: the mutation probability. Default is 0.01
• nelites::Int: the number of elites. Default is 1

Returns

• JohnsonResult: a custom data type that holds the permutation of the jobs

Example

times = Float64[
    3.1 2.8;
    4.0 7.0;
    8.0 3.0;
    5.0 8.0;
    6.0 4.0;
    8.0 5.0;
    7.0 4.0
]

result = johnsons(times)

println(result.permutation)

makespan(times::Matrix, permutation::Vector{Int})

Given a matrix of times and a permutation of the jobs, returns the makespan of the jobs.

Arguments

• times::Matrix: a matrix of times
• permutation::Vector{Int}: a permutation of the jobs

Returns

• Float64: the makespan of the jobs

Example

julia> times = Float64[
    3 3 5;
    8 4 8;
    7 2 10;
    5 1 7;
    2 5 6    
]

julia> result = makespan(times, [1, 4, 5, 3, 2])