mcfadd / job_shop_schedule_problem Goto Github PK

Parallel Tabu Search and Genetic Algorithm for the Job Shop Schedule Problem with Sequence Dependent Set Up Times

License: ISC License

Python 97.81% HTML 2.19%

job-scheduler job-shop-scheduling-problem job-shop-schedulling tabu-search genetic-algorithm np-hard combinatorics combinatorial-optimization python cython

job_shop_schedule_problem's Introduction

Job Shop Schedule Problem (JSSP)

Version 2.1.0

JSSP is an optimization package for the Job Shop Schedule Problem.
JSSP has two different optimization algorithms:

Parallel Tabu Search
Genetic Algorithm

Features

Find near optimal solutions to flexible job shop schedule problems with sequence dependency setup times.
Use of Cython C extensions for fast execution of code.
Plot tabu search and/or genetic algorithm optimization using Plotly.
Create gantt charts using Plotly.
Create production schedule excel file.

For more information as well as examples, read the docs.

How to Install

After cloning this repo, change directories to where setup.py exists and run

pip install --upgrade pip
pip install -r requirements.txt
pip install .

If you get an error about python.h not being found try installing python3-dev.

To build the C-extensions (i.e compile .pyx files) without installing JSSP run

python setup.py build_ext

How to Use

After installation, JSSP can imported as a normal python module.
For examples on how to use JSSP see the jupyter notebooks in the examples folder or see the docs.

Important Note

Job-Tasks in jobTasks.csv and sequenceDependencyMatrix.csv need to be in ascending order according to (job_id, task_id).

Example

The following example minimally demonstrates how to run parallel tabu search to find a solution to the problem instance in data/given_data.

from JSSP.solver import Solver
from JSSP.data import SpreadsheetData

# initialize data
data = SpreadsheetData('data/given_data/sequenceDependencyMatrix.csv',
                       'data/given_data/machineRunSpeed.csv',
                       'data/given_data/jobTasks.csv')

# run parallel Tabu Search
solver = Solver(data)
solution = solver.tabu_search_iter(iterations=500,
                                   num_processes=4,
                                   tabu_list_size=20,
                                   neighborhood_size=250)

# create Schedule
solution.create_schedule_xlsx_file('output/Schedule.xlsx')

Flexible Job Shop

To read in a flexible job shop problem instance from a .fjs file (see data/fjs_data) do the following:

from JSSP.data import FJSData

data = FJSData('data/fjs_data/Barnes/Barnes_mt10c1.fjs')

How to Contribute

If you would like to contribute to this project please see CONTRIBUTING.md.

License

JSSP is licensed under the ISC License:

ISC License

Copyright (c) 2019, Matthew McFadden

Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted, provided that the above
copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

job_shop_schedule_problem's People

Contributors

Stargazers

Watchers

job_shop_schedule_problem's Issues

JSSP.solution._makespan

there are some problem with packets versions
i upgraded them and changed setup.py requirements but when i start the example script is says that JSSP.solution._makespan cant be found

Need some intution about sequence dependency matrix

Understand the input data

Could you explain the "pieces" parameter in class "Task"? Is this like the product quantities of a task? What it is used for in the algorithm?

Helpful Resources

This issue contains links to resources for using git version control, writing documentation in markdown, and writing code in python among other things.

Git

Markdown

Python

Diagrams

Cython

Error running parallel tabu search on Windows

After building and installing JSSP-0.1.0.win-amd64.zip (Windows build), then running TS_Example.ipynb, the following error appeared:

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-8458fe138112> in <module>
     34                                    benchmark=benchmark,
     35                                    verbose=verbose,
---> 36                                    progress_bar=progress_bar
     37                                   )
     38 

