Article

Free access

New and improved algorithms for minsum shop scheduling

Authors:

Maurice Queyranne,

Maxim SvirdenkoAuthors Info & Claims

SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms

Pages 871 - 878

Published: 01 February 2000 Publication History

PDF eReader

References

[1]

J.O. Achugbue and F.Y. Chin, "Scheduling the open shop to minimize mean flow time." SIAM Journal on Computing 11 (1982) 709-72{).]]

Google Scholar

[2]

S. Chakrabarti, C.A. Phillips, A.S. Schulz, D.B. Shmoys, C. Stein and J.Wein, "Improved Scheduling Algorithms for Minsum Criteria." in: F. Meyer auf der Heide and B. Monien, eds, Automata, Languages and Programming (Proceedings of the 23rd International Colloquium ICALP'96, 1996), Lecture Notes in Computer Science 1099, Springer, 646 - 657.]]

Digital Library

Google Scholar

[3]

C. Chekuri, Approximation Algorithms for Scheduling Problems. Ph.D. Dissertation, Dept. of Computer Science, Stanford University, August 1998.]]

Digital Library

Google Scholar

[4]

C. Chekuri, R. Motwani, B. Natarajan, and C. Stein, "Approximation Techniques for Average Completion Time Scheduling." Proceedings of the 8th Symposium on Discrete Algorithms (SODA'97, 1997) 609-618.]]

Digital Library

Google Scholar

[5]

U. Feige and C. Scheideler, "Improved bounds for acyclic job shop scheduling." In: Proceedings of the 30th Annual A CM Symposium on Theory of Computing (STOC'98, 1998), ACM Press, New York, NY, 624-633.]]

Digital Library

Google Scholar

[6]

M. Goemans and J. Kleinberg, "An improved approximation ratio for the minimum latency problem." In: Proceedings of the 7th A CM-SIA M Symposium on Discrete Algorithms (SODA'96, 1996) 152-157.]]

Digital Library

Google Scholar

[7]

L. A. Goldberg, M. Paterson, A. Srinivasan, and E. Sweedyk, "Better approximation guarantees for jobshop scheduling." Dept. of Computer Science, University of Waxwick, Coventry, UK. Preliminary version in: Proceedings of the 8th Symposium on Discrete AlgoritAms (1997) 599-608.]]

Digital Library

Google Scholar

[8]

T. Gonzalez and S. Sahni, "Fiowshop and jobshop schedules: Complexity and approximation." Operations Research 26 (1978) 36-52.]]

Google Scholar

[9]

M. GrStschel, L. Lovksz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Springer, 1988.]]

Google Scholar

[10]

L.A. Hall, D.B. Shmoys, and J. Wein, "Scheduling to Minimize Average Completion Time: Off-line and Online Algorithms", Proceedings of the 7th Symposium on Discrete Algorithms (1996) 142-151.]]

Digital Library

Google Scholar

[11]

L.A. Hall, A.S. Schulz, D.B. Shmoys, and J. Wein, "Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms", Mathematics of Operations Research 22 (1997) 513- 544.]]

Google Scholar

[12]

H. Hoogeveen, P. Schuurman, and G. Woeginger, "Nonapproximability results for scheduling problems with reinsure criteria." In: R.E. Bixby, E.A. Boyd, and R.Z. Rios-Mercado, eds, Integer Programming and Combinatorial Optimization (IPCO-VI Proceedings, 1998), Lecture Notes in Computer Science 1412, Springer, 353-366.]]

Digital Library

Google Scholar

[13]

K. Jansen, 1%. Solis-Oba and M. Sviridenko, "Makespan Minimization in Job Shops: a Polynomial Time Approximation Scheme." In: Proceedings of the 31tA Annual A CM Symposium on Theory of Computing (STOC'99, 1999), ACM Press, New York, NY, 394-399.]]

Digital Library

Google Scholar

[14]

E. L. Lawler, M. G. Luby, and V. V. Vazirani, "Scheduling open shops with parallel machines." Operations Research Letters 1 (1982) 161-164.]]

Google Scholar

[15]

F.T. Leighton, B.M. Maggs, and S.B. Rao, "Packet routing and job-shop scheduling in O(congestion + dilation) steps." Combinatoriea 14 (1994) 167-186.]]

Google Scholar

[16]

F.T. Leighton, B.M. Maggs, and A.W. RJcha, "Fast algorithms for finding O(congestion + dilation) packet routing schedules." Technical Report CMU-CS-96-152, School of Computer Science, Carnegie-Mellon University, 1996. To appear in Combinatorico~]]

Google Scholar

[17]

S.T. McCormick and M.L. Pinedo, "Scheduling n Independent Jobs on m Uniform Machines with both Flowtime and Makespan Objectives: A Parametric Analysis." ORSA Journal on Computing 7' (1995) 63-77.]]

Google Scholar

[18]

M. Queyranne, "Polyhedral Approaches to Scheduling Problems." Seminar presented at RUTCOR, Rutgers University, November 16, 1987.]]

Google Scholar

[19]

M. Queyranne, "Structure of a Simple Scheduling Polyhe&on." Mathematical Programming 58 (1993) 263- 285.]]

Google Scholar

[20]

M. Queyranne and A.S. Schulz, "Polyhedral Approaches to Machine Scheduling." Report 408/1994, Department of Mathematics, University of Technology, Berlin, Germany, November 1994; revised, October 1996.]]

Google Scholar

[21]

M. Queyranne and M. Sviridenko, "Approximation Algorithms for Shop Scheduling Problems with Minsum Objective." Research Report, Faculty of Commerce and Business Administration, University of British Columbia, April 29, 19992.]]

