Flow-shop scheduling: Difference between revisions

Revision as of 15:31, 5 February 2022

Latest revision as of 06:52, 19 April 2025

(5 intermediate revisions by 5 users not shown)

Line 1:

{{Short description|Class of computational problem}}

[[File:Flow Shop Ordonnancement.JPEG|thumb|Flow Shop Ordonnancement]]

'''Flow-shop scheduling''' is an [[optimization problem]] in [[computer science]] and [[Operations Research|operations research]]. It is a variant of [[optimal job scheduling]]. In a general job-scheduling problem, we are given ''n'' jobs ''J''₁, ''J''₂, ..., ''J_n'' 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.

Line 7 ⟶ 8:

==Formal definition==

There are ''nm'' machines and ''mn'' jobs. 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.

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 ''nm''-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.

==Sequencing performance measurements (γ)==

Line 20 ⟶ 21:

==Complexity of flow-shop scheduling==

As presented by Garey et al. (1976),<ref name=Garey>{{cite journal

As presented by Garey et al. (1976),<ref name=Garey>Garey, M. R., Johnson, D. S., & Sethi, R. (1976). [https://pubsonline.informs.org/doi/abs/10.1287/moor.1.2.117 The complexity of flowshop and jobshop scheduling].{{closed access}} Mathematics of operations research, 1(2), 117–129.</ref> 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|C_max can be solved optimally by using [[Johnson's Rule]].<ref name=Johnson>Johnson, S. M. (1954). [https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800010110 Optimal two-and three-stage production schedules with setup times included].{{closed access}} Naval research logistics quarterly, 1(1), 61–68.</ref>

| last1=Garey | first1=M. R.

| last2=Johnson | first2=D. S.

| last3=Sethi | first3=Ravi

| date=1976

| title=The complexity of flowshop and jobshop scheduling

| journal=[[Mathematics of Operations Research]]

| volume=1

| issue=2

| pages=117–129

| doi=10.1287/moor.1.2.117}}</ref> 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|C_max can be solved optimally by using [[Johnson's Rule]].<ref name=Johnson>{{cite journal

| last1=Johnson | first1=S. M.

| date=1954

| title=Optimal two-and three-stage production schedules with setup times included

| journal=Naval Research Logistics Quarterly

| volume=1

| issue=1

| pages=61–68

| doi=10.1002/nav.3800010110}}</ref>

Taillard provides substantial benchmark problems for scheduling flow shops, open shops, and job shops.<ref name=Taillard>{{cite journal | doi=10.1016/0377-2217(93)90182-M | author=Taillard, E. | title=Benchmarks for basic scheduling problems | journal=European Journal of Operational Research |date=January 1993 | volume=64 | pages=278–285 | issue=2 | url=http://ideas.repec.org/a/eee/ejores/v64y1993i2p278-285.html }}</ref>

Line 62 ⟶ 81:

[[Category:Optimal scheduling]]

[[Category:Workflow technology]]

[[Category:Engineering management]]