Skip to content
/ HZONE Public

Public repository for the HZONE Components data and documentation

License

Notifications You must be signed in to change notification settings

SHOP4CF/HZONE

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

LogoIRT
Logo

Shop4CF
H-Zone component

Scheduling Tasks with Zone Occupation Constraints

Table of contents

  1. About this Component
  2. Getting Started
  3. Methods explained
  4. Contributing
  5. License
  6. Contact

About this Component

In a Nutshell ..

  • Need :

    • Increase efficiency of operations in shared working areas (same zone inside huge parts or same machines in a factory).
  • Answer :

    • Schedule worker activities considering zone occupation and accessibility constraints.
  • Impact :

    • Safe and comfortable close co-activity among workers
    • Improved efficiency, reduced waiting time, reduce equipment needs
  • Potential Users:

    • Industries producing large products (Aero-spatial, Naval, Construction,etc.)
    • SMEs.

Abstract

This component aims to aid shop-floor managers while scheduling tasks that impose zone occupation constraints in the shop floor (or large product). The component is composed of two complementary parts: a Scheduler and a Simulation model.

The scheduler will search for a sequence of tasks that minimises the total make-span of the project all while taking into account zone occupation requirements, the accessibility of the zone, task precedence conditions, needed worker skills and needed resource types. The scheduler will allocate workers and resource instances to tasks with an effort to balance workload among workers. The schedule produced can then be tested and validated using the Flexsim simulation model, providing more insights and additional performance indicators such as traveled distance and the impact this might have in the global make-span.

In order to easily create application specific simulation models a template model is provided with the appropriate interphases to read input information and produce results on a ready to use dashboard of KPIs: total makespan, number of conflicts, total blocked time, (time an operation was blocked by other operation due to zone occupation or accessibility), list of conflicts, operator Gantts.

This component represents a decision support system to shop floor managers, helping them to improve production efficiency as well as working conditions (including safety) for operators though a smoother coordination of tasks.

shema1

Potential Use Cases

This component is particularly useful in industries producing very large products. In those cases, the ability to do a job and the security of the worker is dependent on the definition and respect of the workspace around the task. The aeronautical industry is a great example. Workers execute jobs in restricted zones and in parallel with other jobs by other workers. Very frequently, workers might encounter zone conflicts with other tasks causing waiting time or dangerous co-activity. E.g. two workers working in opposite sides of an airplane wall one might execute a drilling operation that might endanger the worker in the opposite side.With this component the person responsible for the operators' schedule will be able to produce schedules that guarantee workers co-activity all while trying to minimise the overall make-span and balance workload.

With this component the person responsible for the operator’s schedule will be able to validate the sequence of operations for each worker with the guarantee they will not block another colleague or at list be advised of the critical moment. This situation can also be translated to other large scale manufacturing contexts, like shipbuilding industry as well as to some SMEs manufacturing context.

Human Factors

  • Main relevant human-related issue to be solved or improved:
    • Occupation and accessibility constraints in tight areas
    • Dangerous and non-comfortable close co-activity.
  • What kind of human-technology interaction does the use-case introduce?
    • Task description in a standardized form
    • Graphical presentation of simulations and performance indicators
  • Which are the most relevant workers or workers groups that are affected by the use-case implementation?
    • Operators working in shopfloors where space is tight and operations with various specifics zone occupations could block the access to other zones/machines or mutually interfere in task executions
    • Shop floor managers in charge of planning and scheduling work orders.
  • How will the component affect workers jobs?
    • Better coordination among workers
    • Safer working conditions by avoiding risk zones.

Impact :

The component will help improve planning efficiency by reducing the waiting time of operators to access their working zones and will improve work safety by setting temporal risk zones around operations that are in execution.

Built With

The Scheduler was programmed in JAVA using the IntelliJ IDE and the following libraries:

guava jgrapht apache

The simulator template was developed using Flexsim simulation software (release 22.2.3.)

flexsim

(back to top)


Getting Started

Using Docker

The address for the the HZONE component on docker.ramp.eu is here. You can download the latest image using the pull command button.

Prepare a data folder and copy your input data scheduler file (using the template) inside. This folder will be mounted inside the docker container so you can easily retrieve the input.

