research-article

Improved bounds for scheduling conflicting jobs with minsum criteria

Authors:

Magnús M. Halldórsson,

Hadas ShachnaiAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 4, Issue 1

Article No.: 11, Pages 1 - 20

https://doi.org/10.1145/1328911.1328922

Published: 28 March 2008 Publication History

Abstract

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 as an arbitrary conflict graph.

Building on the framework of Queyranne and Sviridenko [2002b], we present a general technique for reducing the weighted sum of completion-times problem to the classical makespan minimization problem. Using this technique, we improve the best-known results for scheduling conflicting jobs with the min-sum objective, on several fundamental classes of graphs, including line graphs, (k + 1)-claw-free graphs, and perfect graphs. In particular, we obtain the first constant-factor approximation ratio for nonpreemptive scheduling on interval graphs. We also improve the results of Kim [2003] for scheduling jobs on line graphs and for resource-constrained scheduling.

References

[1]

Afrati, F., Bampis, E., Fishkin, A., Jansen, K., and Kenyon, C. 2000. Scheduling to minimize the average completion time of dedicated tasks. In Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science. Springer, 454--464.

Digital Library

[2]

Bar-Noy, A., and Kortsarz, G. 1998. The minimum color-sum of bipartite graphs. J. Algor. 28, 339--365.

Digital Library

[3]

Bar-Noy, A., Halldórsson, M. M., Kortsarz, G., Shachnai, H., and Tamir, T. 2000. Sum multicoloring of graphs. J. Algor. 37, 422--450.

Digital Library

[4]

Bar-Noy, A., Bellare, M., Halldórsson, M. M., Shachnai, H., and Tamir, T. 1998. On chromatic sums and distributed resource allocation. Inf. Comput. 140, 183--202.

Digital Library

[5]

Bell, M. 1992. Future directions in traffic signal control. Transport. Res. Part A 26, 303--313.

[6]

Bodlaender, H. L., and Fomin, F. V. 2004. Equitable colorings of bounded treewidth graphs. In Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science. Springer, 180--190.

[7]

Bullock, D., and Hendrickson, C. 1994. Roadway traffic control software. IEEE Trans. Control Syst. Technol. 2, 255--264.

[8]

Chakrabarti, S., Phillips, C. A., Schulz, A. S., Shmoys, D. B., Stein, C., and Wein, J. 1996. Improved scheduling problems for minsum criteria. In Proceedings of the 23rd International Colloquium on Automata, Languages, and Programming (ICALP). Springer, 646--657.

Digital Library

[9]

Chen, J., Cidon, I., and Ofek, Y. 1993. A local fairness algorithm for gigabit lans/mans with spatial reuse. IEEE J. Select. Areas Commun. 11, 1183--1192.

[10]

Coffman, E. G., Garey, M. R., Johnson, D. S., and LaPaugh, A. S. 1985. Scheduling file transfers. SIAM J. Comput. 14, 3, 744--780.

[11]

Feige, U., Lovász, L., and Tetali, P. 2004. Approximating min-sum set cover. Algorithmica 40, 4, 219--234.

Digital Library

[12]

Gandhi, R., Halldórsson, M. M., Kortsarz, G., and Shachnai, H. 2006. Improved results for data migration and openshop scheduling. ACM Trans. Algor. 2, 1, 116--129.

Digital Library

[13]

Gergov, J. 1999. Algorithms for compile-time memory allocation. In Proceedings of the 10 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 907--908.

Digital Library

[14]

Giaro, K., Malafiejski, M., Kubale, M., and Piwakowski, K. 2002. Dedicated scheduling of biprocessor tasks to minimize mean flow times. In Proceedings of the 4th International Conference on Parallel Processing and Applied Mathematics. Springer, 87--96.

Digital Library

[15]

Gonen, M. 2001. Coloring problems on interval graphs and trees. M. Sc. Thesis, School of Computer Science, The Open University, Tel-Aviv.

