Approximability and nonapproximability results for minimizing total flow time on a single machine

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximability and nonapproximability results for minimizing total flow time on a single machine

Full text

Pdf (789 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 418 - 426

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Hans Kellerer	Institut für Statistik, Ökonometrie und Operations Research, Universität Graz, A-8010 Graz, Austria
Thomas Tautenhahn	Fakultät für Mathematik, Otto-von-Guericke Universität Magdeburg, D-39016 Magdeburg, Germany
Gerhard J. Woeginger	Eindhoven University of Technology, Department of Mathematics and Computing Science, P.O. Box 513, NL-5600 MB Eindhoven, The Netherlands

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 32, Citation Count: 27

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237814.237989 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R.H. Ahmadi and U. Bagchi, "Lower bounds for singlemachine scheduling problems", Naval Res. Logist. 37, 967- 979 (1990).
	2	K.R. Baker, Introduction to Sequencing and Scheduling, Wiley, New York, 1974.
	3	L. Bianco and S. Ricciardelli, "Scheduling of a single machine to minimize total weighted completion time subject to release dates", Naval Res. Logist. 29, 151--167 (1982).
	4	R. Chandra, "On n{l{F dynamic deterministic problems", Naval Res. Logist. 26, 537-544 (1979).
	5	C. Chu, "Efficient heuristics to minimize total flow time with release dates", Oper. Res. Left. 12, 321-330 (1992).
	6	C. Chu, "A branch-and-bound algorithm to minimize total flow time with unequal release dates", Naval Res. Logist. 39, 859-875 (1992).
	7	J.S. Deogun, "On scheduling with ready times to minimize mean flow time", Comput. J. 26,320-328 (1983).
	8	M.I. Dessouky and J.S. Deogun, "Sequencing jobs with unequal ready times to minimize mean flow time", SlAM J, Comput. 10, 192-202 (1981).
	9	J. Du , J. Y.-I. Leung , G. H. Young, Minimizing mean flow time with release time constraint, Theoretical Computer Science, v.75 n.3, p.347-355, Oct. 1990 [doi>10.1016/0304-3975(90)90100-V]
	10	M. E. Dyer , L. A. Wolsey, Formulating the single machine sequencing problem with release dates as a mixed integer program, Discrete Applied Mathematics, v.26 n.2-3, p.255-270, Mar. 1990 [doi>10.1016/0166-218X(90)90104-K]
	11	M.R. Garey and D.S. Johnson, Computers and Intractability, Freeman and Company, San Francisco, 1070.
	12	P.G. Gazmuri, "Probabilistic analysis of a machine scheduling problem", Math. Oper. Res. 10, 328-339 (1985).
	13	A.M.A. Hariri and C.N. Potts, "An algorithm for single machine sequencing with release times to minimize total weighted completion time", Discr. Appl. Math. 5, 99-109 (1983).
	14	J. Labetoulle, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, "Preemptive scheduling of uniform machines subject to release dates", Progress in Combinatorial Optimization, Academic Press, New York, 245-261 (1984).
	15	J.K. Lenstra, A.H.G. Riunooy Karl and P. Brucker, "Complexity of machine scheduling problems", Ann. Discrete Math. 1,343-362 (1977).
	16	W. Mao and A. Rifkin, "Analysis of the FCFS algorithm for 11r~ I ~ 6'3", unpublished manuscript.
	17	M.E. Posner, "Minimizing weighted completion times with deadlines", Oper. Research 33, 562-574 (1985).
	18	W.E. Smith, "Various optimizers for single-state production'', Naval Res. Lo&ist. Quart. 3, 56-66 (1956).

CITED BY 27

	Chandra Chekuri , Sanjeev Khanna, Approximation schemes for preemptive weighted flow time, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Swarup Acharya , S. Muthukrishnan, Scheduling on-demand broadcasts: new metrics and algorithms, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.43-54, October 25-30, 1998, Dallas, Texas, United States
	Soumen Chakrabarti , S. Muthukrishnan, Resource scheduling for parallel database and scientific applications, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.329-335, June 24-26, 1996, Padua, Italy
	Chandra Chekuri , Sanjeev Khanna , An Zhu, Algorithms for minimizing weighted flow time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.84-93, July 2001, Hersonissos, Greece
	Ashish Goel , Monika R. Henzinger , Serge Plotkin , Eva Tardos, Scheduling data transfers in a network and the set scheduling problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.189-197, May 01-04, 1999, Atlanta, Georgia, United States
	Xiaotie Deng , Patrick Dymond, On multiprocessor system scheduling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.82-88, June 24-26, 1996, Padua, Italy
	Baruch Awerbuch , Yossi Azar , Stefano Leonardi , Oded Regev, Minimizing the flow time without migration, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.198-205, May 01-04, 1999, Atlanta, Georgia, United States
	Cynthia A. Phillips , R. N. Uma , Joel Wein, Off-line admission control for general scheduling problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.879-888, January 09-11, 2000, San Francisco, California, United States
	Martin W. P. Savelsbergh , R. N. Uma , Joel Wein, An experimental study of LP-based approximation algorithms for scheduling problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.453-462, January 25-27, 1998, San Francisco, California, United States
	Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
	Cynthia A. Phillips , Cliff Stein , Eric Torng , Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1997, El Paso, Texas, United States
	Luca Becchetti , Stefano Leonardi , S. Muthukrishnan, Scheduling to minimize average stretch without migration, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.548-557, January 09-11, 2000, San Francisco, California, United States
	Martin Skutella , Gerhard J. Woeginger, A PTAS for minimizing the weighted sum of job completion times on parallel machines, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.400-407, May 01-04, 1999, Atlanta, Georgia, United States
	Stefano Leonardi , Danny Raz, Approximating total flow time on parallel machines, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.110-119, May 04-06, 1997, El Paso, Texas, United States
	Luca Becchetti , Stefano Leonardi , S. Muthukrishnan, Average stretch without migration, Journal of Computer and System Sciences, v.68 n.1, p.80-95, February 2004
	Leah Epstein , Rob van Stee, Lower bounds for on-line single-machine scheduling, Theoretical Computer Science, v.299 n.1-3, p.439-450, 18 April 2003
	Nir Avrahami , Yossi Azar, Minimizing total flow time and total completion time with immediate dispatching, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Y. Guo , A. Lim , B. Rodrigues , S. Yu, Minimizing total flow time in single machine environment with release time: an experimental analysis, Computers and Industrial Engineering, v.47 n.2-3, p.123-140, November 2004
	Monaldo Mastrolilli, Notes on max flow time minimization with controllable processing times, Computing, v.71 n.4, p.375-386, December 2003
	Leah Epstein , Rob van Stee, Optimal on-line flow time with resource augmentation, Discrete Applied Mathematics, v.154 n.4, p.611-621, 15 March 2006
	F. Afrati , I. Milis, Designing PTASs for MIN-SUM scheduling problems, Discrete Applied Mathematics, v.154 n.4, p.622-639, 15 March 2006
	Philipp Friese , Jörg Rambau, Online-optimization of multi-elevator transport systems with reoptimization algorithms based on set-partitioning models, Discrete Applied Mathematics, v.154 n.13, p.1908-1931, 15 August 2006
	Naveen Garg , Amit Kumar, Minimizing average flow time on related machines, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Stefano Leonardi , Danny Raz, Approximating total flow time on parallel machines, Journal of Computer and System Sciences, v.73 n.6, p.875-891, September, 2007
	Nikhil Bansal , Ho-Leung Chan, Weighted flow time does not admit O(1)-competitive algorithms, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1238-1244, January 04-06, 2009, New York, New York
	Nikhil Bansal , Kedar Dhamdhere, Minimizing weighted flow time, ACM Transactions on Algorithms (TALG), v.3 n.4, p.39-es, November 2007
	Jivitej S. Chadha , Naveen Garg , Amit Kumar , V. N. Muralidhara, A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA