Flow Shop Scheduling

Flow shop scheduling is a process optimization technique used in manufacturing and computational settings to manage the flow of jobs through a series of machines. The approach focuses on determining the best sequence for job operations to minimize idle time and ensure an efficient workflow. Each job consists of multiple operations performed on different machines in a predetermined order, where no machine can handle more than one operation simultaneously. The aim is to reduce the overall completion time, known as the "makespan," which is a critical metric in production efficiency.

The complexity of flow shop scheduling arises from various factors, including differing operation times for machines and precedence constraints that may dictate the order of jobs. Solutions often rely on permutation calculations and heuristics, such as Johnson's Rule, which suggests prioritizing jobs based on their processing times. While achieving a perfect solution is challenging due to the NP-hard nature of the problem, numerous strategies exist to find satisfactory scheduling arrangements. Ultimately, effective flow shop scheduling balances mathematical models with the practical realities of machine performance and operational constraints to enhance productivity in diverse industries.

Published in: 2021

By:

Subject Terms

Flow Shop Scheduling

Abstract

For a manufacturing or computer-based company to maximize their profits, it is essential to plan for optimal processing times. Flow shop scheduling iteratively selects the best sequence of work flow for a job using a NP-hard mathematical approach. For a machine sequence where similarly timed machines are involved, the timing issue is easily solved, but when the machines are timed differently for different operations, the calculations can be complex. There are no perfect solutions to optimize job processing times, but finding a balance between sequence optimization and resources to do the job are key.

Overview

Flow shop scheduling refers to the control of the flow of jobs in a series of machines. The scheduling aspect of the problem is solved using permutation calculations that establish the sequence of the job flow through a machine queue. The desired result is to produce an undisrupted flow with minimum idle or waiting time, to ensure efficiency. It is generally used when the order of the job sequence is of importance. This type of scheduling can be used in both manufacturing facilities as well as in computer processes.

The problem set up for flow shop scheduling is that there are n machines and m jobs. Each job has n operations (finite). The i-th operation of a job must be sequentially performed until it reaches the i-th machine in the sequence. There is a restriction that no machine can execute more than one operation at a time. It is assumed that there is no limit to storage or buffer capacities with successive machines. The execution time is specified for each operation of each job and the order of each job is specified. The order of each operation is executed so that the first operation in a job is executed on the first machine, then the second is executed on the second machine, until the n-th operation is completed. The order of each job can be executed in more than one way. This is an example of a permutation flow shop problem.

One of the chief issues with flow shop scheduling is to attain the optimal order to execute the job operations. The ultimate goal for the job is to reduce the time it takes to complete a job, or the "makespan" of the job. This is a complex work problem that involves several methods to achieve the optimal order. Issues that can arise with a given flow shop scheduling problem include, precedence constraints for certain operations (based on the product), set up times that differ for each job, and jobs that have due and release times.

If the objective is to minimize makespan scheduling for identical machines, then a given set of n jobs with processing times pi ϵ Z+, i=1, ……, n, and m is a positive integer. Included in this set of calculations is size of objects to be packed in bins, determining the number of bins of a specified size that need to be packed, and determining the time interval for which the makespan is being considered. This type of problem is constructed on the basis that bin packing is NP-hard complexity for decision problems. Bin packing is calculated based on a fixed number of object sizes. The core algorithm follows five steps which includes: (1) discarding the small objects of less than ϵt sizes, (2) rounding the remaining objects, (3) detecting optimal solution of time, (4) increasing both bin sizes and objects to original size (promotes a valid packing), and (5) filling bins with small objects to arrive at total number of bins required.

If the objective is to minimize makespan scheduling for unrelated machines, then a given set J of n jobs and a set of M of m machines. The processing time for one job then, is j ϵJ on machine i ϵ is pij ϵ Z+. The calculation for unrelated machines involves five steps, which include: (1) execute a binary search within the interval [α/m, α], to find the smallest value of T (time); (2) identify an extreme point solution; (3) assign jobs to machines using the integral; (4) build a fractional support graph and identify the appropriate point; and (5) assign jobs based on the matching point in the graph.

