Scheduler

Concept

Concept

With the scheduler you can optimize the assignment of tasks to agents. Every task takes an amount of time to complete and yields a reward once completed. Every agent is characterized by his availability: it can be either available in a certain timeslot (1) or not(1).

The scheduler tries to assign jobs to agents such that it maximizes the reward of job execution while respecting the schedule of the agents.

For example, suppose we have two tasks with a Duration of 2 and 3:

\[\begin{split}D = \begin{bmatrix} 2\\ 3 \end{bmatrix}\end{split}\]

For now, let’s assume that for both tasks we get a Reward of 5 if we execute it:

\[\begin{split}R = \begin{bmatrix} 5\\ 5 \end{bmatrix}\end{split}\]

We also have two agents, which operate in the time interval [1, 2, …, 5]. Agent 1 is available during the first two timeslots, agent 2 during the last three. Let us denote the agents’ Availability by A:

\[\begin{split}A = \begin{bmatrix} 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 1 \end{bmatrix}\end{split}\]

We can immediately see that the optimal assignment is to assign the start of task 1 to agent 1 in timeslot 1, and task 2 to operator 2 in timeslot 3. This may seem trivial, but imagine having 1000 tasks and 100 agents!

Luckily, we can use the simpleor.scheduler module. You can:

• import a solver in your own code

• use the command line to read problem description files and write to a solution file.

Usage

Usage Solver

You can import the schedule solver as follows:

from simpleor.scheduler import ScheduleSolverTimeIndex

schedule_solver = ScheduleSolverTimeIndex(
    task_durations=task_durations,
    available_timeslots=available_timeslots,
    task_rewards=task_rewards
)

Since we are now in programming language, we start counting from 0, not 1. Calling .solve() on the ScheduleSolverTimeIndex instance will run an Integer Linear Programming solver on the problem description.

schedule_solver.solve()

Now we can inspect the solution. The inspection returns a list. Each element of the list is an assigned task, with the following fields: task_id, agent_id, start_time, stop_time, task_duration

schedule_solver.get_solution(kind="native")

[
    (0, 0, 0, 2, 2),
    (1, 1, 2, 5, 3),
]

You can also use kind="dataframe", in which case you get back a pandas dataframe.

In case you do not want to program in Python, you can use the command line.

$ scheduler --help``

Usage: schedule [OPTIONS]

  Command Line Interface for scheduler

Options:
  --durationsfile TEXT  Path to task_durations file
  --schedulefile TEXT   Path to available_schedule file
  --rewardsfile TEXT    Path to task rewards file (optional, default equal reward)
  --read TEXT           What kind of file to read (['csv', 'excel'])
  --solutiondir TEXT    Directory where the solution is written to
  --solutionfile TEXT   Filename of the solution
  --write TEXT          What kind of file to read (['csv', 'excel'])
  -v, --verbose TEXT    Verbosity level ['debug', 'info', 'warning', 'error',
                        'critical']
  --help                Show this message and exit.

First, you need to create two files.

• task_durations.csv, which should be a list of the task durations (in one column). The task durations should be integer.

• available_schedule.csv, where every row corresponds to an agent. A row corresponds to an agent, a column to a period. A 1 indicates the agent is available in that timeslot, a 0 means not available.

Optionally, you can have a task_rewards.csv file specifying the value of executing a certain task. If you do not specify this file, the solver will assume an equal reward for every task.

You can store these files anywhere you like. Save the paths to these files somewhere.

Next, open a terminal and type the following command (replace <TASK_DURATION_PATH> and <AVAILABLE_SCHEDULE_PATH> with the paths you just stored):

$ schedule --durationsfile <TASK_DURATION_PATH> --schedulefile <AVAILABLE_SCHEDULE_PATH>

By default, the solution will be stored in the data directory of the package. If you want to store it somewhere else, add the following flag: --solutiondir <SOLUTION_DIRECTORY_PATH>

