Genetic algorithm scheduling

Last updated

The genetic algorithm is an operational research method that may be used to solve scheduling problems in production planning.

Contents

Importance of production scheduling

To be competitive, corporations must minimize inefficiencies and maximize productivity. In manufacturing, productivity is inherently linked to how well the firm can optimize the available resources, reduce waste and increase efficiency. Finding the best way to maximize efficiency in a manufacturing process can be extremely complex. Even on simple projects, there are multiple inputs, multiple steps, many constraints and limited resources. In general a resource constrained scheduling problem consists of:

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” 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 problem. This means that there are no known algorithms for finding an optimal solution in polynomial time.

Fig. 1. Precedence in scheduling Precedence.jpg
Fig. 1. Precedence in scheduling

Genetic algorithms are well suited to solving production scheduling problems, because unlike heuristic methods genetic algorithms operate on a population of solutions rather than a single solution. In production scheduling this population of solutions consists of many answers that may have different sometimes conflicting objectives. For example, in one solution we may be optimizing a production process to be completed in a minimal amount of time. In another solution we may be optimizing for a minimal amount of defects. By cranking up the speed at which we produce we may run into an increase in defects in our final product.

As we increase the number of objectives we are trying to achieve we also increase the number of constraints on the problem and similarly increase the complexity. Genetic algorithms are ideal for these types of problems where the search space is large and the number of feasible solutions is small.

Application of a genetic algorithm

Fig. 2 A. Example Schedule genome SchedulingGenome1.jpg
Fig. 2 A. Example Schedule genome

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 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 add greatly increases the search space and lowers the number of solutions that are good matches.

Bibliography

See also

Related Research Articles

Genetic algorithm competitive algorithm for searching a problem space

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on bio-inspired operators such as mutation, crossover and selection. John Holland introduced genetic algorithms in 1960 based on the concept of Darwin’s theory of evolution; afterwards, his student David E. Goldberg extended GA in 1989.

Mathematical optimization field in applied mathematics; the selection of a best element (with regard to some criterion) from some set of available alternatives

Mathematical optimization or mathematical programming is the selection of a best element from some set of available alternatives. Optimization problems of sorts arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Greedy algorithm algorithm that makes locally optimal choices in a sequence of steps with the goal of reaching a global optimum

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions. Evolution of the population then takes place after the repeated application of the above operators.

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint Programming (CP) is the field of research that specifically focuses on tackling with this kind of problems. Additionally, boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.

In genetic algorithms and evolutionary computation, crossover, also called recombination, is a genetic operator used to combine the genetic information of two parents to generate new offspring. It is one way to stochastically generate new solutions from an existing population, and analogous to the crossover that happens during sexual reproduction in biology. Solutions can also be generated by cloning an existing solution, which is analogous to asexual reproduction. Newly generated solutions are typically mutated before being added to the population.

Scheduling is the process of arranging, controlling and optimizing work and workloads in a production process or manufacturing process. Scheduling is used to allocate plant and machinery resources, plan human resources, plan production processes and purchase materials.

Single-machine scheduling or single-resource scheduling is the process of assigning a group of tasks to a single machine or resource. The tasks are arranged so that one or many performance measures may be optimized.

Vehicle routing problem combinatorial optimization problem about the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers

The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?". It generalises the well-known travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy approach called the savings algorithm.

The Shifting Bottleneck Heuristic is a procedure intended to minimize the time it takes to do work, or specifically, the makespan in a job shop. The makespan is defined as the amount of time, from start to finish, to complete a set of multi-machine jobs where machine order is pre-set for each job. Assuming that the jobs are actually competing for the same resources (machines) then there will always be one or more resources that act as a 'bottleneck' in the processing. This heuristic, or 'rule of thumb' procedure minimises the effect of the bottleneck. The Shifting Bottleneck Heuristic is intended for job shops with a finite number of jobs and a finite number of machines.

In computer science, artificial intelligence, and mathematical optimization, a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.

Guided Local Search is a metaheuristic search method. A meta-heuristic method is a method that sits on top of a local search algorithm to change its behavior.

Job shop scheduling or the job-shop problem (JSP) is an optimization problem in computer science and operations research in which jobs are assigned to resources at particular times. The most basic version is as follows: We are given n jobs J1J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan. The makespan is the total length of the schedule.

A hyper-heuristic is a heuristic search method that seeks to automate, often by the incorporation of machine learning techniques, the process of selecting, combining, generating or adapting several simpler heuristics to efficiently solve computational search problems. One of the motivations for studying hyper-heuristics is to build systems which can handle classes of problems rather than solving just one problem.

In graph theory and combinatorial optimization, a closure of a directed graph is a set of vertices with no outgoing edges. That is, the graph should have no edges that start within the closure and end outside the closure. The closure problem is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in polynomial time using a reduction to the maximum flow problem. It may be used to model various application problems of choosing an optimal subset of tasks to perform, with dependencies between pairs of tasks, one example being in open pit mining.

Flow shop scheduling problems, are a class of scheduling problems with a workshop in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of machines or with other resources 1,2,...,m in compliance with given processing orders. Especially the maintaining of a continuous flow of processing tasks is desired with a minimum of idle time and a minimum of waiting time. Flow shop scheduling is a special case of job shop scheduling where there is strict order of all operations to be performed on all jobs. Flow shop scheduling may apply as well to production facilities as to computing designs.

HeuristicLab

HeuristicLab is a software environment for heuristic and evolutionary algorithms, developed by members of the Heuristic and Evolutionary Algorithm Laboratory (HEAL) at the University of Applied Sciences Upper Austria, Campus Hagenberg. HeuristicLab has a strong focus on providing a graphical user interface so that users are not required to have comprehensive programming skills to adjust and extend the algorithms for a particular problem. In HeuristicLab algorithms are represented as operator graphs and changing or rearranging operators can be done by drag-and-drop without actually writing code. The software thereby tries to shift algorithm development capability from the software engineer to the user and practitioner. Developers can still extend the functionality on code level and can use HeuristicLab's plug-in mechanism that allows them to integrate custom algorithms, solution representations or optimization problems.

In the mathematical modeling of job shop scheduling problems, disjunctive graphs are a way of modeling a system of tasks to be scheduled and timing constraints that must be respected by the schedule. They are mixed graphs, in which vertices may be connected by both directed and undirected edges. The two types of edges represent constraints of two different types:

The nurse scheduling problem (NSP), also called the nurse rostering problem (NRP), is the operations research problem of finding an optimal way to assign nurses to shifts, typically with a set of hard constraints which all valid solutions must follow, and a set of soft constraints which define the relative quality of valid solutions. Solutions to the nurse scheduling problem can be applied to constrained scheduling problems in other fields.