Wyniki wyszukiwania - Biblioteka Nauki

1

Complexity of scheduling of coupled tasks with chains precedence constraints and constant even length of the gap

100%

Ecker K. , Tanaś M.

|

2007

|

tom Vol. 32, No. 3

199-212

EN

The coupled tasks scheduling was originally introduced for modelling complex radar devices. It is still used for controlling such devices and applied in similar applications. This paper considers a problem of coupled tasks scheduling on one processor, under the assumptions that all processing times are equal to 1, the gap has an exact even length and the precedence constraints are strict. Although it is proven that the problem stated above is NP-hard in the strong sense if the precedence constraints have a form of a general graph, it is possible to solve some of its relaxed versions in polynomial time. This paper containts a solution for the problem of coupled tasks scheduling with assumption that the precedence constraints graph has a form of chains and it presents an algorithm which can solve the problem with such assumption in time O(n log n).

2

List scheduling of general task graphs under LogP model

100%

Kalinowski T. , Kort I. , Trystram D.

|

1998

|

tom nr 865

3-18

EN

The aim of this report is to assess the applicability of the list scheduling approach to the LogP model. More precisely, we present two adaptations of the Earliest Task First (ETF) heuristic. Then, we establish an upper bound on list schedules under LogP model. Finally, we present an extensive experimental study for different graph classes and model instances.

PL

Celem pracy jest ocena przydatności algorytmów listowych dla modelu LogP. W raporcie przedstawiono rozszerzenia algorytmu ETF, w których uwzględniono wymagania nakładane przez ten model. Ustalono wartość górnego ograniczenia na długość obliczonego uszeregowania oraz zaprezentowano wyniki symulacyjne dla różnych klas grafów programu i parametrów systemu.

3

Single machine scheduling problem with job release dates consisting of a constant and a dynamic part

100%

Janiak A. , Słoniński P.

|

2001

|

tom T. 5, z. 1/2

289-297

EN

In this paper we present a solution of a scheduling problem with non-classical models of job release dates. (The release date can be interpreted as a preliminary process, which determines the moment at which the job can be processed on the single machine, e.g. the critical machine.) We assumed that the release date consists of a constant (not dependent on the resource) and a dynamic (differential) part. The state of the process that corresponds to the dynamic part is given by the differential equation, which determines the speed of the change of this process as a function of resource allocated. After the preliminary process (e.g. performed on parallel machines) is completed, the jobs are processed on a single critical machine. The processing time on the critical machine is constant and known a priori. In this paper we minimize the job completion time of a set of n jobs with the above models of release dates on a single machine. The global level of the resource that can be divided by the preliminary processes that determine the release dates of particular jobs is known. We are to find a permutation of jobs on the critical machine and resource allocation that minimizes the completion time of all jobs. It was shown that the above problem is NP-hard even for identical functions of job release models and identical constant parts of the dates; it is strongly NP-hard for different models of job release models and identical constant parts of the dates. Approximation algorithms for solving the considered problem are constructed. Their effectiveness was tested in experimental analysis.

PL

W pracy podano rozwiązanie problemu szeregowania zadań z nieklasycznymi modelami terminów dostępności. (Termin dostępności zadania może być interpretowany jako pewien wstępny proces, którego czas trwania determinuje moment gotowości zadania do właściwej obróbki na pojedynczej maszynie, np. maszynie krytycznej). Przyjęto, że model terminu dostępności zadań składa się z części stałej (której czas trwania nie zależy od ilości przydzielonego zasobu) i części dynamicznej (różniczkowej). Stan procesu odpowiadającego części dynamicznej jest opisany równaniem różniczkowym, które określa prędkość zmiany tego procesu w zależności od ilości przydzielonego zasobu ciągłego. Po zakończeniu procesu przygotowawczego (np. realizowanego na równoległych maszynach) zadania są wykonywane na pojedynczej maszynie krytycznej. Czas właściwej obróbki każdego zadania na maszynie krytycznej jest stały i znany a priori. W pracy minimalizuje się czas zakończenia wykonania zbioru n zadań o powyższych modelach terminów dostępności na pojedynczej maszynie. Znana jest przy tym ilość zasobu dostępna do rozdysponowania w każdej chwili pomiędzy procesy wyznaczające terminy dostępności poszczególnych zadań. Należy znaleźć takie uszeregowanie zadań na maszynie krytycznej oraz taki rozdział ograniczonego globalnie zasobu, aby czas zakończenia wykonania wszystkich zadań był minimalny. Wykazano, że powyższy problem jest NP-trudny nawet dla jednakowych funkcji modeli terminów dostępności i identycznej stałej części terminu dostępności, a silnie NP-trudny dla różnych funkcji i identycznej stałej części terminu dostępności. Skonstruowano algorytmy aproksymacyjne rozwiązywania rozpatrywanego problemu. Efektywność tych algorytmów sprawdzono na drodze eksperymentów obliczeniowych.

