Open Access
Issue
RAIRO-Oper. Res.
Volume 56, Number 2, March-April 2022
Page(s) 1079 - 1088
DOI https://doi.org/10.1051/ro/2022045
Published online 14 April 2022
  • F. Abed, J.R. Correa and C.C. Huang, Optimal coordination mechanisms for multi-job scheduling games. In: ESA (2014). [Google Scholar]
  • R. Ahuja, O. Ergun, J. Orlin and A. Punnen, A survey of very large-scale neighborhood search techniques. Disc. Appl. Math. 123 (2002) 75–102. [CrossRef] [Google Scholar]
  • E. Angel, A survey of approximation results for local search algorithms. In: Efficient Approximation and Online Algorithms, edited by E. Bampis, K. Jansen and C. Kenyon. Springer (2006) 30–73. [CrossRef] [Google Scholar]
  • N. Bansal, A. Srinivasan and O. Svensson, Lift-and-round to improve weighted completion time on unrelated machines. In: STOC (2016). [Google Scholar]
  • P. Brucker, J. Hurink and F. Werner, Improving local search heuristics for some scheduling problems. Part II. Disc. Appl. Math. 72 (1997) 47–69. [CrossRef] [Google Scholar]
  • T. Brueggemann, J.L. Hurink and W. Kern, Quality of move-optimal schedules for minimizing total weighted completion time. Oper. Res. Lett. 34 (2006) 583–590. [CrossRef] [MathSciNet] [Google Scholar]
  • T. Brueggemann, J.L. Hurink, T. Vredeveld and G.J. Woeginger, Exponential size neighborhoods for makespan minimization scheduling. Naval Res. Logist. 58 (2011) 795–803. [CrossRef] [MathSciNet] [Google Scholar]
  • J. Bruno, E.G. Coffman and R. Sethi, Scheduling independent tasks to reduce mean finishing time. Commun. ACM 17 (1974) 382–387. [CrossRef] [Google Scholar]
  • Y. Cho and S. Sahni, Bounds for list schedules on uniform processors. SIAM J. Comput. 9 (1980) 91–103. [CrossRef] [MathSciNet] [Google Scholar]
  • R. Cole, J.R. Correa, V. Gkatzelis, V. Mirrokni and N. Olver, Decentralized utilitarian mechanisms for scheduling games. Games Econ. Behav. 92 (2015) 306–326. [CrossRef] [Google Scholar]
  • R.W. Conway, W.L. Maxwell and L.W. Miller, Theory of Scheduling. Addison-Wesley (1967). [Google Scholar]
  • J.R. Correa and F.T. Muñoz, Performance guarantees of local search for minsum scheduling problems. Math. Program. (2020). https://doi.org/10.1007/s10107-020-01571-5. [Google Scholar]
  • W.L. Eastman, S. Even and I.M. Isaacs, Bounds for the optimal scheduling of n jobs on m processors. Manage Sci. 11 (1964) 268–279. [CrossRef] [Google Scholar]
  • L. Epstein and J. Sgall, Approximation schemes for scheduling on uniformly related and identical parallel machines. Algorithmica 39 (2004) 43–57. [CrossRef] [MathSciNet] [Google Scholar]
  • G. Finn and E. Horowitz, A linear time approximation algorithm for multiprocessor scheduling. BIT Numer. Math. 19 (1979) 312–320. [CrossRef] [Google Scholar]
  • A. Frangioni, E. Necciari and M.G. Scutellà, A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems. J. Comb. Optim. 8 (2004) 195–220. [CrossRef] [MathSciNet] [Google Scholar]
  • M. Garey and D. Johnson, Strong NP-completeness results: Motivation, examples, and implications. J. ACM 25 (1978) 499–508. [CrossRef] [Google Scholar]
  • M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman and Co., San Francisco (1979). [Google Scholar]
  • R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Disc. Math. 5 (1979) 287–326. [CrossRef] [Google Scholar]
  • W.A. Horn, Minimizing average flow time with parallel machines. Oper. Res. 21 (1973) 846–847. [CrossRef] [Google Scholar]
  • E. Horowitz and S. Sahni, Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23 (1976) 317–327. [CrossRef] [Google Scholar]
  • J.K. Lenstra, A.H.G. Rinooy Kan and P. Brucker, Complexity of machine scheduling problems. Ann. Disc. Math. 1 (1977) 343–362. [CrossRef] [Google Scholar]
  • S. Li, Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations. In: FOCS (2017). [Google Scholar]
  • W. Michiels, E. Aarts and J. Korst, Theoretical Aspects of Local Search. Springer Science & Business Media, Berlin (2007). [Google Scholar]
  • C. Rutten, D. Recalde, P. Schuurman and T. Vredeveld, Performance guarantees of jump neighborhoods on restricted related parallel machines. Oper. Res. Lett. 40 (2012) 287–291. [CrossRef] [MathSciNet] [Google Scholar]
  • P. Schuurman and T. Vredeveld, Performance guarantees of local search for multiprocessor scheduling. INFORMS J. Comput. 19 (2007) 52–63. [CrossRef] [MathSciNet] [Google Scholar]
  • M. Skutella and G.J. Woeginger, A PTAS for minimizing the total weighted completion time on identical parallel machines. Math. Oper. Res. 25 (2000) 63–75. [CrossRef] [MathSciNet] [Google Scholar]
  • W.E. Smith, Various optimizers for single-stage production. Naval Res. Logist. 3 (1956) 59–66. [CrossRef] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.