To run the component using Docker use the following command :

docker run -v PATH_TO_YOU_DATA_FOLDER:/root/shop4cf_hzones/data hzone:latest NAME_OF_YOUR_INPUT_FILE.xlsx

For exemple, if you have a input file named : MyInputData.xlsx inside a data folder located at in your Documents folder on Windows. Use the following command :

docker run -v C:/Users/username/Documents/data:/root/shop4cf_hzones/data hzone:latest MyInputData.xlsx

From Source / JAR file

Prerequisites

  • Java Virtual Machine ( Java 12.0.1 or higher)
  • Windows 10 or higher (might work with older releases)
  • Microsoft Excel (.xlsx)
  • Flexsim 22.2.3. or higher (might work with older releases)

Installation

  1. Download and install a JAVA Virtual Machine from Oracle website: https://www.java.com/download/
  2. Install Microsoft Excel
  3. Download and install the free version of Flexsim Simulator available @ https://www.flexsim.com/
The free version of Flexsim is sufficient to run the models provided by this component. The template limited to TODO #of Tasks, # of obstacles,etc

Utilization Steps:

  1. Enter problem data in the input file: InputData_Scheduler.xlsx

    Sheet Data
    "Parameters" Specification of Scheduler parameters
    "Tasks" Specification of Task information
    "Workers" Specification of Worker Skills.
    "Resources" Specification of Resourcs with their types.
    "Layout" Specification of Shop-floor layout in 2D
  2. Run the Scheduler

    1. Option 1: via Docker
      TODO --> include docker details
    2. Option 2: locally
      1. Download HZone Files in local disk from Git repository
      2. Open console and go to the folder where HZones.jar is located.
      3. Execute the scheduler by typing this command:
        java -jar HZones.jar <FilePath to InputData File>
        E.g. java -jar HZones.jar "C:\Documents\HZones\data\InputData_Scheduler.xlsx"
  3. Read scheduler output in console.

  4. Experiment trying different scheduler parameters. Keep the best solution.

  5. Recover the output file produced by the scheduler. The output file will be generated @ the filepath specified in Sheet:"Parameters"

  6. Open Flexsim template model HZone_template_model. ( Make sure Flexsim software is already installed in your computer)

  7. Set up the model ( see section: Setting up a simulation)

  8. Input data into the simulation model

  9. Run the simulation

  10. Read simulation results (KPIs)

Specification of Input Data

Sheet: "Tasks"

Field Description
Task_ID Identifier of the Task
Ref Reference number of the Task
Description Text description of the task. Useful for workers.
This field is considered when comparing two task instances
Duration Time necessary to execute the task in seconds.
Worker Skills Type of skill the worker needs to execute this task.
For the moment this is limited to only one skill per task.
This should be coherent with the worker specification in Sheet:"Workers".
Resources Types of resources needed for this task.
Multiple resources can be specified using " ; ".
Predecessors Indicate the Task_ID of the tasks that need to be executed before this.
This should be specified as a hard precondition and not as a preference.
Zone(x) X coordinate of the reference point of the zone. (center?)
Zone(y) Y coordinate of the reference point of the zone. (center?)
x+ Relative x coordinate of one side of the zone with respect to Zone(x) coordinate.
x- idem in the opposite direction.
y+ Relative y coordinate of one side of the zone with respect to Zone(y) coordinate.
y- idem in the opposite direction.

Sheet: "Workers"

Field Description
Worker Id Identifier of the worker
Skills Skills the worker posses.
Multiple skills can be specified using " ; ".
WorkLoad Empty: will be filled with the output
IdleTime Empty: will be filled with the output
Utilization Rate Empty: will be filled with the output

Sheet: "Resources"

Field Description
Resource Id Identifier of the resource instance.
Type Identifier of the type of resource.
Several resource instances can be of the same type
WorkLoad Empty: will be filled with the output
IdleTime Empty: will be filled with the output
Utilization Rate Empty: will be filled with the output

Sheet: "Layout"

