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:
Introduction Read chapter Read first chapter

2019 | OriginalPaper | Chapter

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

Authors : Michael Z. Zgurovsky, Alexander A. Pavlov

Published in: Combinatorial Optimization Problems in Planning and Decision Making

Publisher: Springer International Publishing

Log in

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

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.

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 The Total Tardiness of Tasks Minimization on Identical Parallel Machines with Arbitrary Fixed Times of Their Start and a Common Due Date
next chapter The Four-Level Model of Planning and Decision Making
Footnotes
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.
 
Literature
1.
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.
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.
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.
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.
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.
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.
Sidney J.B.: Decomposition algorithm for single-machine sequencing with precedence relation and deferral costs. Oper. Res. 23, 283–298 (1975)MathSciNetCrossRef
8.
Pavlov, A.A. (ed.): Sistemy avtomatizirovannogo planirovaniya i dispetchirovaniya gruppovyh proizvodstvennyh processov (Системы автоматизированного планирования и диспетчирования групповых производственных процессов; Automated planning and dispatching of group production processes). Tekhnika, Kyiv (1990)
9.
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.
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)
Metadata
Title
The Total Weighted Completion Time of Tasks Minimization with Precedence Relations on a Single Machine
Authors
Michael Z. Zgurovsky
Alexander A. Pavlov
Copyright Year
2019
Book
Combinatorial Optimization Problems in Planning and Decision Making

Print ISBN: 978-3-319-98976-1

Electronic ISBN: 978-3-319-98977-8

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-319-98977-8_7

Premium Partners

    Image Credits