By default, the name of the solution file is solution_cli.csv. In case you want to change it, add the flag --solutionfile solution_cli

Instead of csv, you can also use excel files. In that case, add the following flag: --read excel or --write excel

Usage Generator

Still on my todo list :)

Code

Code

class simpleor.scheduler.ScheduleProblemGenerator(n_agents: int, n_timeslots: int, n_tasks: int, min_task_duration: Optional[int] = 1, max_task_duration: Optional[int] = None, min_block_duration: Optional[int] = 1, max_block_duration: Optional[int] = None)

Class for generating scheduling problems.

Args:

n_agents (int): number of agents n_timeslots (int): number of timeslots n_tasks (int): number of tasks min_task_duration (int, optional): minimum task duration. Defaults to 1. max_task_duration (int, optional): maximum task duration. Defaults to n_timeslots. min_block_duration (int, optional): minimum number of consecutive timeslots

that an agent has to be available. Defaults to 1. (e.g. min_block_duration = 3 implies that the agent is either not available or available for at least 3 timeslots consecutively)

max_block_duration (int, optional): maximum number of consecutive timeslots

that an agent has to be available. Defaults to n_timeslots.

generate(generate_rewards: Optional[bool] = False, min_reward: Optional[int] = None, max_reward: Optional[int] = None)

Generates a scheduling problem based on class attributes

The main attributes that are set with this method are self.available_timeslots, self.task_durations and optionally self.task_rewards if generate_rewards = True.

Args:

generate_rewards (bool): if the rewards should be

generated or not

min_reward (int, optional): minimum reward value max_reward (int, optional): maximum reward value

class simpleor.scheduler.ScheduleSolverBase(task_durations: List[int], available_timeslots: List[List[int]], task_rewards: Optional[List[Union[int, float]]] = None)

Base class for common functionality of schedule solvers We are interested in the setting where machines are not always available and jobs have job-specific rewaurds.

Args:

task_durations (list): integers with task durations available_timeslots (list): list of list of integers where 1

indicates the agent is available and 0 not available. currently assumes wide format, where a row is a machine and a column a time index

task_rewards (list): floats of reward received for completing task

get_objective_value() → float

Returns the objective value of the optimal solution (if solution is found)

get_solution(kind: Optional[str] = 'native')

Get the solution of the scheduling problem

Args:

kind (str, optional): choose ‘native’ to return native python objects,

‘dataframe’ for a pandas solution.

Returns:

the solution as native python object or dataframe

get_status() → str

Returns the solution status after the problem has been tried to solve

set_problem()

Sets the Linear Programming problem of the object. This functions sets the variables, constraints, and objective.

solve()

Solves the scheduling problem based on the object’s attribute

write_solution(directory: str, filename: str, how: str)

Write solution of scheduling problem to disk

Args:

directory (str): directory where the solution should be saved filename (str): filename of the solution how (str): how the file should be saved

(choose ‘csv’ or ‘excel’)

class simpleor.scheduler.ScheduleSolverContinuousStartTime(task_durations: List[int], available_timeslots: List[List[int]], task_rewards: Optional[List[Union[int, float]]] = None)

class simpleor.scheduler.ScheduleSolverTimeIndex(task_durations: List[int], available_timeslots: List[List[int]], task_rewards: Union[List[Union[int, float]], NoneType] = None)

simpleor.scheduler.read_schedule_problem(task_durations_file_path: str, available_schedule_file_path: str, how: str, task_rewards_file_path: Optional[str] = None, **kwargs) → Tuple

Reads scheduling problem data from csv files

Args:

task_durations_file_path (str): path to the task durations file available_schedule_file_path (str): path to the file with information

about when agents are available (str)

rewardsfile (str): path to the task rewards file how (str): method of how to read (choose csv/excel)

Returns:

task_durations (list): list with task durations available_schedule (list): list with information about when an agent

is available

task_rewards (list): list with task rewards. all 1 if reward file not

specified