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).
- 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)
At the moment the package provides a limited amount of functionalities.
Scheduling is a main module of the package. It provides:
- a set of structures for representing:
- fixed processing times jobs,
- parallel machines,
- 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 module provides a number of objective functions that can be used to estimate the quality of a schedule.
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
- 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.
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")
The following example shows how to use some of the functionalities provided by the
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
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