~\Anaconda3\envs\JSSP_env\lib\site-packages\JSSP\solver.py in tabu_search_time(self, runtime, num_solutions_per_process, num_processes, tabu_list_size, neighborhood_size, neighborhood_wait, probability_change_machine, reset_threshold, initial_solutions, benchmark, verbose, progress_bar)
     70                                  probability_change_machine=probability_change_machine,
     71                                  reset_threshold=reset_threshold, initial_solutions=initial_solutions,
---> 72                                  benchmark=benchmark, verbose=verbose, progress_bar=progress_bar)
     73 
     74     def tabu_search_iter(self, iterations, num_solutions_per_process=1, num_processes=4, tabu_list_size=50,

~\Anaconda3\envs\JSSP_env\lib\site-packages\JSSP\solver.py in _tabu_search(self, stopping_condition, time_condition, num_solutions_per_process, num_processes, tabu_list_size, neighborhood_size, neighborhood_wait, probability_change_machine, reset_threshold, initial_solutions, benchmark, verbose, progress_bar)
    186         # start child processes
    187         for p in processes:
--> 188             p.start()
    189             if verbose:
    190                 print(f"child TS process started. pid = {p.pid}")

~\Anaconda3\envs\JSSP_env\lib\multiprocessing\process.py in start(self)
    103                'daemonic processes are not allowed to have children'
    104         _cleanup()
--> 105         self._popen = self._Popen(self)
    106         self._sentinel = self._popen.sentinel
    107         # Avoid a refcycle if the target function holds an indirect

~\Anaconda3\envs\JSSP_env\lib\multiprocessing\context.py in _Popen(process_obj)
    221     @staticmethod
    222     def _Popen(process_obj):
--> 223         return _default_context.get_context().Process._Popen(process_obj)
    224 
    225 class DefaultContext(BaseContext):

~\Anaconda3\envs\JSSP_env\lib\multiprocessing\context.py in _Popen(process_obj)
    320         def _Popen(process_obj):
    321             from .popen_spawn_win32 import Popen
--> 322             return Popen(process_obj)
    323 
    324     class SpawnContext(BaseContext):

~\Anaconda3\envs\JSSP_env\lib\multiprocessing\popen_spawn_win32.py in __init__(self, process_obj)
     63             try:
     64                 reduction.dump(prep_data, to_child)
---> 65                 reduction.dump(process_obj, to_child)
     66             finally:
     67                 set_spawning_popen(None)

~\Anaconda3\envs\JSSP_env\lib\multiprocessing\reduction.py in dump(obj, file, protocol)
     58 def dump(obj, file, protocol=None):
     59     '''Replacement for pickle.dump() using ForkingPickler.'''
---> 60     ForkingPickler(file, protocol).dump(obj)
     61 
     62 #

~\Anaconda3\envs\JSSP_env\lib\site-packages\JSSP\solution\makespan.cp36-win_amd64.pyd in View.MemoryView._memoryviewslice.__reduce_cython__()

TypeError: no default __reduce__ due to non-trivial __cinit__

The problem has to do with pickling cython memory views. When python.multiprocessing.Process starts (i.e. is spawned), the memory views in makespan.cp36-win_amd64.pyd cannot be pickled.

Possible solutions

create a __reduce__ function that converts the memory views to a numpy arrays as described in this stackoverflow thread

TODO List

This issue is for recording a general TODO list of tasks.

Todo

Flow diagram describing the steps of our program.
Create solution class in data_set.py
Create feasible_solution_factory.py for generating feasible solutions.
Finish tabu_search.
Create another instance of the problem (i.e. jobTasks.csv, sequenceDependencyMatrix.csv, machineRunSpeed.csv) that is slightly bigger than the one currently in the data
Create a function that generates schedules with start/end times for the job-tasks on each machines given an operation list. (see code TODO comment in Solution class)
Research how to run multiple TS processes in parallel (i.e. multi-programming) and collect their results when they finish. (see multi-programming in python)
Research how/if we can use Cython to speed up runtime (i.e. # iterations of TS performed in a certain duration)