4

Szeregowanie zadań przy czasach przezbrojeń zależnych od stanu systemu - badania symulacyjne

100%

Kucharska E. , Dutkiewicz L.

|

2001

|

tom T. 5, z. 1/2

335-343

PL

Artykuł dotyczy problemu specyficznego szeregowania zadań, w którym czasy przezbrojeń poszczególnych maszyn zależą nie tylko od zadania poprzedniego i następnego, ale również od stanu całego systemu. Zaprezentowany został opis modelu algebraiczno-logicznego zagadnienia. Zaproponowano algorytm, który wyznacza w sposób symulacyjny kolejność wykonywania zadań i przydział zasobów do nich przy równoczesnej minimalizacji ustalonego kryterium jakości i spełnieniu ograniczeń czasowych. Przedstawiono wyniki przeprowadzonych eksperymentów. Wskazano kierunki dalszych badań.

EN

The presented article refers to a specific task scheduling when retooling time for all devices depends not only on the previous and the next task, but also on the general state of the system. An (algebraic-logical) model of the system has been presented. An algorithm that sets up task scheduling and resource allocation using simulation methods has been proposed. Results of experiments have been presented as well as future research possibilities.

5

Wielomaszynowy problem szeregowania z optymalizowanymi przedziałami czasowymi zakończenia wykonywania zadań

100%

Janiak A. , Marek M.

|

2001

|

tom T. 5, z. 1/2

277-281

PL

W pracy rozpatrywany jest wielomaszynowy problem szeregowania, w którym dla zadań dobierane są optymalnie przedziały czasowe zakończenia ich wykonywania. Rozpatrywany przypadek jest uogólnieniem znanych z literatury naukowej problemów, w których dokonywano doboru pożądanych terminów zakończenia wykonania zadań. Dla badanego w pracy problemu należy znaleźć takie uszeregowanie zadań na identycznych maszynach równoległych oraz takie wartości parametrów określających położenie optymalizowanych przedziałów na osi czasu, które minimalizują rozpatrywane kryterium. W kryterium tym, karze podlegają zarówno zadania wykonane zbyt wcześnie (odpowiada to kosztom przechowywania produktu gotowego), jak również zadania spóźnione (odpowiada to kosztom nie dotrzymania terminu realizacji). Dodatkowo, kryterium to, zależy także od wartości parametrów określających jakość dobieranych przedziałów czasowych. Wykazano NP-zupełność badanego problemu, wykorzystując do tego NP-zupełny Problem Podziału.

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.

6

Minimalizacja sumy opóźnień w jednomaszynowym problemie szeregowania zadań czasowo zależnych

100%

Janiak A. , Kozłowski J.

|

2001

|

tom T. 5, z. 1/2

259-268

PL

W pracy rozpatrywany jest jednomaszynowy problem szeregowania zadań z czasami wykonywania opisanymi liniową funkcją zależną od momentu rozpoczęcia ich wykonywania. Optymalizacji podlega suma opóźnień zadań. Badany problem jest NP-trudny nawet w przypadku stałych czasów wykonywania zadań, dlatego w celu jego rozwiązania skonstruowano szereg algorytmów przybliżonych, w których wykorzystano własności wykazane dla jego szczególnych przypadków. Jakość rozwiązań generowanych przez skonstruowane algorytmy została porównana eksperymentalnie.

EN

The paper deals with a single machine scheduling problem for the total tardiness minimization. The job processing time is given as start time dependent linear function, which contains two parts. The first part denotes a fixed processing time and the second part (characterized by a growth rate) describes the job processing time deterioration. Since the classical version of the latter problem is NP-hard, we constructed three approximation algorithms to solve its special cases. The algorithms were developed based on the problem properties, which were proved in the paper. In order to compare the quality of proposed algorithms, we performed a numerical experiment.

