article

Flowshop and Jobshop Schedules: Complexity and Approximation

Authors:

Teofilo Gonzalez,

Sartaj SahniAuthors Info & Claims

Operations Research, Volume 26, Issue 1

Pages 36 - 52

https://doi.org/10.1287/opre.26.1.36

Published: 01 February 1978 Publication History

Abstract

We show that finding minimum finish time preemptive and non-preemptive schedules for flow shops and job shops is NP-complete. Bounds on the performance of various heuristics to generate reasonably good schedules are also obtained.

References

[1]

P. BRUCKER, J. K. LENSTRA, AND A. H. G. RINNOOY KAN, "Complexity of Machine Scheduling Problems," Mathematisch Centrum, Amsterdam, Technical Report BW 43/75, April 1975.

Google Scholar

[2]

E. G. COFFMAN, JR., Computer and Job Shop Scheduling Theory, John Wiley & Sons, New York, 1976.

Google Scholar

[3]

R. W. CONWAY, W. L. MAXWELL, AND L. W. MILLER, Theory of Scheduling, Addison-Wesley, Reading, Mass., 1967.

Google Scholar

[4]

M. R. GAREY, D. S. JOHNSON, AND R. SETHI, "Complexity of Flow Shop and Job Shop Scheduling," Math. Opns. Res. 1, 117-129 (1976).

Digital Library

Google Scholar

[5]

T. GONZALEZ, O. H. IBARRA, AND S. SAHNI, "Bounds for LPT Schedules on Uniform Processors," SIAM J. Computing, 5, 155-166 (1977).

Crossref

Google Scholar

[6]

T. GONZALEZ AND S. SAHNI, "Open Shop Scheduling to Minimize Finish Time," J. Assoc. Comput. Machinery, 23, 665-679 (1976).

Digital Library

Google Scholar

[7]

R. L. GRAHAM, "Bounds on Multiprocessing Timing Anomalies," SIAM J. Appl. Math. 17, 416-429 (1969).

Crossref

Google Scholar

[8]

J. R. JACKSON, "An Extension of Johnson's Results on Job Lot Scheduling," Naval Res. Logist. Quart. 3, 201-203 (1956).

Crossref

Google Scholar

[9]

R. M. KARP, "Reducibility among Combinatorial Problems," in Complexity of Computer Computation, pp. 85-104, R. E. Miller and J. W. Thatcher (Eds.), Plenum Press, New York, 1972.

Google Scholar

[10]

R. M. KARP, "On the Computational Complexity of Combinatorial Problems," Networks 5, 45-68 (1975).

Digital Library

Google Scholar

[11]

S. SAHNI, "Computationally Related Problems," SIAM J. Computing 3, 262-279 (1974).

Crossref

Google Scholar

Cited By

View all

Jiang XLee KPinedo M(2024)Bicriteria two-machine flowshop scheduling: approximation algorithms and their limitsJournal of Scheduling10.1007/s10951-023-00781-x27:1(61-86)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10951-023-00781-x
Wang ZLiao W(2024)Smart scheduling of dynamic job shop based on discrete event simulation and deep reinforcement learningJournal of Intelligent Manufacturing10.1007/s10845-023-02161-w35:6(2593-2610)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s10845-023-02161-w
Yang DQian BZhang ZHu RLi K(2024)A Hyper-Heuristic Algorithm with Q-Learning for Distributed Flow Shop-Vehicle Transport-U-Assembly Integrated Scheduling ProblemAdvanced Intelligent Computing Technology and Applications10.1007/978-981-97-5578-3_24(300-310)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-5578-3_24
Show More Cited By

Flowshop and Jobshop Schedules: Complexity and Approximation
1. Mathematics of computing

Recommendations

The Complexity of Flowshop and Jobshop Scheduling

NP-complete problems form an extensive equivalence class of combinatorial problems for which no nonenumerative algorithms are known. Our first result shows that determining a shortest-length schedule in an m-machine flowshop is NP-complete for m ≥ 3. ...
Makespan distribution of permutation flowshop schedules

The makespan distribution of permutation flowshop schedules has been a topic of debate for almost fifty years. Many researchers have confirmed or doubted the famous claim that the makespan distribution of permutation flowshop schedules is asymptotically ...
Dense open-shop schedules with release times

We study open-shop scheduling problems with job release times. The objective is to minimize the makespan. Dense schedules, easy to construct, are often used as approximate solutions. Performance ratios of the makespans from dense schedules and that of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Operations Research Volume 26, Issue 1

February 1978

224 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 February 1978

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

65
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jiang XLee KPinedo M(2024)Bicriteria two-machine flowshop scheduling: approximation algorithms and their limitsJournal of Scheduling10.1007/s10951-023-00781-x27:1(61-86)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10951-023-00781-x
Wang ZLiao W(2024)Smart scheduling of dynamic job shop based on discrete event simulation and deep reinforcement learningJournal of Intelligent Manufacturing10.1007/s10845-023-02161-w35:6(2593-2610)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s10845-023-02161-w
Yang DQian BZhang ZHu RLi K(2024)A Hyper-Heuristic Algorithm with Q-Learning for Distributed Flow Shop-Vehicle Transport-U-Assembly Integrated Scheduling ProblemAdvanced Intelligent Computing Technology and Applications10.1007/978-981-97-5578-3_24(300-310)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-5578-3_24
Song HYang YLin JYe J(2023)An effective hyper heuristic-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problemApplied Soft Computing10.1016/j.asoc.2023.110022135:COnline publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.asoc.2023.110022
Lan KZhang ZQian BHu RZhang D(2023)A Hyper-Heuristic Algorithm with Q-Learning for Distributed Permutation FlowshopScheduling ProblemAdvanced Intelligent Computing Technology and Applications10.1007/978-981-99-4755-3_11(122-131)Online publication date: 10-Aug-2023
https://dl.acm.org/doi/10.1007/978-981-99-4755-3_11
Strusevich V(2022)Complexity and approximation of open shop scheduling to minimize the makespanComputers and Operations Research10.1016/j.cor.2022.105732144:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.cor.2022.105732
Chen YCai YLiu LChen GGoebel RLin GSu BZhang A(2022)Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graphJournal of Combinatorial Optimization10.1007/s10878-021-00793-343:3(571-588)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s10878-021-00793-3
Dong JGoebel RHu JLin GSu B(2021)Minimizing total job completion time in MapReduce schedulingComputers and Industrial Engineering10.1016/j.cie.2021.107387158:COnline publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1016/j.cie.2021.107387
Leng CQiao YHu XWang H(2020)Co-scheduling aperiodic real-time tasks with end-to-end firm and soft deadlines in two-stage systemsReal-Time Systems10.1007/s11241-020-09352-156:4(391-451)Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s11241-020-09352-1
Kagaris DDutta S(2019)Scheduling Mutual Exclusion Accesses in Equal-Length JobsACM Transactions on Parallel Computing10.1145/33425626:2(1-26)Online publication date: 8-Aug-2019
https://dl.acm.org/doi/10.1145/3342562
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

The Complexity of Flowshop and Jobshop Scheduling

Makespan distribution of permutation flowshop schedules

Dense open-shop schedules with release times

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations