# 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

- 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!`

.