This sheet is defined differently then the others. The rows 3 and 4 are used to specify the dimensions of the Layout and the dimensions of the Worker aura within the layout. From row 5 and on, each row is an entry of an "obstacle" in the layout with its coordinates and dimensions. By "obstacle" we refer to any physical element occupying a space inside the layout that is fixed and that cannot be traversed by a worker. e.g. Machine, wall, etc. Multiple "obstacles" can be declared.

Field Description
EntityName Identifier of "obstacle".
X X coordinate of the reference point of the zone (center?).
Y Y coordinate of the reference point of the zone (center?).
x+ Relative x coordinate of one side of the zone with respect to Zone(x) coordinate.
x- idem but in the opposite direction.
y+ Relative y coordinate of one side of the zone with respect to Zone(y) coordinate.
y- idem but in the opposite direction.

Setting up the Scheduler ("Parameters" Sheet)

The Scheduler of this component offers several methods to search for a scheduling solution as well as some parameters so that users can tune the scheduling method that best fits to the nature of their application. Indeed, there is no single method that is best for all use cases. This is a feature this component, to provide a scheduling tool that user can adapt to the nature and needs of their application and make experimentation to fine tune the right set of parameters.

Field Description
OutputFile Name of the output file on which the schedule will be written.
The folder will be created in the "data" folder which should be in the same folder as the executable.
Method Scheduling algorithm that will be used to solve the problem.
Priority Rule Priority Rule with which the scheduling algorithm will base its search. (heuristic)
Worker Selector Rule Selector rule with which the algorithm will allocate workers to tasks when searching for a solution.
Resource Selector Rule idem as worker selector rule.
Accessibility Method Algorithm used to find a path in the shop-floor between two zones.
Time Limit This parameter is only used for the DFS_ft_EA_Method. It is the time allowed for the algorithm to search for better solutions.

Examples of parameter combinations:

  • Example1: [ Method: ParallelScheduleScheme_Method/ Priority Rule:SPT/ Worker Selector Rule: LeastWorkLoad/ Resource Selector Rule:LeastWorkLoad / Accessibility Method: A_Star]

    This combination will use the parallel scheduling scheme using the "Shortest Processing Time" priority rule as heuristic. Workers and resources will be allocated to tasks according to their workload and the layout map wil be explored using the A_Star algorithm.

  • Example2: [ Method: ParallelScheduleScheme_Method/ Priority Rule:ALL/ Worker Selector Rule: LeastWorkLoad/ Resource Selector Rule:LeastWorkLoad / Accessibility Method: A_Star]

    This combination will also use the parallel scheduling scheme but will use all the priority rules and return the solution with shortest make-span and indicate the priority rule that produced it.

  • Example3: [ Method: DFS_ft_EA_Method/ Priority Rule: / Worker Selector Rule: LeastWorkLoad/ Resource Selector Rule:LeastWorkLoad / Accessibility Method: A_Star]

    This combination will use a Depth First Search algorithm with features of Evolutionary algorithms, the user could choose a priority rule to apply, if left empty the algorithm will use the SPT rule.

Methods:

Method Description
ParallelScheduleScheme_Method Implements the Parallel Scheduling Scheme to construct a solution using a priority rule as heuristic.
DFS_ft_EA_Method Implements a Depth First Search algorithm to construct initial solutions and will consecrate the remaining allowed time to search for improvements to this solutions

A Depth First Search Algorithm to explore the solution space given by the couple: Task+Worker was also considered. However,this method was left out as it easily becomes unsolvable due to combinatorial complexity of the problem which (in most cases) will not finish the search in a reasonable time.

Priority Rules

Users have the choice of several priority rules. These rules are based the following sources of information:

  • Activity information: information about time or cost estimates of the activities determines the activity priorities.
  • Network information: information on the project network logic determines the activity priorities.
  • Resource information: information about the project resources determines the activity priorities.

Here is the list of Priority Rules implemented:

Priority Rule Description
SPT Shortest Processing Time
LPT Longest Processing Time
MIS Most Immediate Successors.
Put the activities with the most direct successors first.
MTS Most Total Successors.
Put the activities with the most direct and indirect successors first.
GRPW Greatest Rank Position Weight
The GRPW is computed as the sum of the duration of the activity and the duration of its immediate successors
GRWC Greatest Resource Work Content
WorkContent= Duration x (Num of Resources)
GCRWC Greatest Cumulative Resource Work Content
*Work content of the activity plus the sum of the work content of all immediate successors

