Wyniki wyszukiwania - Biblioteka Nauki

1

Rozwiązywanie dyskretno-ciągłych problemów rozdziału zasobów przez dyskretyzację zasobu ciągłego

100%

Józefowska J. , Mika M. , Różycki R. , Waligóra G. , Węglarz J.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

tom z. 129

221-229

PL

W artykule rozważa się dyskretno-ciągły problem rozdziału zasobów. W problemach tego typu do wykonania zadań konieczne są jednocześnie zasoby ciągłe i dyskretne, przy czym wszystkie zasoby są odnawialne. Szybkość wykonania każdej czynności zależy od przydzielonej jej w danej chwili ilości zasobu ciągłego. Czynności są niepodzielne, a celem jest minimalizacja długości uszeregowania. W pracy zaproponowano metodę rozwiązania polegającą na transformacji powyższego problemu do klasycznego problemu rozdziału zasobów z wieloma sposobami wykonywania czynności.

EN

In this paper a discrete-continuous project scheduling problem is considered. In this problem activities simultaneously require for their processing discrete and continuous resources. The processing rate of each activity depends on the amount of the continuous resource allotted to this activity at a time. All the resources are renewable ones. The activities are nonpreemtable and the objective is to minimize the makespan. Discretization of this problem leading to a classical (i.e. discrete) project scheduling problem in the multimode version is presented.

2

Minimalizacja sumarycznej ilości zużytego zasobu w problemie szeregowania zadań o dynamicznych modelach terminów dostępności

100%

Janiak A. , Słoniński P.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

tom z. 129

179-190

PL

W pracy zaprezentowano rozwiązanie problemu minimalizacji sumarycznej ilości zużytego zasobu przy dynamicznych (różniczkowych) modelach terminów dostępności zadań oraz przy ograniczeniu na czas zakończenia wykonywania wszystkich zadań. Wykazano szereg istotnych własności rozważanego problemu (między innymi dotyczących postaci funkcji rozdziału zasobu). Bazując na udowodnionych własnościach podano konstrukcję algorytmu szeregowania zadań na maszynie krytycznej oraz przydział zasobu do terminów dostępności zadań, który zapewnia zakończenie wykonywania zadań w ustalonym czasie minimalizując ilość zużytego na ten cel zasobu.

EN

The aim of this contribution is to present a solution of the problem of minimizing total amount of resource consumed in the resource allocation and scheduling problem with dynamic (differential) models of job release dates. There is also constraint set on the time of finishing processing of all the jobs in this problem. Many important properties of this problem have been proven (e.g. those concerning the character of the resource allocation function). The presented scheduling algorithm is based on the properties proven in this paper. There are also given some generalizations of the considered problem.

3

Metody przeszukiwań dyskretnych przestrzeni rozwiązań

63%

Bożejko W. , Smutnicki C.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

tom z. 131

25-35

PL

Proponujemy wykorzystanie graficznej reprezentacji przestrzeni rozwiązań problemów kombinatorycznych do badania własności tych problemów i analizy algorytmów rozwiązywania. Szczegółowo wprowadzane i dyskutowane są miary odległości rozwiązań dla przestrzeni permutacji oraz jej odwzorowania w euklidesowe przestrzenie 1,2,3D. Technikę zilustrowano na przykładzie algorytmów poszukiwań lokalnych dla jednomaszynowego problemu szeregowania z kryterium średniego opóźnienia zadań.

EN

We propose to apply the graphic representation of the solution space of combinatorial problems for the analysis properties of the problem and solution algorithms. Particularly, there have been introduced and discussed distance measures between solutions in the space of permutations and its transformation into Euclidian spaces 1,2,3D. Local search algorithms for single-machine scheduling problem with the mean tardiness criterion have illustrated this technique.

4

Przybliżone algorytmy rozwiązywania jednomaszynowego problemu szeregowania zadań o zmiennych wartościach

63%

Bachman A. , Janiak A. , Kozik A. , Winczaszek M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

tom z. 134

23-32

PL