[16]

Grötschel, M., Lovász, L., and Schrijver, A. 1993. Geometric Algorithms and Combinatorial Optimization. Springer.

[17]

Hall, L., Schulz, A. S., Shmoys, D. B., and Wein, J. 1997. Scheduling to minimize average completion time: Off-Line and on-line approximation algorithms. Math. Oper. Res. 22, 513--544.

Digital Library

[18]

Hall, L., Shmoys, D. B., and Wein, J. 1996. Scheduling to minimize average completion time: Off-Line and on-line approximation algorithms. In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 142--151.

Digital Library

[19]

Halldórsson, M. M., and Kortsarz, G. 2002. Tools for multicoloring with applications to planar graphs and partial k-trees. J. Algor. 42, 2, 334--366.

Digital Library

[20]

Halldórsson, M. M., Kortsarz, G., Proskurowski, A., Salman, R., Shachnai, H., and Telle, J. A. 2003a. Multicoloring trees. Inf. Comput. 180, 2, 113--129.

Digital Library

[21]

Halldórsson, M. M., Kortsarz, G., and Shachnai, H. 2003b. Sum coloring interval graphs and k-claw free graphs with applications for scheduling dependent jobs. Algorithmica 37, 187--209.

Digital Library

[22]

Hoogeveen, H., van der Velde, S. L., and Veltman, B. 1994. Complexity of scheduling multi-processor tasks with prespecified processor allocations. Discr. Appl. Math. 55, 259--272.

Digital Library

[23]

Kim, Y. 2005. Data migration to minimize the average completion time. J. Algor. 55, 42--57.

Digital Library

[24]

Kubale, M. 1996. Preemptive versus non-preemptive scheduling of biprocessor tasks on dedicated processors. Euro. J. Oper. Res. 94, 242--251.

[25]

Kubicka, E. 1989. The chromatic sum of a graph. Ph.D. Thesis, Western Michigan University.

[26]

Malafiejski, M., Giaro, K., Janczewski, R., and Kubale, M. 2004. Sum coloring of bipartite graphs with bounded degree. Algorithmica 40, 4, 235--244.

Digital Library

[27]

Marx, D. 2004. Chromatic sum and minimum sum multicoloring. http://www.cs.bme.hu/dmarx/sum.html.

[28]

Marx, D. 2003. Minimum sum multicoloring on the edges of trees. In Proceedings of the 1st Workshop on Approximation and Online Algorithms. Springer, 214--226.

Digital Library

[29]

Nicoloso, S., Sarrafzadeh, M., and Song, X. 1999. On the sum coloring problem on interval graphs. Algorithmica 23, 109--126.

[30]

Potts, C. N. 1980. An algorithm for the single machine sequencing problem with precedence constraints. Math. Program. Stud. 13, 78--87.

[31]

Queyranne, M. 1993. Structure of a simple scheduling polyhedron. Math. Program. 58, 263--285.

Digital Library

[32]

Queyranne, M. 1987. Polyhedral approaches to scheduling problems. Seminar presented at Rucor, Rutgers University.

[33]

Queyranne, M., and Sviridenko, M. 2002a. A (2 + &epsi;)-approximation algorithm for generalized preemptive open shop problem with minsum objective. J. Algor. 45, 202--212.

Digital Library

[34]

Queyranne, M., and Sviridenko, M. 2002b. Approximation algorithms for shop scheduling problems with minsum objective. J. Schedul. 5, 287--305.

[35]

Schulz, A. S. 1996. Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds. In Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization. Springer, 301--315.

Digital Library

[36]

Woeginger, G. 1997. Private communication.

[37]

Wolsey, L. 1985. Mixed integer programming formulations for production planning and scheduling problems. Invited talk at the 12th International Symposium on Mathematical Programming, Cambridge, MA.

Cited By

