Genetic algorithm scheduling: Difference between revisions

Revision as of 22:11, 6 February 2018

Latest revision as of 17:56, 5 June 2023

(9 intermediate revisions by 6 users not shown)

Line 1:

{{No footnotes|date=June 2020}}

The [[genetic algorithm]] is an [[operational research]] method that may be used to solve [[Scheduling (production processes)|scheduling]] problems in [[production planning]].

Line 6 ⟶ 7:

* A [[finite set]] of resources that can be used to complete each job

* A set of constraints that must be satisfied

** Temporal Constraints–theconstraints – the time window to complete the task

** Procedural Constraints–theconstraints – the order each task must be completed

** Resource Constraintsconstraints -– is the resource available

* A set of objectives to evaluate the scheduling performance

A typical factory floor setting is a good example of this, where it is necessary to schedule which jobs need to be completed on which machines, by which employees, in what order and at what time.

==Use of algorithms in scheduling==

In very complex problems such as scheduling there is no known way to get to a final answer, so we resort to searching for it trying to find a “good”"good" answer. Scheduling problems most often use heuristic algorithms to search for the optimal solution. Heuristic search methods suffer as the inputs become more complex and varied. This type of problem is known in [[computer science]] as an [[NP-hard|NP-Hard]] problem. This means that there are no known algorithms for finding an optimal solution in polynomial time.

[[Image:Precedence.jpg|frame|Fig. 1. Precedence in scheduling]]

Line 26 ⟶ 27:

To apply a genetic algorithm to a scheduling problem we must first represent it as a genome. One way to represent a scheduling genome is to define a sequence of tasks and the start times of those tasks relative to one another. Each task and its corresponding start time represents a gene.

A specific sequence of tasks and start times (genes) represents one genome in our population. To make sure that our genome is a [[Candidate solution|feasible solution]] we must take care that it obeys our precedence constraints. We generate an initial population using random start times within the precedence constraints. With genetic algorithms we then take this initial population and cross it, combining genomes along with a small amount of randomness (mutation). The offspring of this combination is selected based on a [[fitness function]] that includes one or many of our constraints, such as minimizing time and minimizing defects. We let this process continue either for a pre-allotted time or until we find a solution that fits our minimum criteria. Overall each successive generation will have a greater average fitness, i.e. taking less time with higher quality than the preceding generations. In scheduling problems, as with other genetic algorithm solutions, we must make sure that we do not select offspring that are infeasible, such as offspring that violate our precedence constraint. We of course may have to add further fitness values such as minimizing costs; however, each constraint that we addadded greatly increases the search space and lowers the number of solutions that are good matches.

==See also==

* [[Genetic algorithm in economics]]

* [[Job Shopshop Schedulingscheduling]]

* [[Quality control and genetic algorithms]]

==Bibliography==

* {{Citation

| last = Wall | first = M. | title = A Genetic Algorithm for Resource-Constrained Scheduling | url = http://lancet.mit.edu/~mwall/phd/thesis/thesis.pdf }}

* {{Citation

| last1 = Lim | first1 = C.

| last2 = Sim | first2 = E.

| title = Production Planning in Manufacturing/Remanufacturing Environment using Genetic Algorithm }}

| url = https://www.koreascience.or.kr/article/CFKO200536035727674.pdf}}

==See also==

* [[Job Shop Scheduling]]

* [[Quality control and genetic algorithms]]

* [[Genetic algorithm in economics]]

==External links==

*[https://web.archive.org/web/20081219135528/http://www.dna-evolutions.com/dnaappletsample.html Demo applet of a genetic algorithm solving TSPs and VRPTW problems]

{{DEFAULTSORT:Genetic Algorithm Scheduling}}

[[Category:Production and manufacturingplanning]]

[[Category:Scheduling (computing)]]

[[Category:Genetic algorithms]]

[[Category:Mathematical optimization in business]]

[[Category:Automated planning and scheduling]]