Scheduling.jl

Scheduling.jl is a pure Julia package that can be seen as a framework for scheduling research. It is maintained by Sascha Hunold (TU Wien) and Bartlomiej Przybylski (AMU Poznan).

Contributors

• Daniel Cano Robledo (Hu's algorithm)
• Rupert Ettrich (Hu's algorithm)
• Jan Hadl (Gonzales & Sahni algorithm for Q|prmp|Cmax)
• Christoph Priesner (Gonzales & Sahni algorithm for Q|prmp|Cmax)

Features

At the moment the package provides a limited amount of functionalities.

Scheduling

Scheduling is a main module of the package. It provides:

• a set of structures for representing:
  • fixed processing times jobs,
  • parallel machines,
  • schedules,
• functions for plotting a schedule and exporting it as a TeX file,
• functions for saving a schedule into an HDF5 binary file and loading it back from such a file.

Scheduling.Objectives

The Scheduling.Objectives module provides a number of objective functions that can be used to estimate the quality of a schedule.

Scheduling.Algorithms

This module provides a set of implementations of the scheduling algorithms. These algorithms may be used to transform a set of jobs and machines into a schedule based on exact, heuristic or approximation approach. The list of algorithms include the standard list algorithms like LPT, SPT, WLPT and WSPT.

Moreover a few algorithms for the $\text{P}||\text{C}_\text{max}$ problem are implemented:

• an exact algorithm based on the Integer Program,
• an approximation algorithm by Hochbaum & Shmoys,
• an on-line MR algorithm for the same problem by Fleischer & Wahl.

Installation

To use Scheduling we require Julia 1.0 or higher. Please see http://julialang.org/downloads for instructions on how to obtain Julia for your system. In order to install the Scheduling package, simply type:

julia> using Pkg; Pkg.add("Scheduling")

Quick start

The following example shows how to use some of the functionalities provided by the Scheduling.jl package

using Scheduling # We need the basic structures
using Scheduling.Algorithms # We will use some predefined algorithms
using Scheduling.Objectives # We will estimate the quality of the resulting schedules

# Generate a set of jobs with processing times from an array
J = Jobs([27, 19, 19, 4, 48, 38, 29, 21, 9, 22, 11, 27, 36, 34, 21, 7, 7, 28])
# Generate a set of 4 identical machines
M = Machines(4)

# Generate an optimal schedule using IP
OPT = Algorithms.P__Cmax_IP(J, M)
# As all the numbers are rational and we expect the length
# of the schedule to have integer time, we need to convert
# the Cmax value
println("Optimal schedule:     Cmax = $(Int(cmax(OPT)))")

# Generate a schedule using LPT list rule
LPT = Algorithms.lpt(J, M)
println("LPT schedule:         Cmax = $(Int(cmax(LPT)))")

# Generate a schedule using SPT list rule
SPT = Algorithms.spt(J, M)
println("SPT schedule:         Cmax = $(Int(cmax(SPT)))")

# Generate a schedule using the Hochbaum-Shmoys algorithm
HS = Algorithms.P__Cmax_HS(J, M, eps = 1//3)
println("HS schedule:          Cmax = $(Int(cmax(HS)))")

# Plot the optimal schedule
Scheduling.plot(OPT)

The output will be:

Optimal schedule:     Cmax = 102
LPT schedule:         Cmax = 104
SPT schedule:         Cmax = 125
HS schedule:          Cmax = 124

and then the optimal plot will be generated by the PyPlot package.

Please note that the functions copy the input vectors before they execute the algorithm. If you want to prevent that, you may call respective functions ending with !, e.g. P__Cmax_HS!.