7

Szeregowanie zadań w acyklicznym systemie otwartym

100%

Giaro K.

|

2001

|

tom T. 5, z. 1/2

213-220

PL

Celem artykułu jest podsumowanie znanych dotychczas oraz zaprezentowanie nowych wyników dotyczących złożoności obliczeniowej problemu poszukiwania optymalnego uszeregowania w systemie otwartym. Przy tym interesują nas systemy rzadkie, to jest takie, których graf jest acykliczny, czyli stanowi drzewo lub las. Rozważanymi kryteriami optymalizacji harmonogramu są: standardowa długość uszeregowana C(max) oraz średni czas zakończenia operacji. Badamy model ogólny niepodzielnych operacji o dowolnych długościach, system o operacjach podzielnych oraz system o zero-jedynkowych czasach wykonania. Innym rozważanym tu nieklasycznym modelem jest harmonogramowanie zwarte, tj. wymagające obustronnego braku przestojów w pracy, tak po stronie zadań, jak i procesorów. Szeregowanie takie jest bowiem zawsze wykonalne w przypadku systemów acyklicznych.

EN

Our aim is summarizing of already known and presenting of some new results on the complexity of optimal task scheduling in open shop. So we are interested in sparse systems, it means that their graphs are acyclic forming a tree of a forest. Our optimization criteria are the standard length of schedule C(TAX) and the average time of finish for operations. We consider the general model of operations with arbitrary length, a system with preemptive operations and finally a system with zero-one execution times. Another model under consideration is compact scheduling, where time breaks are imposed for both points of view: tasks and processors. It is because this kind of schedule could be always constructed for acyclic open shops.

8

Minimizing the resource level in a scheduling problem with dynamic models of jobs on parallel machines

100%

Janiak A. , Słoniński P.

|

2001

|

tom T. 5, z. 1/2

283-288

EN

In this paper we assume a very general - dynamic (differential) - model of jobs. In such model the speed of changing the job state depends on the amount of resource allocated to this job. We present a solution of a problem of minimizing the resource level required to complete the processing of the set of n jobs with dynamic models. The resource level function R(t) is a sum of all resource allocated to the jobs at the moment t. The jobs are processed in parallel on m identical machines (processors) and are not preemptive. Additionally there is a constraint that the maximum job completion time does not exceed the given limit. The solution of this problem consists of finding an assignment of jobs to machines, a permutation of jobs on a particular machine and a resource allocation function, that minimizes the maximum level of resource R(t) required to complete the processing of a set of jobs on the parallel machines. The above problem is NP-hard. We show a few of its properties regarding the form of the solution. Additionally, for some classes of the job model functions, we pointed out the possibility of obtaining the analytical form of the function R(t).

PL

W niniejszej pracy przyjęto bardzo ogólny - dynamiczny (różniczkowy) - model zadania. W modelu tym prędkość zmiany stanu zadania w danej chwili zależy od ilości przydzielonego zasobu podzielnego w sposób ciągły. W pracy minimalizowano poziom zasobu koniecznego do wykonania zbioru n zadań o modelach dynamicznych. Funkcja R(t) poziomu zasobu jest sumą ilości zasobu przydzielonego do zadań w chwili t. Zadania są wykonywane na m równoległych identycznych maszynach (procesorach) i są niepodzielne. Ponadto znane jest ograniczenie na czas zakończenia wykonania wszystkich zadań. Rozwiązanie tego problemu polega na znalezieniu takiego przydziału zadań do procesorów, takiej permutacji zadań na poszczególnych procesorach oraz takiego przydziału zasobu, aby zminimalizować maksymalną wartość funkcji poziomu R(t) zasobu wymaganego do realizacji tych zadań w każdej chwili czasu t. Powyższy problem jest NP-trudny. Udowodniono szereg własności dotyczących postaci rozwiązania problemu. Ponadto, dla pewnych funkcji modeli zadań wskazano możliwość uzyskania wzorów analitycznych określających optymalną postać funkcji R(t).

9

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

100%

Janiak A. , Marek M.

|

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.

10

Złożoność zwartego szeregowania zadań jednostkowych w systemie otwartym, przepływowym i mieszanym

100%

Kubale M. , Giaro K.

|

2001

|

tom T. 5, z. 1/2

329-334

PL

W artykule przedyskutowano złożoność obliczeniową problemu zwartego szeregowania zadań (operacji) jednostkowych na procesorach dedykowanych w systemie otwartym, przepływowym i mieszanym. Modelem matematycznym jest tu zwarte kolorowanie krawędzi grafu dwudzielnego. Ponieważ w ogólności zwarte pokolorowanie krawędzi nie zawsze jest możliwe (a rozstrzygnięcie tego jest NP-zupełne), koncentrujemy się na takich szczególnych typach grafów szeregowania, które posiadają rozwiązania wielomianowe.

EN

In this article we discuss the computational complexity of the problem of compact scheduling of unit execution tasks (operations) in open, flow and mixed shop. A mathematical model of such a problem is a compact (consecutive) coloring of the edges of a bipartite graph. Since in general a compact coloring is not always possible (and it is an NP-complete problem), we concentrate on those graph families that admit polynomial time solutions.

11

The shift scheduling problem : different formulations and solution methods

100%

Jacquet-Lagreze E. , Montaut D. , Partouche A.

|

1998

|

tom Vol. 23, No. 4

199-217

EN

The shift scheduling problem (SSP) consists of determining a set of shifts to cover an extended and variable requirement curve, minimizing the cost. The formulation of the SSP as a set-covering problem has been much studied and many heuristic approaches have been proposed. However, no attempt has been made to solve the problem with Constraint Logic Programming (CLP). After a literature review, we solve the set-covering formulation with Integer Linear Programming (ILP) and CLP Owing to the bad performances of CLP, we suggest an implicit model and test it for the two solution methods. We compare the four approaches and finally conclude that II.P on the classical model gives much better results. Then we propose a very efficient heuristic based on ILP, that permits a high level of flexibility and we measure experimentally the benefit of more flexibility on productivity.

12

Social learning algorithm as a tool for solving some difficult scheduling problems

100%

Jędrzejowicz P.

|

1999

|

tom Vol. 24, No. 2

51-66

EN

The paper investigates application of the new adaptive memory programming techniques called SLA (social learning algorithm) to scheduling multiple variant tasks. SLA has been inspired by analogies to a social phenomenon of organized learning. Main features of both -education systems and SLA include learning stages, massive number of individuals at the beginning stages, selection of best individuals.- before entering further stages of learning, and increasing sophistication and specialization of learning as an individual progresses through stages. The paper introduces a concept of the social learning algorithm (SLA ), and presents two applications of the proposed concept to solving computationally difficult scheduling problems. Computational experiments show that SLA can produce competitive results comparing to other heuristics and metaheuristics.

13

Experimental feedback on bioobjective permutation scheduling problems solved with a population heuristic

80%

Morita H. , Gandibleux X. , Katoh N.

|

2001

|

tom Vol. 26, No. 1

23-50

EN

Population heuristics present native abilities for solving optimization problems with multiple objectives. Using evolution and adaptation mechanisms, a population of individuals evolves in order to describe a good approximation of the efficient solutions. The resolution of the 1 | | (EC,- ,Tmaar) permutation scheduling problems, for which an exact algorithm is available, is investigated using a population heuristic based on genetic algorithms. The aim here is not to put in competition a heuristic method with an exact method but to give an experimental feedback on the resolution abilities of biobjective permutation scheduling problems with a population heuristic. The paper reports the aspects analyzed in this study : first, the pertinence of using genetic information into a population algorithm and second, a detailed multicriteria analysis of efficient solutions for this class of scheduling problems.

14

Computational Experiments for Scheduling Workflow Applications in Grid Environment

80%

Mika M. , Piątek W. , Waligóra G. , Węglarz J.

|

2011

|

tom Vol. 17, No. 1-2

53-62

EN

The problem of scheduling workflow applications in a grid environment is considered. The problem is divided into two stages: (i) resource allocation, which consists in allocating distributed grid resources to tasks of a workflow in such a way that the resource demands of each task are satisfied, and (ii) scheduling performed by local grid schedulers. Grid resources are divided into computational and network resources. Computational and transmission workflow tasks are distinguished. A computational experiment is presented in order to show the importance of resource allocation, as well as examine the influence of the local scheduling policy. Certain conclusions and directions for future research are given.

15

Multi-mode resource-constrained project schedulig problem with discounted positive cash flows - simulated annealing vs. tabu search

80%

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

|

2002

|

tom Vol. 27, No. 2

97-114

EN

In this paper the multi-mode resource-constrained project scheduling problem with discounted cash flows is considered. A positive cash flow is associated with the completion of each activity. The objective is the maximization of the net present value of all cash flows. Local search metaheuristics: simulated annealing and tabu search are proposed to solve this problem. A comprehensive computational experiment is described, performed on a set of standard test problems constructed by the ProGen project generator, where the activities' cash flows are generated randomly with the uniform distribution. The metaheuristics are computationally compared with the random sampling method. The results are analyzed and discussed and some final remarks are included.

16

Scheduling of surface mount technology lines with machine downtimes

80%

Sawik T.

|

2001

|

tom T. 5, z. 1/2

485-492

EN

The paper presents new mixed integer programming formulation for scheduling of printed wiring board assembly in SMT (Surface Mount Technology) lines with limited machine availability. The interval of machine non-availability is defined to be a period of time when the machine is not available to perform its intended function due to planned downtime events such as preventive maintenance, production tests, change of consumables/chemicals, or prescheduled production runs. The SMT line consists of several processing stages in series, separated by finite intermediate buffers, where each stage has one or more identical parallel machines. A board which has completed processing on a machine may remain there and block the machine until a downstream machine becomes available for processing. The objective is to determine an assembly schedule within the remaining free processing intervals for a mix of board types so as to complete the boards in minimum time. Numerical examples are presented to illustrate applications of the proposed model and an advanced algebraic modelling language AMPL with CPEX solver.

PL

W pracy przedstawiono nowy model programowania całkowitoliczbowego mieszanego do optymalizacji harmonogramów montażu powierzchniowego kart elektronicznych, w przypadku występowania zaplanowanych przestojów maszyn. Przerwy takie mogą reprezentować zaplanowane remonty prewencyjne, testy produkcyjne, wymianę podajników z częściami składowymi itp. Elastyczna linia montażu powierzchniowego składa się z szeregowo połączonych stacji montażowych, rozdzielonych buforami międzyoperacyjnymi o ograniczonych pojemnościach, zaś każda stacja obejmuje jedną lub kilka jednakowych maszyn pracujących równolegle. Linia przeznaczona jest do jednoczesnego montażu kilku lub kilkunastu typów wyrobów. Każdy wyrób po wykonaniu operacji montażu na danej stacji jest transportowany do stacji następnej lub bufora pomiędzy stacjami. Jeśli w buforze nie ma miejsca, wyrób pozostaje na dotychczasowej stacji i blokuje ją do momentu zwolnienia miejsca w buforze. Należy wyznaczyć najkrótszy harmonogram montażu zadanej partii różnych wyrobów. Zamieszczono przykłady harmonogramów montażu kart elektronicznych wyznaczonych za pomocą opracowanego modelu przy zastosowaniu pakietu optymalizacji dyskretnej AMPL/CPLEX.

17

Własności algorytmów poszukiwań lokalnych

80%

Bożejko W. , Smutnicki C.

|

2001

|

tom T. 5, z. 1/2

95-101

PL

Przedyskutowano zastosowanie miary odległości pomiędzy rozwiązaniami w przestrzeni permutacji dla oceny własności algorytmów poszukiwań lokalnych. Pokazano ich pewne nowe własności. Pokazano interpretację miar w związku z różnymi perturbacjami używanymi w algorytmach. Zaproponowano ogólną metodę transformacji przestrzeni permutacji w przestrzeń Euklidesową Ar-wymiarową. W szczególności, podano przykład transformacji w przestrzeń 2-wymiarową z użyciem permutacji referencyjnych. Pokazano także obrazy przestrzeni dla problemu szeregowania z kryterium średniego łącznego spóźnienia.

EN

Distance measures between solutions in the space of permutations have been discussed, to evaluate properties of some local search algorithms. New their properties have been proved. We show interpretation of these measures in term of various perturbations used in algorithms. Next, we introduce transformation of permutation space into Euclidian k-dimensional space. Particularly, there has been proposed the transformation to 2-dimensional plane, which uses reference permutations. Images of the solution space for the single-machine scheduling problem with the mean tardiness criterion have been shown.

18

Problem minimalizacji czasu cyklu w pewnym procesie produkcyjnym

80%

Smutnicki C. , Dąbrowski P.

|

2001

|

tom T. 5, z. 1/2

507-516

PL

W pracy rozważany jest realny problem harmonogramowania zleceń klientów w zakładzie przemysłu budowlanego zajmującym się produkcją bloków betonowych. System produkcyjny może być modelowany jako hybrydowe połączenie problemu szeregowania zleceń w systemie przepływowym z ograniczeniami no-wait/no-store (bez czekania/bez składowania) oraz kombinacji maszyn bottle-neck/non-bottleneck (wąskie gardło/brak wąskiego gardła). Kryterium optymalizacyjnym jest minimalizacja czasu cyklu. Problem ten może być rozwiązany przez dekompozycję do podproblemów na podstawie własności rozpatrywanego kryterium. Uzyskane w ten sposób podproblemy mogą być rozwiązywane w prosty sposób.

EN

The problem of scheduling in production of concrete blocks in a firm from building industry has been considered. This production system can be modeled by flow-shop scheduling problem with mixed no-wait/no-store constraints and non-bottleneck machines. The scheduling criterion is the length of cycle time. The problem is solved by decomposition into several subproblems, accordingly to properties of scheduling criterion. Next, obtained subproblems can be solved in a simple way.

19

Modelowanie niepewności w pewnym problemie szeregowania zadań

80%

Bożejko W. , Wodecki M.

|

2001

|

tom T. 5, z. 1/2

103-112

PL

W pracy przedstawiamy przykład stosowania metod probabilistycznych oraz teorii zbiorów rozmytych do modelowania niepewnych danych. Oba sposoby reprezentacji niedeterministycznych parametrów porównujemy na przykładzie jednomaszynowego problemu minimalizacji sumy kar zadań nie wykonanych w terminie. Na bazie powszechnie obecnie stosowanej metaheurystyki tabu search skonstruowano algorytmy rozwiązywania rozpatrywanego problemu szeregowania zadań. Na podstawie otrzymanych wyników obliczeniowych można stwierdzić, że najbardziej odporne na zaburzenie danych są rozwiązania wyznaczone przez algorytm probabilistyczny (niepewne dane są zmiennymi losowymi).

EN

We show some samples of probablistic methods and fuzzy sets application to model uncertainly data in some scheduling problems. We compare both methods of undeterministic parameters representation on the one - machine problem of minimalization the total weighted number of late jobs. On base of taboo search metaheuristic (commonly currently applied) we construct algorithms to solve scheduling problem as described above. On the basis of computational results we can affirm that the most resistant to data disturbance is solution created by probabilistic algorithm (uncertainly data are random variables).

20

Unifying planning and scheduling as timelines in a component-based perspective

80%

Fratini S. , Pecora F. , Cesta A.

|

2008

|

tom Vol. 18, no. 2

231-271

EN

The timeline-based approach to planning represents an effective alternative to classical planning for complex domains requiring the use of both temporal reasoning and scheduling features. This paper discusses the constraint-based approach to timeline planning and scheduling introduced in OMPS. OMPS is a an architecture for problem solving which draws inspiration from both control theory and constraint-based reasoning, and which is based on the notion of components. The rationale behind the component-based approach shares with classical control theory a basic modeling perspective: the planning and scheduling problem is represented by identifying a set of relevant domain components which need to be controlled to obtain a desired temporal behavior for the entire system. Components are entities whose properties may vary in time and which model one or more physical (or logical) domain subsystems relevant to a given planning context. The planner/scheduler plays the role of the controller for these entities, and reasons in terms of constraints that bound their internal evolutions and the desired properties of the generated behaviors (goals). Our work complements this modeling assumption with a constraint-based computational framework. Admissible temporal behaviors of components are specified as a set of causal constraints within a rich temporal specification, and goals are specified as temporal constraint preferences. The OMPS software architecture presented in this paper combines both specific and generic constraint solvers in defining consistent timelines which satisfy a given set of goals.