Flow shop scheduling

Last updated

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.

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.

Workshop room or building, with tools, used to repair or make goods

Beginning with the Industrial Revolution era, a workshop may be a room, rooms or building which provides both the area and tools that may be required for the manufacture or repair of manufactured goods. Workshops were the only places of production until the advent of industrialization and the development of larger factories. In the 20th and 21st century, many Western homes contain a workshop in the garage, basement, or an external shed. Home workshops typically contain a workbench, hand tools, power tools and other hardware. Along with their practical applications for repair goods or do small manufacturing runs, workshops are used to tinker and make prototypes.[1][2][3]

Machine tool using energy to perform an intended action

A machine is a mechanical structure that uses power to apply forces and control movement to perform an intended action. Machines can be driven by animals and people, by natural forces such as wind and water, and by chemical, thermal, or electrical power, and include a system of mechanisms that shape the actuator input to achieve a specific application of output forces and movement. They can also include computers and sensors that monitor performance and plan movement, often called mechanical systems.

Contents

A special type of flow shop scheduling problem is the permutation flow shop scheduling problem in which the processing order of the jobs on the resources is the same for each subsequent step of processing.

In engineering, a process is a series of interrelated tasks that, together, transform inputs into Automation system. These tasks may be carried out by people, nature or machines using various resources; an engineering process must be considered in the context of the agents carrying out the tasks and the resource attributes involved. Systems engineering normative documents and those related to Maturity Models are typically based on processes, for example, systems engineering processes of the EIA-632 and processes involved in the Capability Maturity Model Integration (CMMI) institutionalization and improvement approach. Constraints imposed on the tasks and resources required to implement them are essential for executing the tasks mentioned.

Formal definition

There are n machines and m jobs. Each job contains exactly n operations. The i-th operation of the job must be executed on the i-th machine. No machine can perform more than one operation simultaneously. For each operation of each job, execution time is specified.

Operations within one job must be performed in the specified order. The first operation gets executed on the first machine, then (as the first operation is finished) the second operation on the second machine, and so on until the n-th operation. Jobs can be executed in any order, however. Problem definition implies that this job order is exactly the same for each machine. The problem is to determine the optimal such arrangement, i.e. the one with the shortest possible total job execution makespan. [1]

Sequencing Performance Measurements (γ)

The sequencing problem can be stated as determining a sequence S such that one or several sequencing objectives are optimized.

  1. (Average)Flow time,
  2. Makespan,Cmax
  3. (Average) Tardiness,
  4. ....

detailed discussion of performance measurement can be found in Malakooti(2013).

Behnam Malakooti, is Professor of Systems Engineering of Department of Electrical Engineering and Computer Science at the Case Western Reserve University (CWRU), OH, USA. He has been affiliated with CWRU since 1982. He is a pioneer researcher in risk, Operations Management, Manufacturing Systems, multiple criteria optimization. He developed artificial neural networks for predicting decision-making behavior for out-of-sample data. He also pioneered the theory of multiple-objective optimization for solving decision making, operations and manufacturing systems, machinability of materials, Artificial Neural Networks, facility layout, and group technology and clustering.

Complexity of flow shop scheduling

As presented by Garey et al. (1976), most of extensions of the flow shop scheduling problems are NP-Hard and few of them can be solved optimally in O(nlogn), for example F2|prmu|Cmax can be solved optimally by using Johnson's Rule.

Solution methods

The proposed methods to solve flow shop scheduling problems can be classified as exact algorithm such as Branch and Bound and Heuristic algorithm such as genetic algorithm.

In computer science and operations research, exact algorithms are algorithms that always solve an optimization problem to optimality.

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.

Minimizing makespan,Cmax