W mniejszej pracy rozpatrzono jednomaszynowy problem szeregowania zadań przy kryterium maksymalizacji sumy wartości zadań. Wartość zadania jest opisana malejącą funkcją potęgową zależną od jego czasu zakończenia wykonywania. Dla badanego problemu skonstruowano i porównano eksperymentalnie szereg algorytmów heurystycznych typu konstrukcyjnego i typu "popraw".

EN

The paper deals with a single machine scheduling problem where the sum of job values should be maximized. A job value is given as a exponentially decreasing function dependent on its completion time. We experimentally compared some heuristic algorithms constructed to solve the problem under consideration.

5

Scheduling coupled tasks on a single processor

63%

Błażewicz J. , Ecker K. , Kis T. , Tanaś M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

tom z. 134

53-66

EN

This paper considers a problem of coupled task scheduling on one processor, where all processing times are equal to 1, the gap has exact length h, precedence constraints are strict and the criterion is to minimize the schedule length. This problem is introduced e.g. in systems controlling radar operations. We show that the general problem is NP-hard. This paper also shows a fast approximation algorithm for chain precedence constraints.

PL

W referacie zaprezentowano problem szeregowania zadań sprzężonych na jednym procesorze, z jednostkowymi czasami wykonywania operacji, stałą długością przerwy pomiędzy operacjami, gdzie celem jest minimalizacja długości uszeregowania. Problem ten często występuje w praktyce w systemach sterowania urządzeniami radarowymi. W referacie pokazujemy NP-trudność problemu w przypadku ogólnych ograniczeń kolejnościowych oraz szybki algorytm aproksymacyjny dla ograniczeń kolejnościowych typu "łańcuch".

6

Jednomaszynowy problem szeregowania z potęgowymi funkcjami zmiany wartości zadań

63%

Bachman A. , Janiak A. , Kozik A. , Winczaszek M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

tom z. 134

13-22

PL

W niniejszej pracy rozpatrzono jednomaszynowy problem szeregowania, w którym wartości zadań zależą od momentów zakończenia ich wykonywania i są opisane malejącymi funkcjami potęgowymi. Rozwiązanie problemu polega na znalezieniu takiego uszeregowania, dla którego suma wartości zadań jest maksymalna. Problem sformułowany powyżej znajduje praktyczne zastosowanie np. w procesie odzysku surowców (np. części ze starych komputerów, samochodów), planowaniu sprzedaży, czy też magazynowaniu i transporcie produktów psujących się. Złożoność obliczeniowa rozpatrywanego problemu jest wciąż zagadnieniem otwartym, jednakże w pracy wykazano szereg własności określających optymalne rozwiązanie badanego problemu. Własności te zostały wykorzystane przy konstrukcji algorytmu opartego na metodzie podziału i ograniczeń. Dla skonstruowanego algorytmu przeprowadzono eksperyment obliczeniowy w celu określenia jego efektywności.

EN

The paper deals with a single machine scheduling problem, where job value is characterized by an exponential function dependent on job completion time. The objective is to find a sequence of jobs for which the sum of job values calculated at their completion times is maximized. The computational complexity status of the considered problem is still an open question, however it seams to be NP-hard. We proved some properties characterizing the optimal solution of the problem stated above. Based on these properties we constructed a branch and bound algorithm which quality was experimentally analyzed.

7

Szeregowanie zadań elastycznych

63%

Błażewicz J. , Kovalyov M. , Machowiak M. , Trystram D. , Węglarz J.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

tom z. 134

67-79

PL

Przedstawiono tutaj problem szeregowania n niezależnych zadań w systemie procesorów równoległych. Zadania są elastyczne, tj. zadanie może być wykonywane przez kilka procesorów jednocześnie oraz prędkość wykonywania zadania jest nieliniową funkcją od ilości procesorów przydzielonych do niego. Całkowita liczba procesorów w systemie wynosi m i jest to górna granica liczby procesorów, które mogą być używane przez wszystkie zadania w tym samym czasie. Dodatkowym założeniem jest podzielność zadań oraz możliwość zmiany liczby procesorów przydzielonych do zadania w trakcie jego wykonywania. Celem jest znalezienie uszeregowania, dla którego czas zakończenia wszystkich zadań jest najkrótszy z możliwych. Prezentowany jest prosty algorytm o złożoności 0(n), rozwiązujący ten problem w przypadku, kiedy wszystkie funkcje prędkości wykonywania są wypukłe. Jeżeli funkcje te są wszystkie wklęsłe, przedstawiono algorytm pakowania prostokątów (PACK), który rozwiązuje ten problem w czasie wielomianowym.

