Overview

pyschedule is a package to formulate and solve resource-constrained scheduling problems, which covers a lot! Its main modelling entities are:

• precedence relations between tasks (e.g. this one is before this one)
• resource requirements of tasks (e.g. this one can be done either by him or her)

Architecture

• pyschedule is not a general optimization language but only targets the scheduling use case. However, this already covers quite a lot of problems seen in practice. Within this universe, it tries to be as simple as possible but not simpler
• pyschedule is organized in scenarios where a scenario S is basically a list of tasks S.T, resources S.R and constraints S.constraints between tasks or tasks and resources. However, it is not necessary to study the internals of pyschedule to use it
• pyschedule exploits the python language to provide a syntax that is comparable to the usual declarative description languages, e.g. S += T1 < T2 means that in scenario S task T1 should finish before task T2 starts. Technically, T1 < T2 generates a constraint of type PrecedenceLax which is added to S
• pyschedule scenarios can be solved using different solvers which are not part of pyschedule. Hence, pyschedule offers a convenient front-end to formulate scheduling problems in order to try different approaches. The solution is written directly to the scenario. Specifically, each task T gets a start T.start and a list of resources T.resources
• pyschedule also offers GANTT-chart type of plotting, since optimization without visualization does not work

Solvers

pyschedule tries to gain the best of two worlds by supporting classical MIP-models as well as Constraint Programming solvers. All solvers are in the solvers subpackage:

• pulp.solve(scenario,kind) : classical bigM-type MIP-formulation build on top of package pulp, works for small models. Use parameter "kind" to select the MIP-solver ("CBC" (default if kind is not provided), "CPLEX", "GLPK"). CBC is part of pulp and hence works out of the box
• pulp.solve_discrete(scenario,horizon,kind) : time-indexed MIP-formulation, requires a "horizon"-parameter which defines the maximum number of time periods. The specific MIP-solver can also be selected via parameter "kind"
• ortools.solve(scenario,horizon) : the open source CP-solver of Google, a little restricted but good to ensure feasibility of larger models. Also requires the "horizon"-parameter. Make sure that package ortools is installed
• cpoptimizer.solve(scenario) : IBM CP Optimizer, requires command "oplrun" to be executable. Industrial-scale solver that runs fast on very large problems
• cpoptimizer.solve_docloud(scenario,api_key) : IBM CP Optimizer hosted in the cloud, you need to provide an "api_key" which you can get here for a trial
• to be continued ...

There are also some pre-defined heuristics (meta-solvers) that build on other solvers:

• listsched.solve : iteratively add tasks
• localsearch.solve : iteratively remove and add tasks

pyschedule has been tested with python 2.7 and 3.4. All solvers support a parameter "msg" to switch feedback on/off. Moreover, solvers.pulp.solve, solvers.pulp.solve_discrete and solvers.ortools.solve support a parameter "time_limit" to limit the running time.

Constraints

Precedences

• FIX : fixed start and used resources, e.g. T1.start = 3; T1.resource = [R1], this ensures that T1 will be scheduled starting at time 3 on resource R1. Note that this partially overwrites the final solution. Hence, the solving process respects a given partial solution
• BOUND : normal bounds, e.g. T1 > 3 or T1 < 5, this ensures that T1 is scheduled in between 3 and 5
• LAX : lax precedences, e.g. T1 < T2, T1 is finished before T2 starts
• LAXPLUS : lax precedences with offset, e.g. T1 + 3 < T2, T1 is finished 3 time units before T2 starts
• TIGHT : tight precedences, e.g. T1 <= T2, T2 starts exactly when T1 finishes
• TIGHTPLUS : tight precedences with offset, e.g. T1 + 3 <= T2, T2 starts exactly 3 time units after T1 finishes
• COND : conditional precedences, e.g. T1 + 3 << T2, if T1 and T2 share any resource and T1 finishes before T2, then T1 is finished even 3 time units before T2 starts

Resources

each task needs at least one resource. To keep the syntax concise, pyschedule used % as an operator to connect tasks and resources

• MULT : multiple resources, e.g. S += T1 % [R1, R2], T1 uses R1 and R2
• ALT : alternative resources, e.g. S += T1 % R1 | R2, T1 uses either R1 or R2
• ALTMULT : alternative resources which are similar for different tasks, e.g. S += R1 | R2 % [T1,T2], T1 and T2 either use R1 or R2, but they both use the same one
• CUMUL : cumulative resources, e.g. R1 = S.Resource('R1',size=3); S += T1 % R1*2, R1 has size 3 and T1 uses 2 units of that size whenever run. This can be used to model worker pools or any other resource with a high multiplicity. Using a resource of size n instead n resources of size 1 often helps the solver

Solvers vs Constraints

output of the test script:

	pulp.solve	pulp.solve_discrete	ortools.solve	cpoptimizer.solve
scenario
FIX	True	Error	True	True
BOUND	True	True	True	True
LAX	True	True	True	True
LAXPLUS	True	True	False	True
TIGHT	True	True	True	True
TIGHTPLUS	True	True	False	True
COND	True	True	False	True
ALT	True	True	True	True
MULT	True	True	True	True
ALTMULT	True	True	True	True
CUMUL	False	True	False	True

True means that the constraint is working, False means that the constraint has no effect, and Error means that it produces an error when using it (to be fixed).

Outlook

Constraints that are only partially implemented or on the TODO list:

• CAP : capacities, the envisioned syntax is S += R1[3:7] < 2 to ensure R1 can only process 2 time units between 3 and 7. Other metrics except pure time consumption should also be supported
• FIRST : first/last tasks on resources, the envisioned syntax is S += R1[3:7] < T1 to ensure that T1 is the last task on R1 in between 3 and 7
• MULT : high-multiplicity scheduling, the envisioned syntax is T1 = S.Task('T1',mult=10) which ensures that T1 is seen as a task consisting of 10 identical parts. This is partially done using task_groups in solver pulp.solve_discrete. Using this instead of adding 10 identical tasks can help the solver
• ??? : resource-dependent precedences, the envisioned syntax is S += R1 % T1 + 3 << T2 which ensures that only on resource R1 the conditional precedence T1 + 3 << T2 holds. This would make conditional precedences more applicable