Further Insights

Both types of problems can be optimally solved by employing Johnson's Rule, prioritizing the shortest activity job for each batch of jobs. In a paper published in 1954, Johnson outlined his method for optimizing the makespan for jobs at two work centers. The concept behind the optimization of time for two work centers can be applied to the optimization of time for unrelated machines that have different operation times for a task in a job. Essentially, the method has a few assumptions that must be met before applying to the problem of job times, which include: (1) time for each job must be constant, (2) job times are mutually exclusive to the job sequence, (3) all jobs must move through the first work center before moving through the second work center, and (4) all jobs are prioritized equally. to execute the method, each job and their work times taken at each work center must be populated. The job with the shortest activity time is identified. If the job with the shortest activity time is scheduled at the first work center, then that job is placed first in the sequence, but if it is at another work center, the job will be placed last. The next shortest activity job is then selected and subjected to the same process until the longest job in the sequence remains. When the second work center is activated for the job sequence has a significant idle time, the job can be split to minimize the makespan. These methods can be applied to both machines and computing algorithms.

Discourse

Since the Johnson Rule was implemented, a substantial body of research has emerged to address specific issues when attempting to minimize makespan. Namely, many mathematical proofs have been offered to address NP-hardness of specific job processing times. In a paper by Bachman and Janiak (2004), the authors detailed their proof of NP-hardness in total completion time and total weighted completion times. The goal was to demonstrate NP-hardness in two different models of job processing times, using the reductions from the 3-Partition Problem. They also demonstrated that makespan minimization problems with job ready times was equal to the maximum lateness minimization problem.

Though it is generally agreed that including setup times in processing times is reasonable for some scheduling problems (i.e., when set up times are minimal compared with processing times), there are times when it is not possible. This is the case when considering chemical, pharmaceutical, printing, semiconductor, and metal processing industries. Performance measures of makespan can be improved by separating setup times from processing times. This translates into leveraging the idle time of the first machine by setting the time for the job on the second machine to be performed before the conclusion of the job of the first machine (idle machine).

Another problem with calculating optimal processing times is in the assumption that job processing times are known as fixed variables in advance. Random variation in processing times must be considered when solving the processing time problem. Some job processing times follow specific probability distributions, such as exponentially distributed processing times. However, in some environments it is hard to ascertain the exact probability distributions when modeled using random variables. Assuming a particular probability distribution is usually not the best method of solving the problem. Upper and lower bounds on processing times can be determined when there are unknown random variables associated with processing times.

For all problems attempting to optimize job processing times, there is no perfect solution. All methods covered here are heuristic in nature, in that they often are not perfect solutions but meet immediate needs to get the processes into production. Optimization for the processes are usually met in subsequent problem-solving meetings. These meetings include information that underlines the issues with job processes from a timing perspective (those that involve mathematical solutions) and any problems that arise from machine/program performance, customer issues with products, and loss of profits due to any of the reasons mentioned. In other words, no job optimization process occurs in a closed system. It always entails the involvement of more than one issue affecting the overall problem and it requires a multidisciplinary approach to solving the problem.

If it is determined that loss of profit is due to machine/program performances, these issues must be addressed before any clarity can be achieved with improvement in job performance timing. These issues are interdependent because there is often a trade-off for optimizing job performance times when upgrades or repairs are necessary but not financially feasible for a company. This translates into sub-optimal job performance times in non-ideal situations. The heuristic methods for optimizing the job performance time are selected with the idea that even in imperfect production conditions it is possible to maximize the makespan of a job.

In summary, flow shop scheduling is a method for calculating optimal job processing times for machines or computer programs in the setting of similar or dissimilar operating machines. The goal is to minimize makespan, or the time needed to complete one job with a set of machines. The original method for optimizing the job processing time was using Johnson's Rule, which identifies the shortest activity job or operation in a job sequence or batch and plans the sequence to always have the next shortest activity job move next in line. The complexity of this process is seen when the sequence of machines required to do the job have different operating times. While many different approaches have been taken to address how best to optimize the timing of a job processing sequence, other factors must be weighed, such as machines operating at optimum levels, to ensure that the mathematical approach will be effective. Otherwise there is a trade-off in the effectiveness of optimizing job processing times.