Google Scholar

[22]

P~. Roundy, R. "98% effective Integer-Ratio Lot Sizing for One-Warehouse Multi-Retailer Systems." Management Science 31 (1985) 1416-1430.]]

Google Scholar

[23]

A.S. Schulz, "Polytopes and Scheduling." Ph.D. Thesis, Faculty of Mathematics, Technical University of Berlin, Berlin, Germany, February 1996.]]

Google Scholar

[24]

A.S. Schulz, "Scheduling to minimize total weigthed completion time: Performance guarantees of LP-based heuristics and lower bounds." In: W.H. Cunningham, M. Queyranne and S.T. McCormick, eds, Integer Programming and Combinatorial Optimization (IPCO-V Proceedings, 1996), Lecture Notes in Computer Science 1084, Springer, 301-315.]]

Digital Library

Google Scholar

[25]

P. Schuurman and G.J. Woeginger, "Approximation algorithms for the rnultiprocessor open shop scheduling problem." To appear in Operation Research Letters.]]

Google Scholar

[26]

D.B. Shmoys, "Using linear programming in the design and analysis of approximation algorithms: Two illustrative exaraples." In: K.Jansen and J.Rolim, eds, Approximation Algorithms for Combinatorial Optimization (APPROX'98 Proceedings, 1998), Lecture Notes in Computer Science 1444, Springer, 15-32.]]

Digital Library

Google Scholar

[27]

S.V. Sevastianov and G.J. Woeginger, "Makespan Minimization in Preemtive Two-Machine Job Shops." Computing 60 (1998) 73-79.]]

Digital Library

Google Scholar

[28]

D.B. Shmoys, C. Stein, and J. Wein, "Improved approximation algorithms for shop scheduling problems." SIAM Journal of Computing 23 (1994), 617-632.]]

Digital Library

Google Scholar

[29]

M. Skutella, "Approximation and Randomization in Scheduling", Ph.D. Thesis, Faculty of Mathematics, Technical University of Berlin, Berlin, Germany, May 1998.]]

Google Scholar

[30]

L.A. Wolsey, "Mixed integer programming formulations for production planning and scheduling problems." Invited talk at the 12th International Symposium on Mathematical Programming, MIT, Cambridge, Mass., August 1985.]]

Google Scholar

Cited By

View all

Mestre JTeng S(2008)Adaptive local ratioProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347099(152-160)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347099
Moscibroda TMutlu OBazzi RPatt-Shamir B(2008)Distributed order scheduling and its application to multi-core dram controllersProceedings of the twenty-seventh ACM symposium on Principles of distributed computing10.1145/1400751.1400799(365-374)Online publication date: 18-Aug-2008
https://dl.acm.org/doi/10.1145/1400751.1400799
Andresen MBräSel HMöRig MTusch JWerner FWillenius P(2008)Simulated annealing and genetic algorithms for minimizing mean flow time in an open shopMathematical and Computer Modelling: An International Journal10.1016/j.mcm.2008.01.00248:7-8(1279-1293)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.1016/j.mcm.2008.01.002
Show More Cited By

Index Terms

Recommendations

Approximation algorithms for shop scheduling problems with minsum objective: A correction

We present a correction to the paper, "Approximation algorithms for shop scheduling problems with minsum objective" (Journal of Scheduling 2002; 5 :287---305) by Queyranne and Sviridenko. This correction provides a correct derivation of its 2e ...
Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion

Flexible job shop scheduling problem.Ensembles of heuristics.Re-scheduling for new job insertion.Multiple objectives scheduling problem. This study investigates the flexible job shop scheduling problem (FJSP) with new job insertion. FJSP with new job ...
Improved bounds for scheduling conflicting jobs with minsum criteria

We consider a general class of scheduling problems where a set of conflicting jobs needs to be scheduled (preemptively or nonpreemptively) on a set of machines so as to minimize the weighted sum of completion times. The conflicts among jobs are formed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms

February 2000

965 pages

ISBN:0898714532

Chairman:
David Shmoys

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 February 2000

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
488
Total Downloads

Downloads (Last 12 months)51
Downloads (Last 6 weeks)7

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mestre JTeng S(2008)Adaptive local ratioProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347099(152-160)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347099
Moscibroda TMutlu OBazzi RPatt-Shamir B(2008)Distributed order scheduling and its application to multi-core dram controllersProceedings of the twenty-seventh ACM symposium on Principles of distributed computing10.1145/1400751.1400799(365-374)Online publication date: 18-Aug-2008
https://dl.acm.org/doi/10.1145/1400751.1400799
Andresen MBräSel HMöRig MTusch JWerner FWillenius P(2008)Simulated annealing and genetic algorithms for minimizing mean flow time in an open shopMathematical and Computer Modelling: An International Journal10.1016/j.mcm.2008.01.00248:7-8(1279-1293)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.1016/j.mcm.2008.01.002
Garg NKumar APandit V(2007)Order scheduling modelsProceedings of the 27th international conference on Foundations of software technology and theoretical computer science10.5555/1781794.1781804(96-107)Online publication date: 12-Dec-2007
https://dl.acm.org/doi/10.5555/1781794.1781804
Queyranne MSviridenko M(2002)A (2 + ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objectiveJournal of Algorithms10.1016/S0196-6774(02)00251-145:2(202-212)Online publication date: 1-Nov-2002
https://dl.acm.org/doi/10.1016/S0196-6774%2802%2900251-1

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Approximation algorithms for shop scheduling problems with minsum objective: A correction

Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion

Improved bounds for scheduling conflicting jobs with minsum criteria