EN

The problem of optimal scheduling n independent tasks on a parallel processor system is studied. The tasks are malleable, i.e. a task may be executed by several processors simultaneously and the processing speed of a task is a non-linear function of the number of processors allotted to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the tasks are preemptable and the number of processors allotted to one task may change during its execution. The objective is to find a schedule for which the makespan, is minimized. An 0(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave the rectangles packing (PACK) algorithm is presented, which solves the problem in polynomial time.

8

Szeregowanie zadań o znanej sekwencji z uwzględnieniem kosztów wyprzedzeń i opóźnień

63%

Bauman J. , Józefowska J.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

tom z. 134

43-52

PL

W pracy rozważa się problem szeregowania zadań, o dowolnych oczekiwanych terminach zakończenia, na jednej maszynie z kryterium minimalizacji kosztów nieterminowości wykonania zadań. Funkcje kosztów wyprzedzeń i opóźnień są liniowe, asymetryczne i indywidualne dla poszczególnych zadań. Zaprezentowano algorytm o złożoności O(nlogn) znajdujący optymalne uszeregowanie danej sekwencji zadań. Koncepcja polega na zastosowaniu funkcji określającej koszt modyfikacji uszeregowania, aktualizowanej po uszeregowaniu kolejnego zadania.

EN

We consider one-machine scheduling problem with individual due dates to minimize earliness-tardiness cost. The functions of the earliness-tardiness cost are linear, asymmetric and task dependent. We propose an 0(nlogn) algorithm to find an optimal schedule for a given sequence of jobs. A concept of a schedule modification cost function updated after adding each task is used.

9

Jednomaszynowy problem szeregowania zadań o zmiennych wartościach

63%

Bachman A. , Janiak A. , Krysiak T.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

tom z. 134

33-42

PL

W pracy rozpatrzono jednomaszynowy problem szeregowania, w którym wartości zadań są opisane potęgową funkcją zależną od czasów zakończenia ich wykonywania. Rozpatrzono kryterium maksymalizacji sumy wartości zadań. Analizowany problem został przeformułowany w taki sposób, że zamiast maksymalizacji sumy wartości zadań, optymalizowanym kryterium jest minimalizacja sumy strat ich wartości. Określono złożoność obliczeniową ogólnej wersji problemu wykorzystując transformację z Problemu Podziału. Dla szczególnych przypadków badanego problemu wykazano szereg własności określających optymalne rozwiązanie.

EN

The paper deals with a single machine scheduling problem where job values are characterized by an exponential function dependent on the completion time of job execution. Maximization of the total values is considered as an optimization criterion. However, to simplify the considerations, we reformulate the problem so that the total lost of job values should be minimized. We prove that the general version of the problem stated above is NT-hard. The proof is done from the well known Partition Problem. We construct some optimal algorithms which solve special cases of the general problem in polynomial time.

10

Analiza jednomaszynowych problemów szeregowania zadań z czasowo zależnymi czasami wykonywania

63%

Bachman A. , Janiak A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

1998

|

tom z. 123

11-22

PL

W pracy dokonano przeglądu literaturowego jednomaszynowych problemów szeregowania zadań, których czasy wykonywania są pewnymi funkcjami zależnymi od momentu rozpoczęcia ich wykonywania. Autorzy dokonali porównania różnych modeli opisujących rozpatrywaną zależność czasu wykonywania zadania ze względu na stosowane kryteria.

EN

In the paper we analysed the single machine scheduling problems with start time dependent processing times. We presented the complete state of art in this area containing thirty three articles from last twenty years. The notation of the presented models have been unified. We described also the techniques used to solve considered problem with some remarkable results.

11

Zagadnienie szeregowania zadań w systemach taśmowych ze specyficznymi wymaganiami

63%

Grabowski J. , Pempera J.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

1998

|

tom z. 125

30-36

PL

W niniejszej pracy przedstawia się szereg algorytmów heurystycznych dla zagadnienia kolejnościowego taśmowego z wymaganiami typu 'bez czekania' oraz z terminami dostępności zadań. Przedstawiono wyniki obliczeniowe algorytmów oraz analizę porównawczą.

EN

This paper deals with sequencing of jobs in the flow-shop problem with release date and no-wait requirements. This problem can formulated as follows. There is the set of jobs J1,J2,.......Jn, each of n jobs has to be processed on machines M1, M2........,Mm in that order. A machine can process only one job at a time and preemption of a job is not permitted. Furthermore, between the pairs of machines (Mk, Mk+1), k+1,2,...m-1, there are 'no wait' requirements. The purpose of the optimization is to find such a schedule of jobs on machines that maximum completion time of jobs is minimized. Our problem belongs to the class of NP-hard problems what justifies searching for heuristic algorithms based on statistical and dynamical priority rules. Finally, the computational results and discussion of the performance of algorithms are presented.

12

Algorytm symulowanego wyżarzania dla problemu rozdziału zasobów z wieloma sposobami wykonywania czynności

63%

Józefowska J. , Mika M. , Różycki R. , Waligóra G. , Węglarz J.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

tom z. 129

211-220

PL

W pracy rozważa się problem rozdziału zasobów z wieloma sposobami wykonywania czynności. Celem jest znalezienie takiego uszeregowania dopuszczalnego, które minimalizuje czas trwania projektu. Zaproponowano algorytm symulowanego wyżarzania dla tego problemu oraz przedstawiono wyniki eksperymentu obliczeniowego.

EN

In this paper a multi-mode resource-constrained project scheduling problem is considered. The objective is to find a feasible solution which minimizes the makespan. A simulated annealing algorithm is developed to solve this problem and a performance analysis of this algorithm is presented on the basis of a comprehensive computational experiment.

13

Jednomaszynowy problem szeregowania zadań czasowo i zasobowo zależnych przy kryterium minimalizacji czasu zakończenia wykonania zadań

63%

Bachman A. , Janiak A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

tom z. 129

23-32

PL

W niniejszej pracy wykazano NP-zupełność jednomaszynowego problemu szeregowania zadań z czasami wykonywania zależnymi zarówno od momentu rozpoczęcia wykonywania, jak również od ilości przydzielonego zasobu przy kryterium minimalizacji czasu zakończenia wykonania zadań.

EN

The paper deals with a single machine scheduling problem, in which the job processing times are start time and resource dependent. We prove that this problem is NP-complete for the makespan minimization.

14

Szeregowanie zadań z optymalizacją średniego czasu zakończenia operacji w systemie otwartym

63%

Piwakowski K.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

tom z. 129

315-320

PL

W niniejszej pracy rozważamy graniczne przypadki otwartego systemu obsługi zadań niepodzielnych NOSS (Non-Preemptive Open-Shop Scheduling), dla których problem szeregowania z optymalizacją średniego czasu zakończenia operacji przestaje być wielomianowy i staje się NP-trudny. W szczególności dowodzimy, że wielomianowy przypadek pojedynczego zadania składającego się z n operacji wykonywanych na n różnych procesorach staje się NP-trudny po dołączeniu drugiego zadania, składającego się z jednej operacji wykonywanej na jednym (z góry określonym) procesorze.

EN

In this paper we consider some special cases of the Non-Preemptive Open-Shop Scheduling model with the average completion time of all operations as the optimality criterion. In particular we prove that the polynomial solvable case where there is only one job consisting of n operations, becomes NP-hard when another job with only one operation sharing one of the processors is added.

15

Podzielne szeregowanie zadań dwuprocesorowych na maszynach dedykowanych w celu minimalizacji sumy czasów zakończenia

63%

Małafiejski M. , Kuszner Ł. , Kubale M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

tom z. 134

313-325

PL

W pracy rozważamy deterministyczne szeregowanie zadań dwuprocesorowych na maszynach dedykowanych, które minimalizuje sumę czasów zakończenia, przy czym dopuszcza się możliwość przerwania wykonywania zadania i ponownego wznowienia obsługi z pomijalnie małym kosztem. W standardowej notacji ten problem zapisujemy jako P|fix j = 2, pmtn| Sigma Cj. Wiadomo, że tak postawione zagadnienie jest problemem silnie NP-trudnym. W pracy badamy złożoność obliczeniową problemu, ograniczając liczbę maszyn. Podajemy wielomianowy algorytm dla problemu P4|fix j = 2, pmtn|Sigma Cj.

EN

In this paper we consider a problem of preemptive scheduling of biprocessor tasks on dedicated processors in order to minimize the sum of completion times. Using the standard notation this problem is denoted as P|fix j = 2, pmtn|Sigma Cj. This problem is strongly NP-hard. We analyze the subproblems obtained by reducing the number of processors. We give an exact polynomial algorithm for open problem P4|fix j = 2, pmtn|Sigma Cj.

16

Minimalizacja sumy ważonych czasów zakończenia wykonywania zadań w jednomaszynowym problemie szeregowania z czasami przezbrojeń zależnymi od zasobów

63%

Janiak A. , Krysiak T. , Lichtenstein M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

tom z. 134

219-232

PL

W niniejszej pracy rozpatrywany jest jednomaszynowy problem szeregowania zadań z przezbrojeniami sekwencyjnie niezależnymi i ograniczeniem technologii grupowej. Przyjęto, że czasy przezbrojeń opisane są przez nierosnące, liniowe funkcje zależne od dodatkowego zasobu podzielnego w sposób ciągły lub dyskretny. Jako kryterium optymalności przyjęto minimalizację ważonych czasów zakończenia wykonywania zadań. Wykazano, że problem z zasobem podzielnym w sposób dyskretny jest problemem NP-trudnym. Ponadto, wykazano szereg własności badanego problemu oraz zaproponowano kilka algorytmów przybliżonych, których efektywność zbadano eksperymentalnie.

EN

In the paper a single machine scheduling problem with sequence- independent setup times and group technology is considered. The setup times are given as some nonincreasing, linear functions dependent on additional continuously or discretely-divisible resources. The scheduling criterion is the minimization of the total weighted completion time. It is shown that the problem with discretely-divisible resources is NP-hard. Additionally, some specific properties of the problem are proven, and several approximation algorithms are proposed. The efficiency of these algorithms is verified experimentally.

17

Szeregowanie zadań z przezbrojeniami i czasami wykonywania zadań zależnymi od zasobów - minimalizacja sumy ważonych czasów zakończenia wykonywania zadań

63%

Janiak A. , Krysiak T. , Lichtenstein M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

tom z. 134

209-218

PL

W pracy rozpatrzono dwa jednomaszynowe problemy szeregowania przy kryterium minimalizacji sumy ważonych czasów zakończenia wykonywania zadań oraz ograniczeniu na całkowitą ilość dostępnego zasobu. W pierwszym problemie czasy przezbrojeń są zależne od ilości przydzielonego zasobu, występuje tutaj także wymóg technologii grupowej. W drugim problemie czasy wykonywania zadań są zależne od zasobu, natomiast przezbrojenia są równe zero. Wykazano równoważność obu problemów dla malejącej funkcji liniowej opisującej zależność czasu przezbrojenia oraz czasu wykonywania od zasobu. Dla rozpatrywanych problemów wykazano szereg własności określających optymalne rozwiązania ich szczególnych przypadków oraz własności pomocnicze wykorzystane przy konstrukcji algorytmów heurystycznych rozwiązujących te problemy.

EN

The paper deals with two single machine scheduling problems considered for the sum of weighted completion times minimization. In the first problem, the setup times are resource-dependent and there is group technology restriction. In the second one the processing times are resource-dependent and the setup times are equal to zero. It is shown that both problems are equivalent if both the setup and processing times are decreasing resource dependent linear functions. We prove some properties for the considered problems, based on which some special cases of the considered problem can be solved optimally. These properties are also used to construct some heuristic algorithms solving the general cases of the problems under considerations. The efficiency of the heuristic algorithms is tested experimentally.

18

Wykorzystanie algorytmów ewolucyjnych do rozwiązania wybranego problemu szeregowania zadań z ruchomymi realizatorami

63%

Józefczyk J. , Thomas W.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

tom z. 134

233-242

PL

W pracy jest rozważane specyficzne, proste zagadnienie szeregowania zadań, w którym należy uwzględniać ruch realizatorów. Ograniczono się do szeregowania zadań niezależnych i niepodzielnych na realizatorach dowolnych w celu minimalizacji długości uszeregowania. Do rozwiązania sformułowanego problemu optymalizacyjnego zastosowano i przedstawiono dwie wersje algorytmu ewolucyjnego. Zaprezentowano wybrane rezultaty badań symulacyjnych, w których dokonano eksperymentalnej oceny rozpatrywanego algorytmu rozwiązania.

EN

Scheduling of manufacturing tasks on moving executors for a simple case is considered in the paper. The problem of independent and non-preemptive tasks as well as unrelated executors with makespan as the performance index is investigated. The corresponding optimization problem is formulated and solved using two versions of an evolutionary algorithm. The results of simulation experiments, which verify the quality of the solution algorithm, are given.

19

W pełni wielomianowy schemat aproksymacyjny dla pewnego problemu szeregowania zadań uwarunkowanych czasowo

63%

Ocetkiewicz K. M.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2008

|

tom T. 16

433-438

PL

W artykule tym rozważany jest następujący problem szeregowania zadań: dany jest jeden procesor, zbiór zadań j1...,jn, czas przetwarzania zadania i wynosi Pi = a + bisi, zaś celem jest minimalizacja całkowitego czasu wykonywania zadań. Przedstawiony został pełny wielomianowy schemat aproksymacyjny, który, o ile wszystkie współczynniki wydłużania zadań (bi) w instancji problemu są różne i większe od pewnej, ustalonej liczby u, pozwala znaleźć rozwiązanie l+epsilon przybliżone w czasie będącym wielomianem rozmiaru danych oraz odwrotności epsilonu.

EN

In this article a following time-dependent scheduling problem is considered: there is given one processor, a set of j1,...,jn, the processing time of the ith job is given by pi = a + bisi and our goal is to minimize total completion time. A fully polynomial time approximation scheme is proposed, that, providing all deterioration rates are greater than a certain constant u, allows us to find a solution that is not more than 1+epsilon times greater than the optimal one. The running time of this algorithm is expressed by a polynomial of the size of the input and a reciprocal of epsilon.

20

Optymalny dobór przedziałów czasowych zakończenia wykonywania zadań w wybranych jednomaszynowych problemach szeregowania

63%

Janiak A. , Marek M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2001

|

tom T. 5, z. 1/2

269-276

PL

W pracy rozpatrywane są problemy szeregowania należące do nowej klasy zagadnień, w których występują optymalizowane przedziały czasowe zakończenia wykonywania zadań. Wspomniane przedziały czasowe są uogólnieniem klasycznych pożądanych terminów zakończenia wykonywania zadań. Dobór tych przedziałów czasowych stanowi nowe zagadnienie, które nie było dotąd rozpatrywane w literaturze naukowej. Rozpatrywane w pracy dwa jednomaszynowe problemy szeregowania różnią się od siebie sposobem doboru parametrów charakteryzujących optymalizowane przedziały czasowe zakończenia wykonywania zadań. W obu przypadkach minimalizowane jest kryterium, które stanowi maksimum z trzech następujących wartości: maksymalne opóźnienie, maksymalne wcześniejsze wykonanie oraz funkcja wartości parametrów określających szerokości i położenie optymalizowanych przedziałów na osi czasu. Opierając się na wykazanych własnościach dla badanych problemów, skonstruowano dla nich optymalne algorytmy rozwiązania.

EN

The paper deals with single machine scheduling problems, in which a due interval should be assigned to each job. Due interval is a generalization of well known classical due date and describes a time interval, in which a job should be finished. Due interval assignment is completely new approach and to our knowledge has not been investigated in the scientific literature. We consider two single machine scheduling problems, in which different models of due intervals are introduced. The problem is to find a sequence of jobs and an assignment of due intervals to each job, which minimize the maximum of the following three parts: the maximum tardiness, the maximum earliness and the due interval parameters. Based on proved properties, we constructed the optimal solutions for both problems under considerations.