Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
In Memoriam: Ker-I Ko (1950–2018) Read chapter Read first chapter

2020 | OriginalPaper | Chapter

A Review for Submodular Optimization on Machine Scheduling Problems

Author : Siwen Liu

Published in: Complexity and Approximation

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper provides a review of recent results on machine scheduling problems solved by methods of submodular optimization. We present some basic definitions of submodular functions and their connection to scheduling models. Based on the classification of problem features, we conclude different scheduling models, applications of these scheduling scenarios, approaches of submodular optimization, and the performance of corresponding algorithms. It is shown that the use of these submodular optimization methodologies yields fast and efficient algorithms for specific scheduling models such as controllable processing time, unreliable job processing, and common operation scheduling. By identifying the trends in this field, we discuss some potential directions for future research.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter An Efficient Approximation Algorithm for the Steiner Tree Problem
next chapter Edge Computing Integrated with Blockchain Technologies
Literature
1.
2.
Arbib, C., Felici, G., Servilio, M.: Common operation scheduling with general processing times: a branch-and-cut algorithm to minimize the weighted number of tardy jobs. Omega 84, 18–30 (2019)CrossRef
3.
Bambagini, M., Lelli, J., Buttazzo, G., Lipari, G.: On the energy-aware partitioning of real-time tasks on homogeneous multi-processor systems. In: 2013 4th Annual International Conference on Energy Aware Computing Systems and Applications (ICEAC), pp. 69–74. IEEE (2013)
4.
5.
Belov, G., Scheithauer, G.: Setup and open-stacks minimization in one-dimensional stock cutting. INFORMS J. Comput. 19(1), 27–35 (2007)MathSciNetMATHCrossRef
6.
Chaudhry, I.A., Khan, A.A.: A research survey: review of flexible job shop scheduling techniques. Int. Trans. Oper. Res. 23(3), 551–591 (2016)MathSciNetMATHCrossRef
7.
Chen, Y., Krause, A.: Near-optimal batch mode active learning and adaptive submodular optimization. ICML (1) 28(160–168), 8–1 (2013)
8.
Chen, Z.L., Lu, Q., Tang, G.: Single machine scheduling with discretely controllable processing times. Oper. Res. Lett. 21(2), 69–76 (1997)MathSciNetMATHCrossRef
9.
Cheng, T., Chen, Z., Li, C.L.: Parallel-machine scheduling with controllable processing times. IIE Trans. 28(2), 177–180 (1996)CrossRef
10.
Cheng, T., Diamond, J., Lin, B.: Optimal scheduling in film production to minimize talent hold cost. J. Optim. Theor. Appl. 79(3), 479–492 (1993)MathSciNetMATHCrossRef
11.
Edis, E.B., Oguz, C., Ozkarahan, I.: Parallel machine scheduling with additional resources: notation, classification, models and solution methods. Eur. J. Oper. Res. 230(3), 449–463 (2013)MathSciNetMATHCrossRef
12.
Epasto, A., Lattanzi, S., Vassilvitskii, S., Zadimoghaddam, M.: Submodular optimization over sliding windows. In: Proceedings of the 26th International Conference on World Wide Web, pp. 421–430 (2017). International World Wide Web Conferences Steering Committee
13.
Fink, A., Voß, S.: Applications of modern heuristic search methods to pattern sequencing problems. Comput. Oper. Res. 26(1), 17–34 (1999)MATHCrossRef
14.
Fokkink, R., Lidbetter, T., Végh, L.A.: On submodular search and machine scheduling. Math. Oper. Res. 44(4), 1431–1449 (2019)MathSciNetCrossRef
15.
Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. In: Annals of Discrete Mathematics, vol. 5, pp. 287–326. Elsevier (1979)
16.
Ishii, H., Martel, C., Masuda, T., Nishida, T.: A generalized uniform processor system. Oper. Res. 33(2), 346–362 (1985)MATHCrossRef
17.
Jegelka, S., Bach, F., Sra, S.: Reflection methods for user-friendly submodular optimization. In: Advances in Neural Information Processing Systems, pp. 1313–1321 (2013)
18.
Kim, G., Xing, E.P., Fei-Fei, L., Kanade, T.: Distributed cosegmentation via submodular optimization on anisotropic diffusion. In: 2011 International Conference on Computer Vision, pp. 169–176. IEEE (2011)
19.
Krause, A., Golovin, D.: Submodular function maximization (2014)
20.
Masdari, M., Salehi, F., Jalali, M., Bidaki, M.: A survey of pso-based scheduling algorithms in cloud computing. J. Netw. Syst. Manag. 25(1), 122–158 (2017)CrossRef
21.
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions–i. Math. Program. 14(1), 265–294 (1978)MathSciNetMATHCrossRef
22.
Nowicki, E., Zdrzałka, S.: A survey of results for sequencing problems with controllable processing times. Discret. Appl. Math. 26(2–3), 271–287 (1990)MathSciNetMATHCrossRef
23.
Ou, J., Zhong, X., Wang, G.: An improved heuristic for parallel machine scheduling with rejection. Eur. J. Oper. Res. 241(3), 653–661 (2015)MathSciNetMATHCrossRef
24.
Pei, J., Pardalos, P.M., Liu, X., Fan, W., Yang, S.: Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan. Eur. J. Oper. Res. 244(1), 13–25 (2015)MathSciNetMATHCrossRef
25.
Shabtay, D., Kaspi, M.: Minimizing the total weighted flow time in a single machine with controllable processing times. Comput. Oper. Res. 31(13), 2279–2289 (2004)MathSciNetMATHCrossRef
26.
Shabtay, D., Steiner, G.: A survey of scheduling with controllable processing times. Discret. Appl. Math. 155(13), 1643–1666 (2007)MathSciNetMATHCrossRef
27.
Shakhlevich, N.V., Shioura, A., Strusevich, V.A.: Single machine scheduling with controllable processing times by submodular optimization. Int. J. Found. Comput. Sci. 20(02), 247–269 (2009)MathSciNetMATHCrossRef
28.
Shakhlevich, N.V., Strusevich, V.A.: Pre-emptive scheduling problems with controllable processing times. J. Sched. 8(3), 233–253 (2005)MathSciNetMATHCrossRef
29.
Shakhlevich, N.V., Strusevich, V.A.: Preemptive scheduling on uniform parallel machines with controllable job processing times. Algorithmica 51(4), 451–473 (2008)MathSciNetMATHCrossRef
30.
Shioura, A., Shakhlevich, N.V., Strusevich, V.A.: A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines. SIAM J. Discret. Math. 27(1), 186–204 (2013)MathSciNetMATHCrossRef
31.
Shioura, A., Shakhlevich, N.V., Strusevich, V.A.: Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times. Math. Program. 153(2), 495–534 (2015)MathSciNetMATHCrossRef
32.
Shioura, A., Shakhlevich, N.V., Strusevich, V.A.: Energy saving computational models with speed scaling via submodular optimization. In: Proceedings of Third International Conference on Green Computing, Technology and Innovation, pp. 7–18 (2015)
33.
Shioura, A., Shakhlevich, N.V., Strusevich, V.A.: Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines. INFORMS J. Comput. 28(1), 148–161 (2016)MathSciNetMATHCrossRef
34.
35.
Shioura, A., Shakhlevich, N.V., Strusevich, V.A.: Machine speed scaling by adapting methods for convex optimization with submodular constraints. INFORMS J. Comput. 29(4), 724–736 (2017)MathSciNetCrossRef
36.
Shioura, A., Shakhlevich, N.V., Strusevich, V.A.: Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches. Eur. J. Oper. Res. 266(3), 795–818 (2018)MathSciNetMATHCrossRef
37.
38.
Vickson, R.: Two single machine sequencing problems involving controllable job processing times. AIIE Trans. 12(3), 258–262 (1980)MathSciNetCrossRef
39.
Wang, J., Qiao, C., Yu, H.: On progressive network recovery after a major disruption. In: 2011 Proceedings IEEE INFOCOM, pp. 1925–1933. IEEE (2011)
40.
Wang, S., Liu, M.: A branch and bound algorithm for single-machine production scheduling integrated with preventive maintenance planning. Int. J. Prod. Res. 51(3), 847–868 (2013)CrossRef
41.
Wang, S., Liu, M., Chu, C.: A branch-and-bound algorithm for two-stage no-wait hybrid flow-shop scheduling. Int. J. Prod. Res. 53(4), 1143–1167 (2015)CrossRef
42.
Wang, Y., Liu, Y., Kirschen, D.S.: Scenario reduction with submodular optimization. IEEE Trans. Power Syst. 32(3), 2479–2480 (2016)CrossRef
43.
Wolsey, L.A., Nemhauser, G.L.: Integer and Combinatorial Optimization, vol. 55. Wiley, Hoboken (1999)MATH
44.
Yin, Y., Wang, Y., Cheng, T., Wang, D.J., Wu, C.C.: Two-agent single-machine scheduling to minimize the batch delivery cost. Comput. Ind. Eng. 92, 16–30 (2016)CrossRef
45.
Zhang, H., Vorobeychik, Y.: Submodular optimization with routing constraints. In: Thirtieth AAAI Conference on Artificial Intelligence (2016)
46.
Metadata
Title
A Review for Submodular Optimization on Machine Scheduling Problems
Author
Siwen Liu
Copyright Year
2020
Book
Complexity and Approximation

Print ISBN: 978-3-030-41671-3

Electronic ISBN: 978-3-030-41672-0

Copyright Year: 2020

DOI
https://doi.org/10.1007/978-3-030-41672-0_16

Premium Partner

    Image Credits