Scheduler for Adaptive Manufacturing Processes Optimization

affiliation
package
license
support
mirror

SAMPO is an open-source framework for adaptive manufacturing processes scheduling. This framework is distributed under the 3-Clause BSD license.

It provides toolbox for generating schedules of manufacturing process under the constraints imposed by the subject area. The core of SAMPO is based on the combination of meta-heuristic, genetic and multi-agent algorithms. Taking as input the task graph with tasks connections and resource constraints, as well as the optimization metric, the scheduler builds the optimal tasks sequence and resources assignment according to the given metric.

Installation

SAMPO package is available via PyPI:

$ pip install sampo

SAMPO Features

The following algorithms for projects sheduling are implemented:

• Heuristic approaches

  • Topological - heuristic algorithm based in toposort of WorkGraph
  • HEFT (heterogeneous earliest finish time) and HEFTBetween - heuristic algorithms based on critical path heuristic

• Genetic evolutional algorithm that uses the idea of evolution and applies mutation, crossover and selection operators to form optimal solutions

Heuristic approaches are also used for initialization in a genetic algorithm to produce better solutions

Advantages of the framework:

• Pipeline structure with easy customization options for additional constraints
• Ability to handle complex projects with a large number of tasks (2-10 thousand)
• Flexible multi-criteria optimization (time, resources and cost, optimization to project deadline) and construction of a set of Pareto-optimal plans
• Ability to use within a modular structure with an Input Data Parser and a Time and Resource Estimation Model to take into account the specifics of the task and subject area

Advanced options:

• Multi-agent modeling block for an effective combining different scheduling algorithms
• Module for generating synthetic graphs with a given structure

How to Use

To use the API, follow these steps:

1. Input data preparation

To use SAMPO for the schedule generation you need to prepare:

• WorkGraph object with the works information representation, including volumes of the works and connections between them

• list of Contractor objects with the information about available resources types and volumes.

  1.1. Loading WorkGraph from file

  wg = WorkGraph.load(my_folder_name, my_file_name)

  1.2. Generating synthetic WorkGraph

  from sampo.generator import SimpleSynthetic
  
  # SimpleSynthetic object used for the simple work graph structure generation
  ss = SimpleSynthetic()
  
  # simple graph
  # should generate general (average) type of graph with 10 clusters from 100 to 200 vertices each
  wg = ss.work_graph(mode=SyntheticGraphType.General,
                     cluster_counts=10,
                     bottom_border=100,
                     top_border=200)
  
  # complex graph
  # should generate general (average) type of graph with 300 unique works, 100 resources and 2000 vertices
  wg = ss.advanced_work_graph(works_count_top_border=2000,
                              uniq_works=300,
                              uniq_resources=100)

  1.3. Contractors generation

  Manual Contractor list generation:

  contractors = [Contractor(id="OOO Berezka", workers=[Worker(id='0', kind='general', count=100)])]

2. Scheduling process

   2.1. Scheduler constructing

   There are 4 classes of schedulers available in SAMPO:

   • HEFTScheduler
   • HEFTBetweenScheduler
   • TopologicalScheduler
   • GeneticScheduler

   Each of them has various hyper-parameters to fit. They should be passed when scheduler object created.

   from sampo.scheduler.heft import HEFTScheduler
   
   scheduler = HEFTScheduler()

   from sampo.scheduler.genetic import GeneticScheduler
   
   scheduler = GeneticScheduler(mutate_order=0.05,
                                mutate_resources=0.05)

   2.2. Schedule generation

   schedule = scheduler.schedule(wg, contractors)[0]

3. Pipeline structure

When data was prepared and scheduler built, you should use scheduling pipeline to control the scheduling process:

from sampo.pipeline import SchedulingPipeline

schedule = SchedulingPipeline.create() \
      .wg(wg) \
      .contractors(contractors) \
      .schedule(HEFTScheduler()) \
      .finish()[0]

Supported by

The study is supported by the Research Center Strong Artificial Intelligence in Industry of ITMO University as part of the plan of the center's program: Development and testing of an experimental prototype of a library of strong AI algorithms in terms of adaptive optimization of production processes based on intelligent technologies, multi-criteria evolutionary schemes and a multi-agent simulation environment.