flow-shop-scheduling

KO | EN

gitlite — search

#javascript #python #hacktoberfest #react #ai #typescript #llm #go #golang #android #machine-learning #rust #deep-learning #linux

flow-shop-scheduling

★ 12 Open GitHub ↗

Flow Shop Scheduling example using the Quantum Hybrid NL Solver.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

[![Open in GitHub Codespaces](https://img.shields.io/badge/Open%20in%20GitHub%20Codespaces-333)](
  https://codespaces.new/dwave-examples/flow-shop-scheduling?quickstart=1)

# Flow Shop Scheduling

Job shop scheduling (JSS)
is an optimization problem with the goal of scheduling jobs on a variety of machines,
where jobs are processed on machines in different orders. The objective is to
minimize the time it takes to complete all jobs, also known as the "makespan".
Flow shop scheduling (FSS)
is a constrained case of JSS where each job uses each machine in the same
order. The machines in FSS problems can often be seen as sequential operations
to be executed on each job, as is the case in this example.

This is a basic example of flow show scheduling that can easily be extended to different
objectives, such as minimizing the delay for the scheduled completion of each job.

This example demonstrates three ways of formulating and optimizing FSS:

*   Formulating a
    [nonlinear model](https://docs.dwavequantum.com/en/latest/concepts/models.html#nonlinear-model)
    and solving on the Stride&trade; hybrid solver
*   Formulating a
    [constrained quadratic model](https://docs.dwavequantum.com/en/latest/concepts/models.html#constrained-quadratic-model)
    (CQM) and solving on the CQM hybrid solver
*   Formulating a constrained quadratic model (CQM) and solving it using SciPy's HiGHS solver.

This example lets you run the scheduler from either the command line or a visual
interface built with [Dash](https://dash.plotly.com/).

![Demo Screenshot](https://raw.githubusercontent.com/dwave-examples/flow-shop-scheduling/main/static/demo.png "Image of demo interface")
![Demo Screenshot](https://raw.githubusercontent.com/dwave-examples/flow-shop-scheduling/main/static/demo_solution.png "Image of demo interface with solution")

## Installation
You can run this example without installation in cloud-based IDEs that support the
[Development Containers Specification](https://containers.dev/supporting) (aka "devcontainers")
such as GitHub Codespaces.

For development environments that do not support `devcontainers`, install requirements:

```bash
pip install -r requirements.txt
```

If you are cloning the repo to your local system, working in a
[virtual environment](https://docs.python.org/3/library/venv.html) is recommended.

## Usage
Your development environment should be configured to access the
[Leap&trade; quantum cloud service](https://docs.dwavequantum.com/en/latest/ocean/sapi_access_basic.html).
You can see information about supported IDEs and authorizing access to your Leap account
[here](https://docs.dwavequantum.com/en/latest/ocean/leap_authorization.html).

Run the following terminal command to start the Dash application:

```bash
python app.py
```

Access the user interface with your browser at http://127.0.0.1:8050/.

The demo program opens an interface where you can configure and submit problems to a solver.

Configuration options can be found in the [demo_configs.py](demo_configs.py) file.

> [!NOTE]\
> If you plan on editing any files while the application is running, please run the application
with the `--debug` command-line argument for easier debugging:
`python app.py --debug`

Alternatively, you can run the flow shop scheduler without the Dash interface using the following
command:

```bash
python flow_shop_scheduler.py [-h] [-i INSTANCE] [-tl TIME_LIMIT]
[-os OUTPUT_SOLUTION] [-op OUTPUT_PLOT] [-sp] [-cqm] [-v] [-q] [-p PROFILE]
[-mm MAX_MAKESPAN]
```

The command line arguments are as follows:
- -h (or --help): show this help message and exit
- -i (--instance): path to the input instance file (default: input/tai20_5.txt);
  see `app_configs.py` for instance names
- -tl (--time_limit) time limit in seconds (default: None)
- -os (--output_solution): path to the output solution file (default:
  output/solution.txt)
- -op (--output_plot): path to the output plot file (default:
  output/schedule.png)
- -sp (--use_scipy_solver): use SciPy's HiGHS solver instead of a hybrid solver, overrides -cqm
  (default: False)
- -cqm (--use_cqm_solver): use the CQM solver instead of the Stride solver
  (default: False)
- -v (--verbose): print verbose output (default: True)
- -p (--profile): profile variable to pass to the sampler (default: None)
- -mm (--max_makespan): manually set an upper bound on the schedule length
  instead of auto-calculating (default: None)

### Input Data
Several problem instances are available in the `input` folder. These instances fall into two
categories:
- [OR-Library] problem instances are contained within the `flowshop1.txt` file. These can be used by
referencing the short name (e.g., "car2", "reC13") in the `app_configs.py` file under `SCENARIOS`.
- [E. Taillard's list] of benchmarking instances are separated into one file per instance. If the
file name starts with "tai", the model expects the format used by Taillard. These can be accessed by
referencing the full file name (e.g., "tai20_5.txt", "tai20_20.txt") in the `app_configs.py` file
under `SCENARIOS`.

These datasets are processed differently so consider following one of these two file structures when
adding new data or update the `load_from_file` function in `model_data.py` to support new file
structures.

### Output
Command line runs will, by default, output a text and image file to an `output` directory. The image
file will contain a plot of the solution and the text file will contain a table of the solution with
columns specifying job id, task, start, dur, task, start, dur, etc.

Dash interface runs will return results as a DataFrame that will be displayed as a Plotly figure in
the user interface.

## Problem Description
The goal of the flow shop scheduling problem is to complete all jobs as quickly as possible.
The model sets the following objectives and constraints to achieve this goal:

**Objectives:** minimize the total completion time (makespan).

**Constraints:** the constraints for this problem fall into multiple categories.
- **Precedence Constraint** ensure that all tasks of a job are executed in the given order.
- **No-Overlap Constraints** ensure no two jobs can execute on the same machine at the same time.
- **Makespan Constraint** (optional) puts an upper bound on the time it takes to complete all jobs.

Constraints are handled differently in the CQM and Stride formulations. The CQM
formulation must explicitly state each constraint and therefore searches a solution space
that includes variable assignments that are infeasible (constraints are violated). The Stride solver
has no need for explicit constraints as the structure of the model limits potential
solutions to only those that adhere to the constraints. By using implicit constraints to limit
the search space to only valid solutions, the Stride solver is often able to find better solutions,
faster.

## CQM Model Overview

### Problem Parameters

- `n`: the number of jobs
- `m`: the number of machines
- `J`: set of jobs (`{0,1,2,...,n-1}`)
- `M`: set of machines (`{0,1,2,...,m-1}`)
- `T`: set of tasks (`{0,1,2,...,m-1}`) that has same dimension as `M`
- `M_(j,t)`:  the machine that processes task `t` of job `j`
- `T_(j,i)`: the task that is processed by machine `i` for job `j`
- `D_(j,t)`:  the processing duration that task `t` needs for job `j`
- `V`:  maximum allowed makespan

### Variables
- `w`: a positive integer variable that defines the completion time (makespan)
  of the JSS
- `x_(j_i)`: positive integer variables used to model start of each job `j` on
  machine `i`
- `y_(j_k,i)`: binaries which define if job `k` precedes job `j` on machine `i`

### Objective
To minimize the total completion time (makespan).

### Constraints
The CQM requires adding a set of explicit constraints to
ensure that tasks are executed in order and that no single machine is used by
different jobs at the same time.

#### Precedence Constraint
Our first constraint, [equation 1](#eq2), enforces the precedence constraint.
This ensures that all tasks of a job are executed in the given order.

![equation1](https://raw.githubusercontent.com/dwave-examples/flow-shop-scheduling/main/static/eq1.png "Equation showing that the start of the next job must come after the previous job")          (1)

This constraint ensures that a task for a given job, `j`, on a machine,
`M_(j,t)`, starts when the previous task is finished. As an example, for
consecutive tasks 4 and 5 of job 3 that run on machine 6 and 1, respectively,
assuming that task 4 takes 12 hours to finish, we add this constraint:
`x_3_6 >= x_3_1 + 12`

#### No-Overlap Constraints
Our second constraint, [equation 2](#eq2), ensures that multiple jobs don't use
any machine at the same time.
![eq2](https://raw.githubusercontent.com/dwave-examples/flow-shop-scheduling/main/static/eq2.png "Equation preventing any two jobs on the same machine at the same time")          (2)

Usually this constraint is modeled as two disjunctive linear constraints
([Ku et al. 2016](#Ku) and [Manne et al. 1960](#Manne)); however, it is more
efficient to model this as a single quadratic inequality constraint. In
addition, using this quadratic equation eliminates the need for using the so
called [Big M](https://en.wikipedia.org/wiki/Big_M_method) value to activate or relax constraint.

The proposed quadratic equation fulfills the same behavior as the linear
constraints:

There are two cases:

- if `y_j,k,i = 0` job `j` is processed after job `k`:
  ![equation2_1](https://raw.githubusercontent.com/dwave-examples/flow-shop-scheduling/main/static/eq2_1.png "Equation simplifying above equation preventing two jobs on the same machine at the same time")
- if `y_j,k,i = 1` job `k` is processed after job `j`:
  ![equation2_2](https://raw.githubusercontent.com/dwave-examples/flow-shop-scheduling/main/static/eq2_2.png "Equation simplifying above equation preventing two jobs on the same machine at the same time")
  Since these equations are applied to every pair of jobs, they guarantee that
  the jobs don't overlap on a machine.

#### Makespan Constraint
In this demonstration, the maximum makespan can be defined by the user or it
will be determined using a greedy heuristic. Placing an upper bound on the
makespan improves the performance of the sampler; however, if the upper
bound is too low then the sampler may fail to find a feasible solution.

## Stride Model Overview
The model for the Stride solver is constructed using the
[flow shop scheduling generator](https://docs.dwavequantum.com/en/latest/ocean/api_ref_optimization/generators.html#dwave.optimization.generators.flow_shop_scheduling)
provided in ``dwave-optimization``.

### Problem Parameters

- `processing_times`: an `mXn` array where `processing_times[m, n]` is the duration of job n on
machine m.

### Variables
- `order`: An array of integer variables of length num jobs.

### Objective
To minimize the last job end time.

### Constraints
Typically, solver performance strongly depends on the size of the solution space for the modeled
problem: models with a smaller solution space tend to perform better than ones with a larger space
as there are less potential solutions to search through to find optimality. A powerful way to reduce
the solution space is by using variables that act as implicit constraints. Such a variable
reduces the solution space to solutions that adhere to its implicit constraints. The Stride solver
has many variable types that allow for model construction to integrate constraints implicitly.
In this problem example, both constraints are handled implicitly.

#### Precedence Constraint
The precedence constraint ensures that all tasks of a job are executed in the given order.

This model uses the
[dwave-optimization](https://docs.dwavequantum.com/en/latest/ocean/api_ref_optimization/index.html)
 ``ListVariable`` to efficiently permutate the order of jobs which prevents violation of this
 constraint, as the constraint is implicitly built into the model.

As can be seen in the two images below, switching the job order can
improve the solution quality, corresponding to a shorter completion
time (makespan).

![fss_example0](https://raw.githubusercontent.com/dwave-examples/flow-shop-scheduling/main/static/fss_example0.png "A schedule showing an inefficient ordering of jobs")
Above: a solution to a flow shop scheduling problem with 3 jobs on 3 machines.

![fss_example1](https://raw.githubusercontent.com/dwave-examples/flow-shop-scheduling/main/static/fss_example1.png "The same schedule as above but with the job order permuted which minimizing overall completion time")
Above: an improved solution to the same problem with a permuted job order.

#### No-Overlap Constraints
The no-overlap constraint ensures that no two jobs use the same machine at the same time.

The ``max`` operation is used to extract the start time for each job, ensuring there is no overlap
between jobs on machines. This constraint is built into the model and therefore, all solutions in
the solution space adhere to it.

## References
<a id="Manne"></a>
A. S. Manne, On the job-shop scheduling problem, Operations Research , 1960,
Pages 219-223.

## License

Released under the Apache License 2.0. See [LICENSE](LICENSE) file.

[E. Taillard's list]: http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html
[OR-Library]: https://people.brunel.ac.uk/~mastjjb/jeb/orlib/flowshopinfo.html

flow-shop-scheduling

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README