F2|prmu|Cmax and F3|prmu|Cmax can be solved optimally by using Johnson's Rule (1954) but for general case there is no algorithm that guarantee the optimality of the solution.
Here is minimization using Johnson's Rule:
The flow shop contains n jobs simultaneously available at time zero and to be processed by two machines arranged in series with unlimited storage in between them. The processing time of all jobs are known with certainty. It is required to schedule n jobs on machines so as to minimize makespan. The Johnson's rule for scheduling jobs in two machine flow shop is given below: In an optimal schedule, job i precedes job j if min{p1i,p2j} < min{p1j,p2i}. Where as, p1i is the processing time of job i on machine 1 and p2i is the processing time of job i on machine 2. Similarly, p1j and p2j are processing times of job j on machine 1 and machine 2 respectively.
The steps are summarized below for Johnson's algorithms:
let, p1j=processing time of job j on machine 1
p2j=processing time of job j on machine 2
Johnson's Algorithm
Step 1:Form set1 containing all the jobs with p1j < p2j
Step 2:Form set2 containing all the jobs with p1j > p2j,the jobs with p1j=p2j may be put in either set.
Step 3: Form the sequence as follows:
(i) The job in set1 go first in the sequence and they go in increasing order of p1j(SPT)
(ii) The jobs in set2 follow in decreasing order of p2j (LPT). Ties are broken arbitrarily.
This type schedule is referred as SPT(1)-LPT(2) schedule.

Other objectives

The algorithm is optimal.

The detailed discussion of the available solution methods are provided by Malakooti (2013).

Footnotes

  1. "posh-wolf website" . Retrieved 28 December 2015.

Related Research Articles

In the bin packing problem, items of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used. In computational complexity theory, it is a combinatorial NP-hard problem. The decision problem is NP-complete.

Combinatorial optimization subset of mathematical optimization

In Operations Research, applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not tractable. It operates on the domain of those optimization problems in which the set of feasible solutions is discrete or can be reduced to discrete, and in which the goal is to find the best solution. Some common problems involving combinatorial optimization are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem.

Ant colony optimization algorithms

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial Ants stand for multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of Artificial Ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing. The burgeoning activity in this field has led to conferences dedicated solely to Artificial Ants, and to numerous commercial applications by specialized companies such as AntOptima.

In computer science, multiprocessor scheduling is an NP-hard optimization problem. The problem statement is: "Given a set J of jobs where job ji has length li and a number of processors m, what is the minimum possible time required to schedule all jobs in J on m processors such that none overlap?" The applications of this problem are numerous, but are, as suggested by the name of the problem, most strongly associated with the scheduling of computational tasks in a multiprocessor environment.

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.

A convenient notation for theoretic scheduling problems was introduced by Ronald Graham, Eugene Lawler, Jan Karel Lenstra and Alexander Rinnooy Kan in. It consists of three fields: α, β and γ.

Vehicle routing problem

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.

In operations research, Johnson's rule is a method of scheduling jobs in two work centers. Its primary objective is to find an optimal sequence of jobs to reduce makespan. It also reduces the amount of idle time between the two work centers. The method minimizes the makespan in the case of two work centers. Furthermore, the method finds the shortest makespan in the case of three work centers if additional constraints are met.

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.

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.

David Shmoys American mathematician

David Bernard Shmoys is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems.

In theoretical computer science and operations research, the open-shop scheduling problem (OSSP) is a scheduling problem in which a given set of jobs must each be processed for given amounts of time at each of a given set of workstations, in an arbitrary order, and the goal is to determine the time at which each job is to be processed at each workstation. The problem was first studied by Teofilo F. Gonzalez and Sartaj Sahni in 1976.

In operations research, the makespan of a project is the distance in time that elapses from the start of work to the end. This type of multi-mode resource constrained project scheduling problem (MRCPSP) seeks to create the shortest logical project schedule, by efficiently using project resources, adding the lowest number of additional resources as possible to achieve the minimum makespan. The term commonly appears in the context of scheduling. There is a complex project that is composed of several sub-tasks. We would like to assign tasks to workers, such that the project finishes in the shortest possible time.

In job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound W. When W = 2, it uses the minimum possible number of distinct levels, and in general it uses at most 2 − 2/W times as many levels as necessary.

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:

Truthful job scheduling is a mechanism design variant of the Job shop scheduling problem from operations research.

Scheduler is a person responsible for making a particular schedule.

Stochastic scheduling concerns scheduling problems involving random attributes, such as random processing times, random due dates, random weights, and stochastic machine breakdowns. Major applications arise in manufacturing systems, computer systems, communication systems, logistics and transportation, machine learning, etc.

References