Description

This downloadable virtual product contains a template project for heuristic scheduling in Python. The heuristic production scheduler loads jobs from a job list onto a set of machines, considering due dates and trying to complete jobs just-in-time. The underlying model is a heuristic loading model that considers a weighted scoring function.

This heuristic loading project was originally developed for a food delivery service, faced with the following task:

• There is a limited group of resources used for preparing meals
• Meals are ordered and have a specified due date, with peaks around morning hours, mid day, and evening hours
• If food is delivered too early, or cooked too early, the taste and freshness suffers and customer satisfaction declines
• If food is delivered too late, customer satisfaction also declines
• Resources for food preparation have startup costs and changeover costs (cleaning, heating) and associated changeover times (e.g. heating up oil for frying french fries / chips)

In short, the objective of this scheduler was to use available resources efficiently, with just-in-time meal preparation whenever possible – in order to maximize customer satisfaction. The tool was deployed as a web-app, using the code available in this project as the underlying solving core. The approach can be used for other types of scheduling problems as well, e.g. job shop scheduling.

Benefits and disadvantages of heuristic scheduling in Python

The main benefit of heuristic scheduling in Python are their fast solution and computation time. Another advantage is that no commercial solver is required, which saves costs.

The main disadvantage of using a scheduling heuristic is higher maintenance and adjustment effort, compared to an analytical computation model solved by an analytical solver such as e.g. Gurobi.

Detailed content of this downloadable heuristic scheduling tool

Below is a screenshot of the contents of this downloadable heuristic scheduling tool. The download is made available in the form of a zip-file.

This tool comprises the following Python modules and executable main application scripts, with associated input-data templates and module installation dependencies:

• main.py: executable file, requires Python installation (Python 3.10 or newer). Implements the solution to the exemplary food delivery service problem, consuming the other modules contained by the zip-file.
• model.py: module that implements the function for heuristic scheduling, used by the main.py application example. The heuristic loading algorithm is specified in this module.
• data.py: contains a data structure for handling scenario data related to the scheduling problem.
• framework.py: module that contains classes for modelling machines and jobs.
• filetools.py: module that contains functions for loading the jobs and machines from the input files.
• viztool.py: module for visualizing scheduling results.
• config.py: allows e.g. configuration of input file paths, output file paths, and optimization parameters alpha (importance of avoiding early production), beta (importance of avoiding setups and changeovers), and gamma (importance of avoiding overdue delivery).
• jobs.csv: contains the jobs with their durations, due dates, and product families.
• schedule.csv: output file into which the resulting schedule is written.
• machines.csv: input file that lists the machines with any already running job ids, if any.
• requirements.txt: dependencies in Python requirred for running this project.

While the user populates the input files and configures model parameters via the config-file, the scheduler generates the output files (schedule table and gantt chart).

Below is an example of the jobs for a given day in a food delivery service business, scheduled with this tool in the past (there are more than 100 customer orders that day, represented in the jobs.csv file) with due dates and durations specified in seconds. Due dates are specified as seconds after scheduling start, i.e. midnight in this case.

For the exemplary food delivery service, used as a use case example by the example implementation in this downloadable project, 5 resources were used for meal preparation. They are modelled in the machines.csv file as illustrated below. You will see that for the food delivery service, no jobs where considered to be running i.e. already assigned jobs at the beginning of the scheduling horizon (midnight of the next day). For this reason, all entries in the “current_job” column are set to 0. If the scheduler had to consider already or still running jobs for a given machine, its ID key would be specified in this column.

The main.py application, executable if you have installed Python, currently prints the schedule into the terminal, saves it in the configured schedule.csv file, and also outputs it as a gantt-chart. See below.

Additional remarks and assumptions

The current implementation of the library and scheduling algorithm make the following assumptions:

• Changeover time and setup time, specified in the config.py file, is considered for the first job on a resource, if the job is not an already running job, and for any changeover to another job that is not from the same family (meal category in the case of the food delivery service).
• The main optimization parameters considered by the scheduler are time an production order finishes early (“inventory time”), the changeover and setup times (“changeover time”), and the time a production order finishes late (“backlog time”), i.e. after due date.
• The relative importance of these three factors is weighted by specifying
  • alpha: cost of inventory time
  • beta: cost of changeover time
  • gamma: cost of backlog time

For any customizations or extensions please contact us for a commercial offer. All of the assumptions can be tailored to your specific needs.