Worker and Resource Selector Rules

The selector rule is the second criteria of the heuristic of the methods implemented in this component. The worker selector rule has a direct impact in the solution as the actions in the exploration are defined be the couple: Task + Assigned Worker

Selector Rule Description
AnyInList Random selection
LeastWorkLoad Selection of the Worker( or Resource) with less workload scheduled

We recommend using the LeastWorkLoad selector rule for workers as it will have the effect of balancing work.

The resource selector rule has a more indirect impact. The algorithms implemented do not consider exploring resource allocation as it will contribute to the combinatorial complexity. This is valid in scenarios where resources (tools) are not considered critical resources.

Accessibility Methods

Several options are available for exploring the layout map when checking if a solution satisfies accessibility constraints. In most solutions A_Star is a good choice finding solutions fast in complex mazes.

Selector Rule Description
BFS Breath First Search
DFS Depth First Search
RandomWalk Randomly Explore the 2D Map
A_Star Finds the shortest path using the "Manhattan distance" adapted for diagonal moves.
Bidirectional_A_Star Explores the map forwards from the source and backwards from the goal.

Even though, in theory, the Bidirectional_A_Star algorithm should be faster than the A_Star to find a feasible path. We do not recommend using this as it has shown slower results than A_Star. This is due to the JGraphT implementation that searches not for a feasible path ( which is sufficient for this application) but for the shortest path which requires more effort than with A_Star.

Scheduler Results

Two outputs are issued from the scheduler:

  • Console display
  • Excel output file at the address indicated in the Parameters sheet in the input data file.

Here is an example of results displayed in the console.

stpwlconsole

When launched, the scheduler will execute tests on the input data to check for coherence.
The tests performed are:

  • Test that the pool of resources satisfies the resource type requirements of tasks.
  • Test that the team of workers satisfies all skill requirements of tasks.
  • Test on precedence inconsistencies such as:
    • At least one task without dependencies
    • Test that there are no precedence loops among tasks

The results of this tests can be seen in the upper part of the console display. Then we can see the time the algorithm took to construct the schedule. Finally, a quick view of the found schedule is printed. here we can find:

  • the number of tasks in the schedule
  • the number of resources used by th schedule
  • the schedule start date
  • the schedule finish date
  • KPI information { MakeSpan, Workload, IdleTime, global utilization rate of workers}
  • the resulting worker schedules.

Results Examples

Here is a comparison of test runs using different parameter combinations for the sample data provided in the "InputData_Scheduler.xlsx" file.

Parameters Results
stp-any-params Makespan: 2549 sec / Utilisation Rate: 0.35223 / num of resources: 22 / number of workers: 7
stp-wl-params Makespan: 2549 sec / Utilisation Rate: 0.35223 / num of resources: 25 / number of workers: 7
mis-any-params Makespan: 2500 sec / Utilisation Rate: 0.35914 / num of resources: 22 / number of workers: 7
mis-wl-params Makespan: 2500 sec / Utilisation Rate: 0.35914 / num of resources: 25 / number of workers: 6
all-any-params Makespan: 2489 sec / Utilisation Rate: 0.36073 / num of resources: 22 / number of workers: 7
Best solution found with priority rule: GRPW
all-wl-params Makespan: 2489 sec / Utilisation Rate: 0.36073 / num of resources: 25 / number of workers: 7
Best solution found with priority rule: GRPW
3-mis_wl-params Makespan: 2347 sec / Utilisation Rate: 0.38255 / num of resources: 25 / number of workers: 7
3-stp_wl-params Makespan: 2335 sec / Utilisation Rate: 0.38452 / num of resources: 25 / number of workers: 7

From these results is can bee seen that the best result given with the Parallel Scheduling Scheme method was given by the GRPW priority rule. We can also observe how the DFS_ft_EA method 3 succeeds in improving the schedule result. In fact, in this case, it succeeded in finding the optimal result as 2335 seconds is the duration of the critical task sequence.

