Flow-shop scheduling
Class of computational problem / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Flow shop scheduling?
Summarize this article for a 10 year old
Flow-shop scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job-scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan – the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as flow-shop scheduling, each job contains exactly m 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.
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. 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 the standard three-field notation for optimal-job-scheduling problems, the flow-shop variant is denoted by F in the first field. For example, the problem denoted by " F3||" is a 3-machines flow-shop problem with unit processing times, where the goal is to minimize the maximum completion time.