untilperfect¶
Introduction¶
The untilperfect application solves the buffer preparation vessel sizing and assignment problem using mixed integer linear programming.
The source repo is at https://github.com/multipitch/untilperfect.
Builds are hosted at https://pypi.org/project/untilperfect/.
Documentation is hosted at https://untilperfect.readthedocs.io/.
This project was forked from https://github.com/multipitch/dissertation. The dissertation repo was created for my masters dissertation on the subject towards an MSc in Business Analytics from University College Dublin; further development has been forked here so that the dissertation repo remains frozen.
Install via pip:
$ pip install untilperfect
Provides the untilperfect CLI command
$ untilperfect --help
usage: model.py [-h] [-b BUFFERS] [-n] [-p PARAMETERS] [-f PATH] [-s SOLVER]
[-t PROBLEM_TYPE] [-v VESSELS] [-w]
Solves the buffer preparation assignment and selection problem.
optional arguments:
-h, --help show this help message and exit
-b BUFFERS, --buffers BUFFERS
buffers filename (default: 'buffers.csv')
-n, --no-plot do not generate plot
-p PARAMETERS, --parameters PARAMETERS
parameters filename (default: 'parameters.ini')
-f PATH, --path PATH file path (default: <current working directory>)
-s SOLVER, --solver SOLVER
solver to be used (default: 'COIN_CMD')
-t PROBLEM_TYPE, --problem-type PROBLEM_TYPE
specify model to solve (default: 'complete'), other
model options are 'basic', 'minimized_hold_time',
'mimimized_used_volume'
-v VESSELS, --vessels VESSELS
vessel filename (default: vessels.csv)
-w, --write write problem to file in .lp format
Distributed under the MIT License.
© Sean Tully 2018-2019.
Contents¶
Problem definition¶
The sections below detai lthe “complete” problem. Other problem variants are the “basic” and “minimized hold time” variants, which are discussed afterwards.
Given¶
Data on buffers e.g.
indices | names | volumes | use start times | use_durations |
---|---|---|---|---|
![]() |
![]() |
![]() |
![]() |
![]() |
0 | Buffer #1 | 5825.23 | 62.86 | 39.16 |
1 | Buffer #2 | 10214.75 | 79.63 | 25.5 |
2 | Buffer #3 | 13995.95 | 17.6 | 61.7 |
3 | Buffer #4 | 14619.52 | 74.28 | 44.19 |
4 | Buffer #5 | 4504.94 | 29.73 | 36.0 |
5 | Buffer #6 | 16361.95 | 5.5 | 38.78 |
6 | Buffer #7 | 3464.09 | 38.25 | 57.93 |
7 | Buffer #8 | 13387.42 | 11.35 | 36.55 |
8 | Buffer #9 | 1064.93 | 61.21 | 45.84 |
9 | Buffer #10 | 1654.58 | 34.88 | 22.03 |
10 | Buffer #11 | 23631.53 | 26.26 | 37.99 |
11 | Buffer #12 | 11546.57 | 94.15 | 56.41 |
Data on available vessels
indices | names | volumes | costs |
---|---|---|---|
![]() |
![]() |
![]() |
![]() |
0 | 1000 L | 1000.0 | 63.10 |
1 | 2000 L | 2000.0 | 95.64 |
2 | 3000 L | 3000.0 | 121.98 |
3 | 4000 L | 4000.0 | 144.96 |
4 | 5000 L | 5000.0 | 165.72 |
5 | 6000 L | 6000.0 | 184.88 |
6 | 8000 L | 8000.0 | 219.71 |
7 | 10000 L | 10000.0 | 251.19 |
8 | 12000 L | 12000.0 | 280.23 |
9 | 16000 L | 16000.0 | 333.02 |
10 | 18000 L | 18000.0 | 357.41 |
11 | 20000 L | 20000.0 | 380.73 |
12 | 22000 L | 22000.0 | 403.14 |
13 | 25000 L | 25000.0 | 435.28 |
14 | 30000 L | 30000.0 | 485.59 |
And some additional parameters:
parameter | symbol | value |
---|---|---|
process cycle time (h) | ![]() |
96.0 |
prep pre duration (h) | ![]() |
12.0 |
prep post duration (h) | ![]() |
1.5 |
transfer duration (h) | ![]() |
2.0 |
hold pre duration (h) | ![]() |
8.0 |
hold post duration (h) | ![]() |
1.5 |
minimum hold duration (h) | ![]() |
12.0 |
maximum hold duration (h) | ![]() |
60.0 |
vessel minimum fill ratio | ![]() |
0.3 |
maximum prep utilization | ![]() |
0.8 |
max slots | ![]() |
5 |
Support formulae:
Subject to¶
Each buffer must be prepared in a defined slot
Each slot may contain at most one vessel
Each vessel must be sufficiently large to prepare allocated buffers
Each vessel must be sufficiently small to prepare allcoated buffers
Each preapration vessel must have a utilization below the maximum utilization limit
The total duration in each hold vessel must be less than the cycle time
Buffer preparation procedures mustn’t clash with one another
Variant Problems¶
Basic¶
The “basic” variant omits the buffer preparation scheduling constraints and as such does not compute a workable schedule. It merely calculates the vessels required to maintain the specified utilization ratio at minimum cost.
Minimized Hold Time¶
The “minimized hold time” variant involves two rounds of optimization. Firstly, the “complete” problem is solved, resulting in a minimum cost.
Next, the optimum (minimized) cost is set as a constraint:
Then the problem is re-run with the following objective to be minimized:
Nomenclature¶
Symbol | Description |
---|---|
![]() |
buffers ![]() ![]() |
![]() |
(relative) cost of vessel ![]() |
![]() |
buffer maximum use duration ratio |
![]() |
vessel minimum fill ratio |
![]() |
buffer minimum use duration ratio |
![]() |
preparation slot maximum utilisation ratio |
![]() |
secondary buffer index ![]() |
![]() |
vessel size index ![]() |
![]() |
buffer index ![]() |
![]() |
slot index ![]() |
![]() |
the buffer ![]() |
![]() |
![]() ![]() |
![]() |
![]() ![]() |
![]() |
lower bound of feasible scheduling region for all buffers
![]() ![]() |
![]() |
preparation reference time for buffer ![]() |
![]() |
preparation reference time for buffer ![]() |
![]() |
upper bound of feasible scheduling region for all buffers
![]() ![]() |
![]() |
buffer ![]() |
![]() |
buffer ![]() |
![]() |
maximum feasible buffer use duration |
![]() |
maximum allowable buffer hold duration |
![]() |
minimum allowable buffer hold duration |
![]() |
duration of post-use operations in buffer hold procedures |
![]() |
duration of operations prior to receiving buffer in buffer hold procedures |
![]() |
total duration of buffer preparation procedures |
![]() |
duration of operations post transferring out buffer in buffer preparation procedures |
![]() |
duration of operations prior to transferring out buffer in buffer preparation procedures |
![]() |
duration of use of buffer ![]() |
![]() |
duration of transfers from buffer preparation vessel to buffer hold vessel |
![]() |
feasible scheduling window for buffer ![]() ![]() |
![]() |
feasible scheduling window for buffer ![]() ![]() ![]() |
![]() |
distinct buffers ![]() ![]() ![]() |
![]() |
buffer ![]() ![]() |
![]() |
a vessel of size ![]() ![]() |
![]() |
buffer ![]() |
![]() |
number of vessel sizes |
![]() |
set of vessel sizes |
![]() |
number of buffers |
![]() |
set of buffers |
![]() |
number of slots |
![]() |
set of slots |
![]() |
process cycle time (start–to–start duration) |
![]() |
volume of buffer ![]() |
![]() |
maximum working volume of vessel size ![]() |
![]() |
largest maximum working volume of available vessel sizes |
![]() |
secondary objective; sum of buffer hold times, given minimal total vessel cost |
![]() |
primary objective; total vessel cost |
![]() |
minimal total vessel cost |
untilperfect package¶
Submodules¶
untilperfect.model module¶
model.py
This module contains the definition of the buffer preparation vessel assignment problem along with classes for Parameters, Buffers and Vessels. It also contains a function for solving the problem.
-
class
untilperfect.model.
BufferPrepProblem
(parameters, buffers, vessels, solver=None)[source]¶ Bases:
object
Determines the optium selection and assignment of prep vessels.
Parameters: - parameters (untilperfect.Parameters) –
- buffers (untilperfect.Buffers) –
- vessels (untilperfect.Vessels) –
- solver (None or pulp.LpSolver, optional) –
-
basic
(do_solve=True)[source]¶ Solve basic problem (no scheduling) to minimize cost.
Parameters: do_solve (bool, optional) – If set to True (default), solves the problem upon construcion. Set this parameter to false to defer solution (useful if other constraints are to be applied before solving). Returns: If do_solve is set to True, returns problem status (see pulp.LpStatus). Return type: int
-
complete
(do_solve=True)[source]¶ Solve complete problem (includes scheduling) to minimize cost.
Parameters: do_solve (bool, optional) – If set to True (default), solves the problem upon construcion. Set this parameter to false to defer solution (useful if other constraints are to be applied before solving). Returns: If do_solve is set to True, returns problem status (see pulp.LpStatus). Return type: int
-
minimized_hold_time
()[source]¶ Solve complete problem to first minimize vessel cost, then minimize hold times subject to the minimum cost.
Returns: If do_solve is set to True, returns problem status (see pulp.LpStatus). Return type: int
-
minimized_used_volume
()[source]¶ Solve complete problem to first minimize vessel cost, then minimize used preparation volume, subject to minimum cost, finally, minimize hold times, subject to minimal cost and minimal used preparation volume.
Returns: If do_solve is set to True, returns problem status (see pulp.LpStatus). Return type: int
-
class
untilperfect.model.
Buffers
(data)[source]¶ Bases:
untilperfect.model.Data
Selection of buffers to be prepared.
Parameters: data (str or dict) – Pass either a filename string or a dict of parameters to initialize a Data class instance. The filename should be that of a valid data file (csv format).
-
class
untilperfect.model.
Data
(data)[source]¶ Bases:
object
Parent class of ‘Buffers’ and ‘Vessels’. If initialized with a ‘dict’, reads data from the ‘dict’. If initialized with a ‘str’, treats it as a filename and reads data from the file.
Parameters: data (str or dict) – Pass either a filename string or a dict of parameters to initialize a Data class instance. The filename should be that of a valid data file (csv format).
-
class
untilperfect.model.
Parameters
(data)[source]¶ Bases:
object
Problem parameters.
Parameters: data (str or dict) – Pass either a filename string or a dict of parameters to initialize a Parameters instance. The filename should be that of a valid parameters file; in ini format and with a [parameters] section.
-
class
untilperfect.model.
Vessels
(data)[source]¶ Bases:
untilperfect.model.Data
Selection of preparation vessels available for use.
Parameters: data (str or dict) – Pass either a filename string or a dict of parameters to initialize a Vessels class instance. The filename should be that of a valid data file (csv format).
-
untilperfect.model.
solve
(parameters_file='parameters.ini', buffers_file='buffers.csv', vessels_file='vessels.csv', problem_type=<function BufferPrepProblem.complete>, solver=None, plot=True, write=True, cli=False)[source]¶ Solve BufferPrepProblem.
Parameters: - parameters_file (str, optional) – Parameters filename.
- buffers_file (str, optional) – Buffers filename.
- vessels_file (str, optional) – Vessels filename.
- problem_type (optional) – Type of problem to solve.
- solver (optional) – Solver to use; see pulp.LpSolver
- plot (bool, optional) – Generate steady-state single-cylce equipent occupancy plot and save to file.
- write (bool, optional) – Write the problem to file in .lp format.
- cli (bool, optional) – Set to True to return problem status, returns problem object otherwise.
Returns: If cli=True, returns status (int, see pulp.LpStatus), if cli=False, returns pulp.LpProblem instance.
Return type: int or pulp.LpProblem
untilperfect.plots module¶
plots.py
This module contains functions to plot results.
-
untilperfect.plots.
cyclic_xranges
(start_time, duration, cycle_time)[source]¶ Where a range crosses the cycle time boundary, split into 2 ranges.
Parameters: Returns: List of operation time ranges.
Return type:
-
untilperfect.plots.
explanatory_plot
(filename='explanatory.svg')[source]¶ Plot that explains duration parameters.
-
untilperfect.plots.
label_style
(label)[source]¶ Wrapper to encode labels in latex format if this setting is active.
Parameters: label (str) – Returns: Return type: str
untilperfect.pulptools module¶
pulptools.py
This module contains a class to handle multidimensional variables in pulp.
Module contents¶
init.py