Looking at the results produced by the MIS priority rule we can observe the effect of the worker selector rule on the schedule. Even though both runs produced equivalent solutions in terms of make-span, the second run shows clearly how work in not well-balanced among workers.Another observation that can be made is that the second run does not need worker 4 and makes use of only 22 resources instead of 25.

Random Selection Least Workload Selection Rule
stp-any-params stp-wl-params
mis-wl-params mis-wl-params

This test, as it can be seen, was over-sized. The workers team is too big for the project thus the low utilization rate. To get a more realistic situation, we made a second test instance using only 3 workers for the same tasks getting a utilization rate around 80% and a make-span not so far from the critical path. The input instance is in the InputData_Scheduler2.xlsx.
NOTE: a different distribution of skills might produce better results.

Parameters Results
3-stp_wl-params_3Workers Makespan: 2608 sec / Utilisation Rate: 0.80329 / num of resources: 25 / number of workers: 3
3-stp_wl-params_3Workers Makespan: 2545 sec / Utilisation Rate: 0.8231 / num of resources: 25 / number of workers: 3

Opening the simulation model

First of all open the model template (HZone_template_model)
You should see de 3D view of the model as this :

ModelView

You can see :

  • 10 operators: they have been created and pre-programed. They are the team which will operate the tasks you will ask them.
  • The purple frame is the border of the zone where the operators will move.

Setting up a simulation

Le model uses data from the scheduler Excel doc output. The data is stored in different tables in the model. You have to copy data from the Excel to the model. To help you navigating in the model a dashboard have been created. If it doesn't pop up at model opening you can access it form the dashboard menu of Flexsim :

DashboardSetup

DashboardSetup2

The dashboard have 5 options and 1 editable text field:

  • Layout Description : correspond to the Layout sheet of the scheduler output. This section describe the working environment (size, obstacles).
  • Tasks Description : correspond ton the Task Plan sheet of the scheduler output. You find here the description of all the tasks the operator will execute.
  • Workers Description : if you want to give specific names to the operators you juste have to fill this table up.
  • Model View : quick access to the 3D view of the model.
  • Clear Tables : it will reset all data if you want to use the model with a different set of data (if your new data contain fewer lines some old data could remain).
  • Set Size : in this filed you have to enter the step you choose in your data. By default, the model is set in meter. If you want a smaller grid 50cm for example enter 0.5. Be careful to use this size in your data (a 1m x 1m zone will be declared as a 2 x 2 zone).
22-44-1 22-44-05 44-88-05
a 22 by 44 grid with a step of 1 a 22 by 44 grid with a step of 0.5 a 44 by 88 grid with a step of 0.5

Input data into model

You just have to copy and paste the data from the Excel sheet to the Flexsim table (same names in Excel sheet and Flexsim table). Just be sure to only select the data and not the headers and to paste it in the first cell of the first row of the table.

DataImport

Once the Tasks and Layout data is imported, the model is ready to go.

Running a simulation

To run the model click on the play button :

Run

When you click on it the model will construct the layout and send you a confirmation.
Click OK, now you can see the environment you described to the scheduler.

Run1

Click another time on Run and the model will start.

Run2

You can adjust the simulation speed with the scrollbar.

Speed

The number displayed is the number of seconds which the simulation progress each second in real time. *NOTE : if you have changed the operator's names the first time you have to run the model once and then reset and restart to see the change.*

Reading simulation results

Once all the tasks have been executed the model will stop by itself.
You can access results in a dashboard :

KPI

In this dashboard you can consult different indicators :

KPI2

The state indicator : it shows the proportion of the different states of the operators. Flying over your mous will display the the percentage for heach part of the graph. The different states are :

  • Idle : This represents the waiting time when the operator have no remaining task. This is available time for operators.
  • Busy : This is the portion of the simulation time when the operator was executing his work.
  • Blocked : This part is the time during the operator could do a task but the zone where he was supposed to work is occupied or inaccessible. During this time operator is not considered available because he has to be ready at the moment his zone will be released.
  • Travel empty : This is the travelling time to go to the different tasks' location.
  • Allocated idle : This portion represent the waiting time of the operators where they have remaining tasks but the predecessors conditions are not fullfilled. During this time the operator is waiting to work. As when he his blocked he has to be ready to work when the conditions will be fullfilled.