Shafiee MGhaderi J(2022)Scheduling Parallel-Task Jobs Subject to Packing and Placement ConstraintsOperations Research10.1287/opre.2021.219870:6(3403-3419)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1287/opre.2021.2198
Niu DLiu BYin M(2021)Local search for weighted sum coloring problemApplied Soft Computing10.1016/j.asoc.2021.107290106:COnline publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1016/j.asoc.2021.107290
Epstein LLevin A(2019)On the performance guarantee of First Fit for sum coloringJournal of Computer and System Sciences10.1016/j.jcss.2018.08.00299(91-105)Online publication date: Feb-2019
https://doi.org/10.1016/j.jcss.2018.08.002
Show More Cited By

Index Terms

Improved bounds for scheduling conflicting jobs with minsum criteria
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Improved results for data migration and open shop scheduling

The data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. We consider this problem with the objective of minimizing the sum of completion times of all storage devices. It ...
A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine

We present a new linear programming relaxation for the problem of minimizing the sum of weighted completion times of precedence-constrained jobs. Given a set of n jobs, each job j has processing time p"j and weight w"j. There is also a partial order @? ...
Preemptive Weighted Completion Time Scheduling of Parallel Jobs

We present a new algorithm for the preemptive offline scheduling of independent jobs on a system consisting of m identical machines. The jobs can be parallel; that is, they may need the concurrent availability of several machines for their execution. To ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 4, Issue 1

March 2008

343 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1328911

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 March 2008

Accepted: 01 May 2007

Received: 01 March 2005

Published in TALG Volume 4, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
457
Total Downloads

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

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shafiee MGhaderi J(2022)Scheduling Parallel-Task Jobs Subject to Packing and Placement ConstraintsOperations Research10.1287/opre.2021.219870:6(3403-3419)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1287/opre.2021.2198
Niu DLiu BYin M(2021)Local search for weighted sum coloring problemApplied Soft Computing10.1016/j.asoc.2021.107290106:COnline publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1016/j.asoc.2021.107290
Epstein LLevin A(2019)On the performance guarantee of First Fit for sum coloringJournal of Computer and System Sciences10.1016/j.jcss.2018.08.00299(91-105)Online publication date: Feb-2019
https://doi.org/10.1016/j.jcss.2018.08.002
Sun H(2019)Non-clairvoyant scheduling with conflicts for unit-size jobsInformation Processing Letters10.1016/j.ipl.2018.12.008144(1-8)Online publication date: Apr-2019
https://doi.org/10.1016/j.ipl.2018.12.008
Friggstad ZGolestanian AKhodamoradi KMartin CRahgoshay MRezapour MSalavatipour MZhang Y(2019)Scheduling problems over a network of machinesJournal of Scheduling10.1007/s10951-018-0591-z22:2(239-253)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s10951-018-0591-z
Gamzu ISegev D(2019)A polynomial-time approximation scheme for the airplane refueling problemJournal of Scheduling10.1007/s10951-018-0569-x22:1(119-135)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s10951-018-0569-x
Shafiee MGhaderi J(2018)An Improved Bound for Minimizing the Total Weighted Completion Time of Coflows in DatacentersIEEE/ACM Transactions on Networking10.1109/TNET.2018.284585226:4(1674-1687)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2845852
Epstein LLevin ASegev DWeimann O(2018)Improved bounds for randomized preemptive online matchingInformation and Computation10.1016/j.ic.2017.12.002259(31-40)Online publication date: Apr-2018
https://doi.org/10.1016/j.ic.2017.12.002
Shafiee MGhaderi J(2017)Scheduling Coflows in Datacenter NetworksACM SIGMETRICS Performance Evaluation Review10.1145/3143314.307854845:1(29-30)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1145/3143314.3078548
Shafiee MGhaderi JHajek BOh SChaintreau AGolubchik LZhang Z(2017)Scheduling Coflows in Datacenter NetworksProceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems10.1145/3078505.3078548(29-30)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1145/3078505.3078548
Show More Cited By

View Options

Login options

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

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents