Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/24567
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorGawiejnowicz, Stanisław. Promotor-
dc.contributor.authorPrzybylski, Bartłomiej-
dc.date.accessioned2019-05-13T07:24:59Z-
dc.date.available2019-05-13T07:24:59Z-
dc.date.issued2019-
dc.identifier.urihttp://hdl.handle.net/10593/24567-
dc.descriptionWydział Matematyki i Informatykipl
dc.description.abstractW rozprawie rozważa się dwa modele szeregowania zadań z ograniczeniami kolejnościowymi i zmiennymi czasami wykonywania na wielu równoległych maszynach. W przypadku pierwszego modelu, w którym zadania jednostkowe mają pozycyjno-zależne czasy wykonywania, udowodniono własności pewnej transformacji oraz podano warunki, przy których transformacja ta pozwala uzyskać w czasie liniowym uszeregowanie optymalne dla uogólnionych zadań jednostkowych, o ile dane jest odpowiednie uszeregowanie optymalne dla zadań o stałych czasach wykonywania. Na tej podstawie pokazano, w jaki sposób można rozwiązać w wielomianowym czasie wybrane problemy rozważanego typu. Zaprezentowano także niezależne od tej transformacji wielomianowe algorytmy dla dwumaszynowych problemów szeregowania uogólnionych zadań jednostkowych z ograniczeniami kolejnościowymi w postaci łańcucha. W przypadku drugiego modelu, czasy wykonywania zadań opisane są całkami Riemanna o granicach zależnych od sumy podstawowych czasów wykonania wcześniejszych zadań. Skonstruowano i opisano własności transformacji związanej z tym modelem, a następnie wykorzystano ją do pokazania pseudowielomianowych rozwiązań problemów z czasami wykonywania zadań opartymi na całkach. Wyniki i pojęcia dotyczące obu modeli zilustrowano przykładami. Pokazano także przykłady otwartych problemów i wskazano na trudności związane z ich rozwiązaniem.pl
dc.description.abstractIn this dissertation, we consider two models of parallel-machine scheduling of precedence-constrained jobs with variable processing times. In case of the first model, in which unit jobs have position-dependent processing times, we introduce a certain transformation and prove its properties. We also show the conditions under which this transformation generates, in linear time, an optimal schedule for generalized unit-time jobs, provided that an optimal schedule for jobs with fixed processing times is known. Based on these results, we show how to solve several of the considered problems in polynomial time. We also present polynomial algorithms for two-machine scheduling problems with generalized unit-time jobs and with precedence constraints in a form of a chain. In case of the second model, job processing times are described by proper Riemann integrals with limits depending on the sum of processing times of jobs executed earlier. We introduce a transformation related to this model and present its properties. This transformation is used to present pseudo-polynomial algorithms for several problems with integral-based processing times. The results and notions concerning both the above models are illustrated with examples. We also present some open problems and point out the difficulties associated with their solution.pl
dc.language.isoengpl
dc.rightsinfo:eu-repo/semantics/restrictedAccesspl
dc.subjectszeregowanie zadańpl
dc.subjectschedulingpl
dc.subjectmaszyny równoległepl
dc.subjectparallel machinespl
dc.subjectograniczenia kolejnościowepl
dc.subjectprecedence constraintspl
dc.subjectzmienne czasy wykonywaniapl
dc.subjectvariable processing timespl
dc.titleSzeregowanie uogólnionych zadań jednostkowych na maszynach równoległychpl
dc.title.alternativeParallel-machine scheduling of generalized unit-time jobspl
dc.typeDysertacjapl
Appears in Collections:Doktoraty (WMiI)
Doktoraty 2010-2021 /dostęp ograniczony, możliwy z komputerów w Bibliotece Uniwersyteckiej/

Files in This Item:
File Description SizeFormat 
PhD_Bartlomiej_Przybylski.pdf
  Restricted Access
2.12 MBAdobe PDFView/Open
Show simple item record



Items in AMUR are protected by copyright, with all rights reserved, unless otherwise indicated.