Travel Distance : with this indicator you can check if the travel distance is well-balanced between operators.

The Gantt Chart : you can visualize the tasks sequence during simulation time.

*NOTE : Worker behaviour was programmed to reflect the way workers operate in a shop floor. In the absence of a supervisory system coordinating all tasks, workers will execute tasks as soon as the task requirements are satisfied with no regard of the global schedule. This behaviour does not match the one expected by the scheduler but reflects the way workers operate. In case of task delays, workers will often execute tasks in a different but valid order that might later block other tasks and impact on the total make-span. Further work will include the option to choose between this behaviour and one strictly respecting the global schedule.

(back to top)


Methods explained

Scheduling problem

This component is intended to solve the Resource Constraint Scheduling Project Scheduling Problem (RCPSP) with additional constraints on zone occupation and accessibility. The RCPSP considers resources of limited availability and tasks with known durations and linked by precedence conditions. To this problem with add the consideration of constraints related to zone occupation and the accessibility of the zone given the zone occupation at the start time of each task. The problem consists then in finding a schedule of minimal make-span by assigning workers and resources to tasks as well as a start time to each task such that all precedence constraints are respected and there are no conflicts in zone occupation.

This problem is NP-hard and can easily produce a large combinatorial complexity. For example, a problem with 15 tasks and 3 workers solution space could reach up to: (num of Tasks)!*(num of workers) = 15!*3= 3,923 billion possibilities.

Method 1 : Parallel Schedule Scheme

This method uses a parallel schedule generation scheme, this method will increment in an iterative manner a time window and will add tasks to the schedule that are eligible based on the satisfaction of their constraints.

Take for example the following project schedule and precedence graph fo a project where the resource pool is limited to 5. For example at time t=8, tasks 1 and 2 are already scheduled. Due to precedence constraints, at this point tasks 3,4 and 5 are eligible to be scheduled. Using a SPT priority rule, the algorithm will first add task 4 then 5 and task 3 will no longer be eligible due to resource conflicts As no other task is eligible at time t=8 the algorithm increments the time window to t=12, that is the soonest event in the schedule, where tasks 3 and 7 become eligible.

precedencegraph
Example:Task Precedence Graph

parallelscheme
Example: Project Schedule using the parallel schedule generation scheme with priority rules.

The algorithm implemented in this component uses the same mechanism. The following figure illustrates its logic.

ps_flowchart
Algorithm: Parallel Schedule Scheme Method.

This method is a good option when the user wants quickly a feasible solution to large and complex problems. Due to this, it is specially suitable for rescheduling when fast response times are needed. Most of the time, and for most problems, this method will provide satisfying solutions, however it does not make any effort to try to improve the solutions. Indeed, there might be much better solutions to the problem in the solution space.

Method 2 : DFS with features of Evolutionary Algorithms

This method was designed to tackle the problems of method 1 and 2, that is: improve the solution in a limited time all while trying to avoid local minima. To do this, the algorithm integrates features of meta-heuristics such as the Evolutionary Algorithms that provide a strategy to explore large solution spaces. These principals consist on creating an initial population of solutions from which child solutions will be produced taking some characteristics of their parents and exploring modifications to them. Among the new population of solutions created only a set of the fittest solutions will remain to produce new children.
this process continues iteratively until a stopping condition ( in this case time) is reached and the best solution is then returned.

The performance of the algorithm depends on many factors:

  • The quality of the initial solutions
  • The strategies for creating child solutions
  • The strategies to orient exploration and avoid local minima
  • The speed to evaluate, compare and create new solutions (the algorithm strength relies on its ability to explore many mutations to allow evolution)

The algorithm, as defined by the strategies described here below, is designed to initially privilege the exploration of a wider solution space far from the vicinity of initial solutions. Then, as time goes by, the algorithm will tend to explore around the vicinity fo the best solutions (which will represent several local minima) to try to refine the solutions.

DFS_EA_flowchart
DFS_ft_EA algorithm

Computing initial solutions

The initial solutions are produced using the DFS algorithm with a heuristic based on a priority rule and the worker selector rule. At each scheduling point the algorithm will compute the eligible actions described y the choice of task and worker. The set if eligible actions is then all possible combinations of enabled tasks by precedence and zone occupation and available skilled workers. The heuristic will evaluate actions according to the rank of the task and the worker with respect to other tasks and workers. This is different to the Parallel Scheduling Scheme where workers where assigned only after the task was selected by the priority rule.

The algorithm produces 2-3 initial solutions using 1: the specified priority rule; 2: SPT rule; 3: MIS rule. This will quickly provide feasible solutions.

initialSolution
Illustration: Initial Solution.

Generating new populations

Selection of branches

To generate a new population the algorithm selects intermediate nodes from the actual population ( current best solutions). Each solution on the population produces 2 childs. For this , all intermediate nodes of the solution are evaluated based on a fitness function:

branchfitness
probability
unexploredaction

Initially the algorithm will privilege the exploration of branches where with more unexplored actions. Then, as time approaches to its deadline, the algorithm will select branches where only a few options where available.

childSolutions

Branch exploration (selection of actions)

Once branches are selected, solutions must be constructed out of them to create new solutions.
These solutions are explored based also on a probability function:

probability
Probability of selecting only among unexplored actions

Else, selection will consider both: unexplored and explored solutions. Then, to select an action, all actions considered will be ranked according to the priority and worker selector rules. An action is then selected according to a probability rule based on their ranking.

The intention of this rule is to initially privilege the exploration of unexplored actions to widen the explored solution space. The heuristic combining priority rule and worker selector rule will orient the exploration. As time approaches its deadline, explored solutions will be more considered for selection, the use of probability function avoid to repetitively explore the same solutions by allowing some randomness to the exploration.

probabilityActionSelection sn
Probability of selection with ranking i.

Where:

  • a1= 1
  • n = an =number of actions
  • i = ranking of the action according to heuristic.

Selection of new population

After exploring all selected branches and producing a new generation of solutions, only 10 of these "survive" for the next generation. For every generation the best first two solutions (i.e. those with shorter make-span) are selected then eight other solutions are selected according to the probability function as a function fo their rank. This is the same function used for action selection.

probabilityActionSelection sn
Probability of selection with ranking i.

This function will not lose the best solution found and will allow less fit solutions to survive that might be in the vicinity of, and therefore, lead to fitter results.

(back to top)


Contributing

TODO .

(back to top)

License

The Software is currently Licence under the Apache2.0 License Agreement with ownership of the copyright given to IRT Jules Verne.

Contact

Commercial Contact

Murielle MANIN
Chef de Projets de Recherche. R&T Project Manager
+33 2 55 11 21 45 ❘ +33 7 57 40 97 13 [email protected]
1 Mail des 20 000 Lieues, 44340 Bouguenais, France

R&T Team Manager

Sébastien RUBRECHT, PhD
Responsable d'équipe de Recherche. R&T Team Manager
Robotique et Cobotique. Robotics & Cobotics
+33 2 55 11 21 75 ❘ +33 7 85 39 21 71 [email protected]
1 Mail des 20 000 Lieues, 44340 Bouguenais, France

Development Engineers

Francisco GAMBOA, PhD
Ingénieur R&D. R&T Engineer
Robotique et Cobotique. Robotics & Cobotics
+33 2 55 11 21 09 ❘ +33 6 31 85 70 20 [email protected]
1 Mail des 20 000 Lieues, 44340 Bouguenais, France

Raphael CASTAGNA
Ingénieur R&D. R&T Engineer
Robotique et Cobotique. Robotics & Cobotics
+33 2 55 11 20 87 ❘ +33 7 57 40 39 62 [email protected]
1 Mail des 20 000 Lieues, 44340 Bouguenais, France

Integration Engineer

Ludovic DELVAL
Ingénieur R&D. R&T Engineer
Robotique et Cobotique. Robotics & Cobotics
+33 2 55 11 20 99 [email protected]
1 Mail des 20 000 Lieues, 44340 Bouguenais, France

(back to top)

About

Public repository for the HZONE Components data and documentation

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages