PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 23

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  problem jednomaszynowy
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available remote Worst-Case Analysis of an Approximation Algorithm for Single Machine Scheduling Problem
Grigoreva Natalia
Annals of Computer Science and Information Systems
|
2021
|
Vol. 25
221--225
EN
—The problem of minimizing the maximum delivery times while scheduling jobs on the single processor is a classical combinatorial optimization problem. This problem is denoted by 1|rj,qj|Cmax has many applications, and it is NP-hard in strong sense. The goal of this paper is to propose a new 3/2approximation algorithm, which runs in O(n log n) time. We proved that the bound of 3/2 is tight. To check the efficiency of the algorithm we tested it on random generated problems of up to 5000 jobs.
2
Problem dystrybucji z terminami dostaw
Bożejko W., Walczyński M., Wodecki M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 150
25-30
PL
W pracy przedstawiono algorytm oparty na metodzie przeszukiwania z tabu, rozwiązywania problemu dystrybucji z terminami dostaw. Jest on równoważny pewnemu jednomaszynowemu problemowi szeregowania, który w literaturze jest oznaczany przez 1|sij|ΣwiTi i należy do klasy problemów silnie NP-trudnych. Wykonano obliczenia na reprezentatywnej grupie danych, a otrzymane wyniki porównano z najlepszymi znanymi w literaturze.
EN
A tabu search algorithm is proposed in the paper to solve a distribution problem with due dates. It is equivalent to a single machine scheduling problem, which is described by 1|sij|ΣwiTi in the literature and it belongs to strongly NP-hard class. Calculations were done on representative group of test instances, obtained results were compared to the best known solutions from the literature.
3
Szeregowanie zadań z najwcześniejszymi i najpóźniejszymi terminami zakończenia
Bożejko W., Wodecki M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
27-32
PL
W pracy przedstawiamy algorytm przybliżony oparły na metodzie przeszukiwania z tabu dla rozwiązywania problemu szeregowania na jednej maszynie zadań, z najwcześniejszymi i najpóźniejszymi terminami zakończenia. W procedurze przeglądania sąsiedztwa (ograniczonego przez eliminację "złych" rozwiązań) stosujemy, jako kryterium wyboru, górne ograniczenie wartości funkcji celu (rozwiązując problem "bez przestojów maszyny").
EN
In the paper we present an algorithm which is based on the tabu method to solving single machine scheduling problem with earliness and tardiness penalties. We apply an upper bound as the criterion in the neighborhood searching (solving "no idle" problem).
4
Jednomaszynowy problem szeregowania zadań z przezbrojeniami
Bożejko W., Wodecki M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
21-26
PL
W pracy przedstawiamy algorytm populacyjny rozwiązywania jednomaszynowego problemu szeregowania zadań z przezbrojeniami, w którym należy zminimalizować sumę kosztów opóźnień. W literaturze jest on oznaczany przez 1 | s[ij] | sigma w[i]T[i] należy do klasy problemów silnie NP-trudnych. Wykonaliśmy obliczenia na reprezentatywnej grupie danych testowych, a otrzymane wyniki porównujemy z najlepszymi znanymi w literaturze. Dla wielu przykładów uzyskaliśmy poprawę najlepszych rozwiązań.
EN
In the paper we propose a population-based algorithm for solving single machine scheduling problem with total tardiness criterion and sequence-dependent setup times. It is represented by 1 | s[ij] | sigma w[i]T[i] in literature and it belongs to the strongly NP-hard class. Calculations on the representative group of benchmark instances were done and results were compared with the best known from literature. Obtained solutions were better than benchmark ones in many instances.
5
Wsadowe szeregowanie zadań jednostkowych na pojedynczym procesorze
Furmańczyk H., Żyliński P.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
127-137
PL
Problem wsadowego szeregowania zadań jednostkowych na jednej maszynie polega na przydzieleniu zadań kompatybilnych do wsadów, które będą wykonywane w oddzielnych chwilach czasu. W pracy zajmiemy się przypadkiem, w którym graf modelujący problem jest grafem porównywalnym, split grafem albo kografem, a wielkość wsadu jest ograniczona przez stałą p. Naszym celem jest takie uszeregowanie zadań, aby łączny czas ich wykonywania był jak najmniejszy. Na koniec omówimy zastosowanie heurystyki wyżarzania symulowanego dla rozważanego problemu w przypadku ogólnym.
EN
Problem of scheduling on a single batch processing machine reduces to attaching compatible jobs to batches. At most one batch can be treated at a time. In this paper we consider cases which are modeled by a graph which is a comparability graph, split graph or a cograph and the capacity of a batch is bounded by a constant p. Our aim is to schedule the jobs in such way that the makespan is as small as possible. In the last section we attemp to solve this problem in general case with the simulated annealing algorithm.
6
Szeregowanie zadań z przezbrojeniami i czasami wykonywania zadań zależnymi od zasobów - minimalizacja sumy ważonych czasów zakończenia wykonywania zadań
Janiak A., Krysiak T., Lichtenstein M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
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.
7
Szeregowanie zadań o znanej sekwencji z uwzględnieniem kosztów wyprzedzeń i opóźnień
Bauman J., Józefowska J.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
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.
8
Przybliżone algorytmy rozwiązywania jednomaszynowego problemu szeregowania zadań o zmiennych wartościach
Bachman A., Janiak A., Kozik A., Winczaszek M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
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.
9
Parallet algorithm for some single machine scheduling problems
Bożejko W., Wodecki M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
81-90
EN
Problem of scheduling a single machine to minimize total weighted late job can be described as follows: there are n jobs to be processed, each job has an integer processing time, a weight and a due date. The objective is to minimize the total weighted late job, where the late job is performed after its due date. The problem belongs to the class of NP-hard problems. In the paper, we propose sequential and parallel (for SIMD model computing) branch and bound algorithms based on elimination criteria. Finally, the computation results and discussion of the performance of algorithms are presented.
PL
W pracy zajmujemy się problemem optymalizacji kolejności wykonywania zadań na jednej maszynie, w którym kryterium optymalności jest suma kosztów zadań spóźnionych. Jest on oznaczany przez n|1||Sigma wiUi i należy do klasy problemów silnie NP-zupełnych. Przedstawiamy algorytm równoległy (dla modelu SIMD) oparty na metodzie podziału i oszacowań, w którym wykorzystano kryteria eliminacyjne.
10
Minimalizacja sumy ważonych czasów zakończenia wykonywania zadań w jednomaszynowym problemie szeregowania z czasami przezbrojeń zależnymi od zasobów
Janiak A., Krysiak T., Lichtenstein M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
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.
11
Jednomaszynowy problem szeregowania zadań o zmiennych wartościach
Bachman A., Janiak A., Krysiak T.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
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.
12
Jednomaszynowy problem szeregowania z potęgowymi funkcjami zmiany wartości zadań
Bachman A., Janiak A., Kozik A., Winczaszek M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
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.
13
Dwukryterialne szeregowanie zadań czasowo-zależnych
Gawiejnowicz S., Kurc W., Pankowska L.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
151-162
PL
W pracy rozważany jest jednomaszynowy problem szeregowania zadań czasowo-zależnych z jednoczesną minimalizacją dwu kryteriów. Czas wykonywania pj zadania j jest funkcją czasu rozpoczęcia t tego zadania, pj=1+alfa jt, gdzie alfa j > 0 dla j=0,1,2,...,n. Zadania są niepodzielne, niezależne, nie ma czasów gotowości ani linii krytycznych. Kryterium optymalności uszeregowania ||.||(lambda) jest ważoną sumą kryteriów Cmax oraz SigmaCj postaci ||C||(lambda) = LambdaSigmaCj + (1-lambda)Cmax, gdzie lambda < [0,1] jest dowolną, ustaloną liczbą rzeczywistą, a C jest wektorem czasów zakończenia zadań. Przedstawiono twierdzenia mówiące, iż istnieje takie lambda o > 0, że dla wszystkich lambda < [0,lambda o] problem ten jest rozwiązywalny w czasie 0(nlogn) oraz takie lambda 1< 1, że dla wszystkich lambda < [lambda 1, 1] optymalne uszeregowanie dla tego problemu jest V-kształtne. Podano także dolne i górne oszacowania stosunku wartości kryterium ||.||(lambda) do wartości kryteriów Cmax oraz SigmaCj.
EN
In the paper a single machine time-dependent scheduling problem with simultaneous minimization of two criteria is considered. Processing time pj of job j is a function of the starting time t of the job, pj=1+alfa jt, where alfa j > 0 for j=0,1,2,...,n. The jobs are nonpreemptable, independent, there are neither ready times nor deadlines. The criterion of a schedule optimality ||.||(lambda) is a weighted sum of Cmax and SigmaCj criteria, ||C||(lambda) = lambda SigmaCj + (1-lambda)Cmax, where lambda < [0,1] is an arbitrary, fixed real number and C is a vector of completion times of jobs. There are presented theorems saying that there exists lambda o > 0 such that for all lambda < [0,lambda o] the problem is solvable in 0(nlogn) time and lambda 1 < 1 such that for all lambda < [lambda 1,1] an optimal schedule for the problem has a V-shape. There are also given lower and upper bounds for the ratio of values of the criterion ||.||(lambda) and values of Cmax and SigmaCj criteria.
14
Algorytmy tabu Search dla problemów szeregowania zadań na jednej maszynie z ograniczoną dostępnością
Formanowicz P.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
115-126
PL
W pracy zaprezentowano algorytmy oparte na metodzie tabu dla problemów szeregowania zadań niepodzielnych na jednej maszynie z okresami niedostępności i kryterium minimalizacji długości uszeregowania, sumy czasów zakończeni zadań oraz maksymalnego opóźnienia. Jakość zaprezentowanych algorytmów przebadano w obszernym eksperymencie obliczeniowym.
EN
In the paper algorithms based on tabu search method for scheduling non-preemptable tasks on a single machine with limited availability have been presented. The criterion functions to be minimized are the makespan, the total completion time, and the maximum lateness. The quality of the algorithms has been examined in an extensive computational experiment.
15
Algorytm zachłanny dla pewnego problemu szeregowania zadań czasowo-zależnych
Gawiejnowicz S., Kurc W., Pankowska L.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
139-150
PL
W pracy jest rozważany jednomaszynowy problem szeregowania zadań czasowo-zależnych. Czas wykonywania pj zadania j jest funkcją czasu t rozpoczęcia tego zadania, pj(t) = 1 + alfa jt, gdzie alfa j > O dla j = O, 1, ... ,n. Zadania są niepodzielne, niezależne, nie ma czasów gotowości ani linii krytycznych, a kryterium optymalności uszeregowania jest łączny czas zakończenia wykonywania zadań. Dla danego ciągu współczynników alfa j, j = O, 1, ... ,n definiowana jest sygnatura, której własności stanowią podstawę do skonstruowania algorytmu zachłannego.
EN
A single machine time-dependent scheduling problem is considered. The processing time pj of job j is a function of the starting time t of the job, pj(t) = 1 + alfa jt, where alfa j > 0 for j = 0, 1, ... ,n. Jobs are non-preemptable and independent, there are neither ready times nor deadlines, and the criterion of optimality is the total completion time. On the ground of properties of a signature for a given sequence of coefficients alfa j, j = 0,1, ... ,n a greedy algorithm for the problem is constructed.
16
Problem szeregowania zadań z liniami krytycznymi na jednej maszynie. Algorytm genetyczny
Lipiński P., Wodecki M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
263-272
PL
W pracy rozpatrywany jest jednomaszynowy problem minimalizacji sumy kosztów zadań opóźnionych. W literaturze jest on oznaczany przez 1|| Sigma wiTi i należy do klasy problemów silnie NP-zupełnych. Do jego rozwiązywania przedstawimy odpowiednio zaadaptowany algorytm genetyczny.
EN
In the paper, one - machine sequencing problem is considered under condition that the total weighted tardiness cist is minimized. Some genetic algorithms and computation results are presented.
17
Problem szeregowania zadań wykonywanych na jednej maszynie z dynamicznym modelem terminów ich dostępności
Janiak A., Słoniński P.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
167-177
PL
W niniejszej pracy zaprezentowano rozwiązanie problemu minimalizacji czasu zakończenia wykonywania zbioru n zadań o dynamicznych modelach terminów dostępności na pojedynczej maszynie krytycznej. Dane jest ograniczenie na ilość zasobu dostępną do rozdysponowania w danej chwili. Wykazano szereg istotnych własności tego problemu, a na ich podstawie skonstruowano algorytm optymalnego rozdziału zasobu dla zadań w ustalonej permutacji oraz algorytm aproksymacyjny szeregowania zadań.
EN
The aim of this contribution is to present the solution of the problem of minimizing the time of processing a set of n jobs with dynamical (differential) models of job release dates on a single critical machine. The amount of resource available at each moment is known a priori. Many important properties of this problem have been proven. They are the base for construction of optimal resource allocation algorithm for jobs processed in a given permutation. There is also presented the approximation algorithm for the scheduling problem.
18
Porównanie technik aproksymacyjnych: tabu search, ewolucyjnej i sieci neuronowej na przykładzie problemu szeregowania zadań z zasobami na pojedynczej maszynie
Janiak A., Marek M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
157-166
PL
W pracy porównano trzy algorytmy metaheurystyczne: tabu search, genetyczny, sieć neuronową dla problemu szeregowania zadań na jednej maszynie z zadanymi terminami dostępności i czasami realizacji zależnymi od ilości przydzielonego zasobu. Przyjętym kryterium jest minimalizacja maksymalnej nietenninowości. Podano wyniki przeprowadzonych eksperymentów numerycznych.
EN
The paper deals with a single machine scheduling problem with given release dates and processing times dependent on resources. Considered criterion is the maximum lateness minimization. To solve the problem three metaheuristic algorithms are presented and compared.
19
Minimalizacja globalnej ilości wykorzystanych zasobów dla jednomaszynowych problemów szeregowania zadań ze zmiennymi czasami wykonania
Iwanowski D., Janiak A.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
123-134
PL
W niniejszej pracy badane są jednomaszynowe problemy szeregowania zadań z czasami wykonania zależnymi od momentu rozpoczęcia wykonywania oraz ilości dostarczonego zasobu. Wykazano, że jeśli problem minimalizacji kryteriów czasowych takich jak długość uszeregowania oraz całkowity czas zakończenia wszystkich zadań przy ograniczeniu na całkowitą dostępną ilość zasobu jest problemem wielomianowym, to odpowiadający mu problem minimalizacji całkowitej ilości zasobu przy ograniczeniu na odpowiednie kryterium czasowe jest również problemem wielomianowym.
EN
The single machine job scheduling problems with time and resource dependent execution times have been examined in this paper. We proved, that if the problem of minimising the time criteria such as the makespan and the total completion time subject to a given constraint on the total resource consumption could be solved in polynomial time, then the corresponding problem of minimizing the total resource consumption subject to a given constraint on the value of the appropriate time criterion can be solved also in polynomial time.
20
Jednomaszynowy problem szeregowania zadań czasowo zależnych przy kryterium minimalizacji sumy opóźnień
Bachman A., Janiak A., Kozłowski J.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
13-22
PL
W pracy rozpatrywano jednomaszynowy problem szeregowania zadań przy kryterium minimalizacji sumy opóźnień. Założono, że czasy wykonywania zadań są liniowo zależne od momentów rozpoczęcia ich wykonywania. Analizowano problemy z jednym wspólnym, dwoma oraz wieloma różnymi pożądanymi terminami zakończenia wykonania zadań. Dla szczególnych przypadków rozpatrywanego problemu skonstruowano optymalne algorytmy wielomianowe.
EN
In the paper we consider a single machine scheduling problem of minimizing the total tardiness. The job processing times are given as start time dependent linear functions. We present some optimal solutions for the special cases of the problem under consideration.
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.