Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Performance Evaluation of Parfois Retailing Stores Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

An Exact and a Hybrid Approach for a Machine Scheduling Problem with Job Splitting

verfasst von : Luís Florêncio, Carina Pimentel, Filipe Alvelos

Erschienen in: Operational Research

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The unrelated parallel machine scheduling problem with job splitting and setup times is addressed in this paper.
A time-indexed integer programming formulation of the problem to minimize a weighted function of the processing occurring both before and after jobs’ due dates is proposed. Moreover, we apply to a suitable decomposition of the integer programming model a recently proposed framework for decomposable integer programming/combinatorial optimization problems (SearchCol, meta-heuristic search by column generation) based on the combination of column generation and meta-heuristics.
A problem specific heuristic to use in the column generation component of the SearchCol is developed. To evaluate the effectiveness of the models and the proposed algorithms, computational tests are performed.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel A Tool to Manage Tasks of R&D Projects
Nächstes Kapitel Testing Regularity on Linear Semidefinite Optimization Problems
Literatur
1.
Allahverdi, A., Gupta, J.N., Aldowaisan, T.: A review of scheduling research involving setup considerations. Omega 27(2), 219–239 (1999)CrossRef
2.
Allahverdi, A., Ng, C., Cheng, T., Kovalyov, M.: A survey of scheduling problems with setup times or costs. Eur. J. Oper. Res. 187(3), 985–1032 (2008)MATHMathSciNetCrossRef
3.
Alvelos, F., Sousa, A., Santos, D.: Combining column generation and metaheuristics. In: Talbi, E.G. (ed.) Hybrid Metaheuristics. Studies in Computational Intelligence, vol. 434, pp. 285–334. Springer, Berlin/Heidelberg (2013)CrossRef
4.
Blum, C., Puchinger, J., Raidl, G.R., Roli, A.: Hybrid metaheuristics in combinatorial optimization: a survey. Appl. Soft Comput. 11(6), 4135–4151 (2011)CrossRef
5.
Chen, J.F.: Scheduling on unrelated parallel machines with sequence-and machine-dependent setup times and due-date constraints. Int. J. Adv. Manuf. Technol. 44(11), 1204–1212 (2009)CrossRef
6.
Chen, J.F., Wu, T.H.: Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints. Omega 34(1), 81–89 (2006)CrossRef
7.
Dantzig, G., Wolfe, P.: Decomposition principle for linear programs. Oper. Res. 8, 101–111 (1960)MATHCrossRef
8.
Desaulniers, G., Desrosiers, J., Solomon, M.: Column Generation, vol. 5. Springer, New York (2005)MATHCrossRef
9.
Desrosiers, J., Lübbecke, M.: A primer in column generation. In: Column Generation, pp. 1–32. Springer, New York (2005)
10.
Fanjul-Peyro, L., Ruiz, R.: Scheduling unrelated parallel machines with optional machines and jobs selection. Comput. Oper. Res. 39, 1745–1753 (2012)MATHMathSciNetCrossRef
11.
Florêncio, L.: A searchcol algorithm for the unrelated parallel machine scheduling problem with job splitting. Master’s thesis, Universidade do Minho (2013)
12.
ILOG: IBM ILOG CPLEX Optimization Studio V12.2 (2010)
13.
Kim, D.W., Kim, K.H., Jang, W., Frank Chen, F.: Unrelated parallel machine scheduling with setup times using simulated annealing. Robot. Comput.-Integr. Manuf. 18(3), 223–231 (2002)CrossRef
14.
Kim, Y., Shim, S., Kim, S., Choi, Y., Yoon, H.: Parallel machine scheduling considering a job-splitting property. Int. J. Prod. Res. 42(21), 4531–4546 (2004)MATHCrossRef
15.
Lee, J.H., Yu, J.M., Lee, D.H.: A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness. Int. J. Adv. Manuf. Technol. 69(9–12), 2081–2089 (2013)CrossRef
16.
Liaw, C.F., Lin, Y.K., Cheng, C.Y., Chen, M.: Scheduling unrelated parallel machines to minimize total weighted tardiness. Comput. Oper. Res. 30(12), 1777–1789 (2003)MATHMathSciNetCrossRef
17.
Lin, Y., Pfund, M., Fowler, J.: Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems. Comput. Oper. Res. 38, 901–9016 (2011)MATHMathSciNetCrossRef
18.
Logendran, R., Subur, F.: Unrelated parallel machine scheduling with job splitting. IIE Trans. 36(4), 359–372 (2004)CrossRef
19.
Logendran, R., McDonell, B., Smucker, B.: Scheduling unrelated parallel machines with sequence-dependent setups. Comput. Oper. Res. 34(11), 3420–3438 (2007)MATHMathSciNetCrossRef
20.
Lopes, M.P., Carvalho, J.d.: A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times. Eur. J. Oper. Res. 176(3), 1508–1527 (2007)
21.
Nait, T.D., Yalaoui, F., Chu, C., Amodeo, L.: A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times. Int. J. Prod. Econ. 99(1), 63–73 (2006)CrossRef
22.
Park, T., Lee, T., Kim, C.O.: Due-date scheduling on parallel machines with job splitting and sequence-dependent major/minor setup times. Int. J. Adv. Manuf. Technol. 59(1), 325–333 (2012)CrossRef
23.
Pfund, M., Fowler, J.W., Gupta, J.N.: A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems. J. Chin. Inst. Ind. Eng. 21(3), 230–241 (2004)
24.
Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems, 2nd edn. Springer, New York (2002)
25.
26.
Rocha, P., Ravetti, M., Mateus, G., Pardalos, P.: Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times. Comput. Oper. Res. 35(4), 1250–1264 (2008)MATHMathSciNetCrossRef
27.
Rodriguez, F.J., Lozano, M., Blum, C., García-Martínez, C.: Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times. Comput. Oper. Res. 40, 1829–1841 (2013)MathSciNetCrossRef
28.
Sarıçiçek, İ., Çelik, C.: Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness. Appl. Math. Model. 35(8), 4117–4126 (2011)MATHMathSciNetCrossRef
29.
Shim, S.O., Kim, Y.D.: Minimizing total tardiness in an unrelated parallel-machine scheduling problem. J. Oper. Res. Soc. 58(3), 346–354 (2006)MathSciNetCrossRef
30.
Shim, S., Kim, Y.: A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property. Comput. Oper. Res. 35(3), 863–875 (2008)MATHMathSciNetCrossRef
31.
Talbi, E.G.: Hybrid Metaheuristics. Studies in Computational Intelligence, vol. 434. Springer, Berlin/Heidelberg (2013)
32.
Unlu, Y., Mason, S.: Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems. Comput. Ind. Eng. 58(4), 785–800 (2010)CrossRef
33.
Vallada, E., Ruiz, R.: A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. Eur. J. Oper. Res. 211(3), 612–622 (2011)MathSciNetCrossRef
34.
Wang, W.L., Wang, H.Y., Zhao, Y.W., Zhang, L.P., Xu, X.L.: Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm. Comput. Oper. Res. 40(5), 1196–1206 (2013)MathSciNetCrossRef
35.
36.
Yalaoui, F., Chu, C.: An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times. IIE Trans. 35(2), 183–190 (2003)CrossRef
37.
Yang, W.H.: Survey of scheduling research involving setup times. Int. J. Syst. Sci. 30(2), 143–155 (1999)MATHCrossRef
38.
Zhu, Z., Heady, R.: Minimizing the sum of earliness/tardiness in multi-machine scheduling: a mixed integer programming approach. Comput. Ind. Eng. 38(2), 297–305 (2000)CrossRef
Metadaten
Titel
An Exact and a Hybrid Approach for a Machine Scheduling Problem with Job Splitting
verfasst von
Luís Florêncio
Carina Pimentel
Filipe Alvelos
Copyright-Jahr
2015
Buch
Operational Research

Print ISBN: 978-3-319-20327-0

Electronic ISBN: 978-3-319-20328-7

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-20328-7_12

Premium Partner

    Bildnachweise