Terms & Concepts

Heuristic: A practical approach to solving a problem or learning that is not necessarily optimal but helps to meet immediate needs.

Johnson's Rule: A method of scheduling jobs in two work centers to reduce makespan.

Makespan: The total amount of time it takes to complete all jobs.

NP-Complete: Any non-deterministic polynomial (NP) set of problems that can be reduced to polynomial time. A set of NP problems is said to be complete if it forms at the intersection of NP and NP-hard problems.

NP-Hard: A concept in computational complexity theory that defines a class of problems to be as hard as the hardest problems in non-deterministic polynomial time hardness.

Permutation: A way, especially one of several possible variations, in which a set or number of tings can be ordered or arranged.

Position-dependent Processing Times: A job processing problem where the positioning of the machines or points in a computing algorithm affects the outcome of job processing time.

Probability Distribution: The pattern that a set of data takes when frequencies are plotted as a histogram. The numbers along the x-axis of the graph represent the individual units that are repeated in the data set, whereas the y-axis indicates the number of times the unit appears within the dataset. Some common distributions include, Gaussian (normal), Binomial, and Poisson.

Random Variation: The concept in statistics that states that in an uncontrolled environment any variable that can be evaluated occurs randomly (as long as it is not known that the variable is dependent upon another variable). The variation of a random variable is the behavior of the variable within a specific environment. This behavior can be plotted on a graph to show a pattern of behavior within a specific time period. This variation pattern is used to predict future behavior or plan for studies where a certain sample size is needed for statistical power.

Bibliography

Bachman, A., and Janiak, A. (2004). Scheduling jobs with position dependent processing times. Journal of Operational Research Society, 55(3), 257–264. Retrieved January 16, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=12871852&site=ehost-live

Bai, D. (2015). Asymptotic analysis of online algorithms and improved scheme for the flow shop scheduling problem with release dates. International Journal of Systems Science, 46(11), 1994–2005. Retrieved January 16, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=102272333&site=ehost-live

Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2), 117–129. Retrieved January 16, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=9276950&site=ehost-live

Gonzalez T, Sahni S. (1978). Flowshop and jobshop schedules: Complexity and approximation. Operations Research, 26(1), 36. Retrieved January 16, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=6668088&site=ehost-live

Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61–68.

Kalczynski, P. J., & Kamburowski, J. (2004). Generalization of Johnson's and Talwar's scheduling rules in two-machine stochastic flow. Journal of the Operational Research Society, 55(12), 1358–1362. Retrieved January 16, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=15325060&site=ehost-live

Liu, W., & Cao, J. (1995). Stochastic scheduling on a single machine subject to multiple breakdown according to different probabilities. Operations Research Letters, 18(2), 81–91.

Rad, S. F., Ruiz, R., & Boroojerdian, N. (2009). New high performing heuristics for minimizing makespan in permutation flowshops. Omega, 37(2), 331–345. Retrieved January 16, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=32983449&site=ehost-live

Shen, J., & Zhu, Y. (2017). Uncertain flexible flow shop scheduling problem subject to breakdowns. Journal of Intelligent & Fuzzy Systems, 32(1), 207–214. Retrieved January 16, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=120827891&site=ehost-live

Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64 (2), 278–285. Retrieved January 16, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=7904293&site=ehost-live

Vickson, R. G., Alfredsson, B. E. (1991) Two- and three-machine flow shop scheduling problems with equal sized transfer batches. International Journal of Production Research, 30(7), 1551–1574. Retrieved January 16, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=5782092&site=ehost-live

Ying, K. C., Lin, S. W. (2013). A high-performing constructive heuristic for minimizing makespan in permutation flowshops. Journal of Industrial and Production Engineering, 30(6), 355–362. Retrieved January 16, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=32983449&site=ehost-live

Flow Shop Scheduling

On this Page

Subject Terms

Flow Shop Scheduling

Abstract

Overview

Further Insights

Discourse

Terms & Concepts

Bibliography

Suggested Reading