Skip to main content

2019 | OriginalPaper | Buchkapitel

7. The Total Weighted Completion Time of Tasks Minimization with Precedence Relations on a Single Machine

verfasst von : Michael Z. Zgurovsky, Alexander A. Pavlov

Erschienen in: Combinatorial Optimization Problems in Planning and Decision Making

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

We consider the problem of constructing a schedule for a single machine that minimizes the total weighted completion time of tasks when the restrictions on their processing order are given by an arbitrary oriented acyclic graph. The problem is NP-hard in the strong sense. Efficient polynomial algorithms for its solving are known only for cases when the oriented acyclic graph is a tree or a series-parallel graph. We give a new efficient PSC-algorithm of its solving. It is based on our earlier theoretical and practical results and solves the problem with precedence relations specified by an oriented acyclic graph of the general form. The first polynomial component of the PSC-algorithm contains sixteen sufficient signs of optimality. One of them will be statistically significantly satisfied at each iteration of the algorithm when solving randomly generated problem instances. In case when the sufficient signs of optimality fail, the PSC-algorithm is an efficient approximation algorithm. If the sufficient signs of optimality are satisfied at each iteration then the algorithm becomes exact. We present the empirical properties of the PSC-algorithm on the basis of statistical studies.

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!

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!

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!

Fußnoten
1
A schedule is feasible if it does not violate the precedence relations.
 
2
All fifteen SSOs are the signs of optimality for feasible subsequences obtained at the current iterations. We give more detailed justification for the implementation of insertion procedures for separate tasks or their constructions in the PSC-algorithm description (Sect. 7.3.4). We base the justification on an analysis of the priority and precedence relations. The presented logic of justifying the rules for constructing a p-ordered schedule in the PSC-algorithm causes the necessity of a more detailed investigation of these relations.
 
Literatur
1.
Zurück zum Zitat Zgurovsky, M.Z., Pavlov, A.A.: Prinyatie Resheniy v Setevyh Sistemah s Ogranichennymi Resursami (Принятие решений в сетевых системах с ограниченными ресурсами; Decision Making in Network Systems with Limited Resources). Naukova dumka, Kyiv (2010) (in Russian) Zgurovsky, M.Z., Pavlov, A.A.: Prinyatie Resheniy v Setevyh Sistemah s Ogranichennymi Resursami (Принятие решений в сетевых системах с ограниченными ресурсами; Decision Making in Network Systems with Limited Resources). Naukova dumka, Kyiv (2010) (in Russian)
2.
Zurück zum Zitat Aksionova, L.A.: Novye polinomial’nye podklassy trudnoreshaemoi zadachi “Minimizaciya summarnogo vzveshennogo momenta” dlia mnozhestva odnogo prioriteta (Новые полиномиальные подклассы труднорешаемой задачи «Минимизация суммарного взвешенного момента» для множества одного приоритета; New polynomial subclasses of the intractable problem “Minimizing the total weighted completion time” for one priority set). Upravl. Sist. i Mash. 182, 21–28 (2002) (in Russian) Aksionova, L.A.: Novye polinomial’nye podklassy trudnoreshaemoi zadachi “Minimizaciya summarnogo vzveshennogo momenta” dlia mnozhestva odnogo prioriteta (Новые полиномиальные подклассы труднорешаемой задачи «Минимизация суммарного взвешенного момента» для множества одного приоритета; New polynomial subclasses of the intractable problem “Minimizing the total weighted completion time” for one priority set). Upravl. Sist. i Mash. 182, 21–28 (2002) (in Russian)
3.
Zurück zum Zitat Pavlov, A.A. (ed.): Konstruktivnye Polinomialnye Algoritmy Resheniya Individualnyh Zadach iz Klassa NP (Конструктивные полиномиальные алгоритмы решения индивидуальных задач из класса NP; Constructive Polynomial Algorithms for Solving Individual Problems from the Class NP). Tehnika, Kyiv (1993) (in Russian) Pavlov, A.A. (ed.): Konstruktivnye Polinomialnye Algoritmy Resheniya Individualnyh Zadach iz Klassa NP (Конструктивные полиномиальные алгоритмы решения индивидуальных задач из класса NP; Constructive Polynomial Algorithms for Solving Individual Problems from the Class NP). Tehnika, Kyiv (1993) (in Russian)
4.
Zurück zum Zitat Pavlov, A.A. (ed.): Osnovy Sistemnogo Analiza i Proektirovaniya ASU (Основы системного анализа и проектирования АСУ; Fundamentals of System Analysis and Design of Automated Control Systems). Vyshcha Shkola, Kyiv (1991) (in Russian) Pavlov, A.A. (ed.): Osnovy Sistemnogo Analiza i Proektirovaniya ASU (Основы системного анализа и проектирования АСУ; Fundamentals of System Analysis and Design of Automated Control Systems). Vyshcha Shkola, Kyiv (1991) (in Russian)
5.
Zurück zum Zitat Pavlov, A.A., Aksionova, L.A.: Novye usloviya polinomial’noi sostavlyayushchei PDS-algoritma zadachi “Minimizaciya summarnogo vzveshennogo momenta” (Новые условия полиномиальной составляющей ПДС-алгоритма задачи «Минимизация суммарного взвешенного момента»; New conditions for the polynomial component of PSC-algorithm for the problem “Minimization of the total weighted completion time”). Probl. Programmir. 2001(1), 69–75 (2001) (in Russian) Pavlov, A.A., Aksionova, L.A.: Novye usloviya polinomial’noi sostavlyayushchei PDS-algoritma zadachi “Minimizaciya summarnogo vzveshennogo momenta” (Новые условия полиномиальной составляющей ПДС-алгоритма задачи «Минимизация суммарного взвешенного момента»; New conditions for the polynomial component of PSC-algorithm for the problem “Minimization of the total weighted completion time”). Probl. Programmir. 2001(1), 69–75 (2001) (in Russian)
6.
Zurück zum Zitat Pavlov, A.A., Pavlova, L.A.: Osnovy metodologii proektirovaniya PDS-algoritmov dlya trudnoreshaemyh kombinatornyh zadach (Основы методологии проектирования ПДС-алгоритмов для труднорешаемых комбинаторных задач; Fundamentals of PDC-algorithms design methodology for intractable combinatorial problems). Probl. Inform. i Upravl. 4, 135–141 (1995) (in Russian) Pavlov, A.A., Pavlova, L.A.: Osnovy metodologii proektirovaniya PDS-algoritmov dlya trudnoreshaemyh kombinatornyh zadach (Основы методологии проектирования ПДС-алгоритмов для труднорешаемых комбинаторных задач; Fundamentals of PDC-algorithms design methodology for intractable combinatorial problems). Probl. Inform. i Upravl. 4, 135–141 (1995) (in Russian)
7.
Zurück zum Zitat Sidney J.B.: Decomposition algorithm for single-machine sequencing with precedence relation and deferral costs. Oper. Res. 23, 283–298 (1975)MathSciNetCrossRef Sidney J.B.: Decomposition algorithm for single-machine sequencing with precedence relation and deferral costs. Oper. Res. 23, 283–298 (1975)MathSciNetCrossRef
8.
Zurück zum Zitat Pavlov, A.A. (ed.): Sistemy avtomatizirovannogo planirovaniya i dispetchirovaniya gruppovyh proizvodstvennyh processov (Системы автоматизированного планирования и диспетчирования групповых производственных процессов; Automated planning and dispatching of group production processes). Tekhnika, Kyiv (1990) Pavlov, A.A. (ed.): Sistemy avtomatizirovannogo planirovaniya i dispetchirovaniya gruppovyh proizvodstvennyh processov (Системы автоматизированного планирования и диспетчирования групповых производственных процессов; Automated planning and dispatching of group production processes). Tekhnika, Kyiv (1990)
9.
Zurück zum Zitat Pavlov, A.A., Pavlova, L.A.: About one subclass of polynomially solvable problems from class “Sequencing jobs to minimize total weighted completion time subject to precedence constraints”. Vestn. Mezhdunar. Solomon. Univer. 1999(1), 109–116 (1999) Pavlov, A.A., Pavlova, L.A.: About one subclass of polynomially solvable problems from class “Sequencing jobs to minimize total weighted completion time subject to precedence constraints”. Vestn. Mezhdunar. Solomon. Univer. 1999(1), 109–116 (1999)
10.
Zurück zum Zitat Zgurovsky, M.Z., Pavlov, O.A., Misura, E.B. PDS-algoritmy i trudnoreshaemye zadachi kombinatornoi optimizacii (ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации; PDC-algorithms and intractable combinatorial optimization problems). Syst. Res. and Inform. Technol. 2009(4), 14–31 (2009) (in Russian) Zgurovsky, M.Z., Pavlov, O.A., Misura, E.B. PDS-algoritmy i trudnoreshaemye zadachi kombinatornoi optimizacii (ПДС-алгоритмы и труднорешаемые задачи комбинаторной оптимизации; PDC-algorithms and intractable combinatorial optimization problems). Syst. Res. and Inform. Technol. 2009(4), 14–31 (2009) (in Russian)
Metadaten
Titel
The Total Weighted Completion Time of Tasks Minimization with Precedence Relations on a Single Machine
verfasst von
Michael Z. Zgurovsky
Alexander A. Pavlov
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-319-98977-8_7

    Marktübersichten

    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.