Article

Free access

Multiprocessor scheduling with rejection

Authors:

Yair Bartal,

Stefano Leonardi,

Alberto Marchetti-Spaccamela,

Jiří Sgall,

Leen StougieAuthors Info & Claims

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

Pages 95 - 103

Published: 28 January 1996 Publication History

PDF eReader

References

[1]

Y. Bartal, A. Fiat, H. Karloff, and R. Vohra, "New algorithms for an ancient scheduling problem", Proceedings of the 24th A CM Symposium on Theory of Computing, Victoria, Canada, 1992, 51-58.

Digital Library

Google Scholar

[2]

Y. Bartal, H. Karloff, and Y. Rabani, "A new lower bound for m-machine scheduling", Information Processing Letters, 50 (1994), 113-116.

Digital Library

Google Scholar

[3]

M. Garey and D. Johnson, Computers and intractability: a guide to the theory of NP- completeness, Freeman, San Francisco, 1979.

Digital Library

Google Scholar

[4]

G. Galambos and G. J. Woeginger. "An online scheduling heuristic with better worst case ratio than Graham's list scheduling". SIAM Journal on Uomputing, 22(2):349-355, 1993.

Digital Library

Google Scholar

[5]

R.L. Graham, "Bounds for certain multiprocessing anomalies", Bell System Technical Journal 45 (1966), 1563-1581.

Google Scholar

[6]

D.$. Hochbaum and D.B. Shmoys, "A polynomial approximation scheme for machine scheduling on uniform processors: using the dual approach", SiAM Journal on Computing, 17, pp. 539-551, 1988.

Digital Library

Google Scholar

[7]

D. Karger, S. Phillips, and E. Torng, "A better algorithm for an ancient scheduling problem", Proceedings of the 5th A CM/SIAM Symposium on Discrete Algorithms, 1994.

Digital Library

Google Scholar

[8]

R.M. Karp, "On-line algorithms versus off-line algorithms' how much is it worth to know the future?", Proc. World Computer Congress, 1992.

Digital Library

Google Scholar

[9]

J.K. Lenstra and A.H.G. Rinnooy Kan, "An introduction to multiprocessor scheduling", Technical Report, CWI, Amsterdam, 1988.

Google Scholar

[10]

J. Sgall, "On-line scheduling on parallel machines'', PhD thesis, Technical Report CMU- CS-94-144, Carnegie-Mellon University, Pittsburgh, PA, U.S.A., 1994.

Google Scholar

[11]

D. Sleator and R.E. Tarjan, "Amortized efficiency of list update and paging rules", Communications of A CM, 28, pp. 202-208 (1985).

Digital Library

Google Scholar

[12]

D. Shmoys, J. Wein, and D. Williamson, "Scheduling parallel machines on-line", Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991, 131- 140.

Digital Library

Google Scholar

Cited By

View all

Shabtay DGasper N(2012)Two-machine flow-shop scheduling with rejectionComputers and Operations Research10.1016/j.cor.2011.05.02339:5(1087-1096)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.cor.2011.05.023
Shabtay DGaspar NYedidsion L(2012)A bicriteria approach to scheduling a single machine with job rejection and positional penaltiesJournal of Combinatorial Optimization10.1007/s10878-010-9350-623:4(395-424)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1007/s10878-010-9350-6
Xu PLi X(2011)TOFUIEEE/ACM Transactions on Networking10.1109/TNET.2010.206722319:2(433-446)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1109/TNET.2010.2067223
Show More Cited By

Recommendations

Multiprocessor Scheduling with Rejection

We consider a version of multiprocessor scheduling with the special feature that jobs may be rejected at a certain penalty. An instance of the problem is given by $m$ identical parallel machines and a set of $n$ jobs, with each job characterized by a ...
Preemptive online scheduling with rejection of unit jobs on two uniformly related machines

We consider preemptive online and semi-online scheduling of unit jobs on two uniformly related machines. Jobs are presented one by one to an algorithm, and each job has a rejection penalty associated with it. A new job can either be rejected, in which ...
Bounded single-machine parallel-batch scheduling with release dates and rejection

We consider the bounded single-machine parallel-batch scheduling problem with release dates and rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and then processed on the machine. The objective is to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '96: Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms

January 1996

586 pages

ISBN:0898713668

Chairman:
Éva Tardos

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 28 January 1996

Check for updates

Qualifiers

Article

Conference

SODA96

Sponsor:

SIGACT
SIAM

SODA96: Conference on Discrete Algorithms

January 28 - 30, 1996

Georgia, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
395
Total Downloads

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

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Shabtay DGasper N(2012)Two-machine flow-shop scheduling with rejectionComputers and Operations Research10.1016/j.cor.2011.05.02339:5(1087-1096)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.cor.2011.05.023
Shabtay DGaspar NYedidsion L(2012)A bicriteria approach to scheduling a single machine with job rejection and positional penaltiesJournal of Combinatorial Optimization10.1007/s10878-010-9350-623:4(395-424)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1007/s10878-010-9350-6
Xu PLi X(2011)TOFUIEEE/ACM Transactions on Networking10.1109/TNET.2010.206722319:2(433-446)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1109/TNET.2010.2067223
Yu YRen SChen NWang XShin SOssowski SSchumacher MPalakal MHung C(2010)Profit and penalty aware (PP-aware) scheduling for tasks with variable task execution timeProceedings of the 2010 ACM Symposium on Applied Computing10.1145/1774088.1774159(334-339)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1145/1774088.1774159
Li SYuan J(2010)Parallel-machine scheduling with deteriorating jobs and rejectionTheoretical Computer Science10.1016/j.tcs.2010.06.008411:40-42(3642-3650)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1016/j.tcs.2010.06.008
Xu PLi XZhao QChandra RKrishnamachari B(2009)Online market driven spectrum scheduling and auctionProceedings of the 2009 ACM workshop on Cognitive radio networks10.1145/1614235.1614247(49-54)Online publication date: 21-Sep-2009
https://dl.acm.org/doi/10.1145/1614235.1614247
Xu PLi X(2009)SOFAProceedings of the 20th International Symposium on Algorithms and Computation10.1007/978-3-642-10631-6_33(311-320)Online publication date: 5-Dec-2009
https://dl.acm.org/doi/10.1007/978-3-642-10631-6_33
Gupta AKrishnaswamy RKumar ASegev D(2009)Scheduling with OutliersProceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-03685-9_12(149-162)Online publication date: 21-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03685-9_12
Plaxton CSun YTiwari MVin HGibbons PVishkin U(2006)Reconfigurable resource schedulingProceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures10.1145/1148109.1148123(93-102)Online publication date: 30-Jul-2006
https://dl.acm.org/doi/10.1145/1148109.1148123
Albers SLeighton FShor P(1997)Better bounds for online schedulingProceedings of the twenty-ninth annual ACM symposium on Theory of computing10.1145/258533.258566(130-139)Online publication date: 4-May-1997
https://dl.acm.org/doi/10.1145/258533.258566

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

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

Multiprocessor Scheduling with Rejection

Preemptive online scheduling with rejection of unit jobs on two uniformly related machines

Bounded single-machine parallel-batch scheduling with release dates and rejection