Wyniki wyszukiwania - BazTech

1

Problem-Independent Approach to Multiprocessor Dependent Task Scheduling

Król D., Zydek D., Koszałka L.

International Journal of Electronics and Telecommunications

|

2012

|

Vol. 58, No. 4

369-379

EN

This paper concerns Directed Acyclic Graph task scheduling on parallel executors. The problem is solved using two new implementations of Tabu Search and genetic algorithm presented in the paper. A new approach to solution coding is also introduced and implemented in both metaheuristics algorithms. Results given by the algorithms are compared to those generated by greedy LPT and SS-FF algorithms; and HAR algorithm. The analysis of the obtained results of multistage simulation experiments confirms the conclusion that the proposed and implemented algorithms are characterized by very good performance and characteristics.

2

Computer-aided system to allotment of the operating tasks in the ship engine room

Kamiński P.

Journal of Polish CIMAC

|

2011

|

Vol. 6, no 2

113-120

EN

The frequent causes of ships’ detentions by port authorities are abnormalities of ship power plant functioning. Each extended ship lay time in port results in a waste of ship operating time thus costs rise to ship owners. This is connected with improper ship power plant management. In order to avoid this, a ship engineer should have at his disposal computer aided system supporting him in the managing of the ship power plant. The prototype of a computer-aided system of operational and maintenance task assignation in ship engine room has been presented in this paper. This system contains three modules that respond of decision-making process for three stages: collecting essential information about operating tasks, selecting of operational and maintenance tasks, generating of the optimal schedule for the set of the determined conditions. For allotment problem was formulated, in the most substantial operating states of a ship like lay time in harbour and sea voyage, the knapsack algorithm’ was applied. The mathematical model uses twocriterions optimization for operational and maintenance task assignation in the ship engine room.

3

Computer-aided system to allotment of the operating tasks in the ship engine room

Kamiński P.

Journal of Polish CIMAC

|

2011

|

Vol. 6, no 3

49-56

EN

The frequent causes of ships’ detentions by port authorities are abnormalities of ship power plant functioning. Each extended ship lay time in port results in a waste of ship operating time thus costs rise to ship owners. This is connected with improper ship power plant management. In order to avoid this, a ship engineer should have at his disposal computer aided system supporting him in the managing of the ship power plant. The prototype of a computer-aided system of operational and maintenance task assignation in ship engine room has been presented in this paper. This system contains three modules that respond of decision-making process for three stages: collecting essential information about operating tasks, selecting of operational and maintenance tasks, generating of the optimal schedule for the set of the determined conditions. For allotment problem was formulated, in the most substantial operating states of a ship like lay time in harbour and sea voyage, the knapsack algorithm’ was applied. The mathematical model uses twocriterions optimization for operational and maintenance task assignation in the ship engine room.

4

Planowanie prac operatorów siłowni okrętowej w warunkach ograniczonego czasu

Kamiński P.

Logistyka

|

2009

|

nr 6

CD-CD

PL

W pracy przedstawiono problem optymalnego planowania zadań eksploatacyjnych w siłowni okrętowej z wykorzystaniem teorii załadunku (pakowania) w warunkach ograniczonego czasu. W podejściu tym maksymalizowane są dwa kryteria: waSności zadań z eksploatacyjnego punktu widzenia oraz najlepszego wykorzystania dostępnego czasu. Określona została postać funkcji celu oraz podstawowe ograniczenia, z jakimi spotyka się starszy mechanik podczas harmonogramowania prac w siłowni okrętowej. Do przeszukiwania przestrzeni dopuszczalnych rozwiązań zastosowano zmodyfikowaną metodę przeglądu z nawrotami.

EN

The problem of operation tasks scheduling in Engine Room used the theory of packing has been presented in this paper. Two criterions is maximized in this approach: importance of the tasks and the best use of accessible time. The objective function, decision variables and fundamental constraints what meet chief engineer were defined. To searching of solutions space was used the modified Depth-first search (DFS) algorithm.

5

Heurystyczna procedura szeregowania zadań w dyskretnym systemie produkcyjnym z uwzględnieniem ograniczeń zasobowych

Buchalski Z.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2008

|

z. 150

37-44

PL

Praca dotyczy zagadnienia czasowo-optymalnego przydziału n zadań niezależnych i zasobu nieodnawialnego do m maszyn równoległych w dyskretnym systemie produkcyjnym. Dla zadanej funkcji czasu realizacji zadań sformułowano model matematyczny zagadnienia oraz zaprezentowano algorytm heurystyczny dla rozwiązania postawionego problemu. Przedstawiono wyniki badań numerycznych wykonanych na bazie zaproponowanego algorytmu heurystycznego.

EN

In the paper problem of time-optimal allocation of n independent tasks and nonrenewable resource's units to m parallel machines in discrete production system is considered. For some tasks execution time function the mathematical model of this problem is formulated and an heuristic algorithm for solution this problem is presented. Some results of numerical experiments for basis of proposed heuristic algorithm are presented.

6

Formalization of Location and Spacing Tasks Modern Methods of Design

Chura I., Kernytskyy A.

Machine Dynamics Problems

|

2007

|

Vol. 31, No. 3

15-24

EN

Tasks of optimal location and spacing of geometric objects arising during material cutting, animation, design of PCBs, design of plans of both habitual and industrial areas, location of equipments and loads and design of economic processes belongs to the class of the abovementioned problems. Therefore, the problem of ES development for the location and spacing problems solution is vital. Interest to the location and spacing tasks solution is determined by the wide spectrum of practical applications from the one side and by the complication and no triviality of the development of mathematical models vital for their adequate description. Regardless the variety of such problems, all of them include the formulation: it is necessary to locate the geometric objects in the given region taking into account terms and limitations so that achieved value of an efficiency function are the nearest ones to the optimum. The tasks of location and spacing of flat objects depending on their application domain are classified in the paper. On the basis of the conducted analysis of practical problems mathematical formalization is presented. As a result of analysis of the known practical problems of location and spacing their similarity by input an output data is distinguished. All formalized problems are joined by main properties: a) there is questions about location of geometric objects of arbitrary form in the regions of arbitrary geometric form, b) each of problems is formalized, at least verbally, as the problem of mathematical programming. In other words, a problem appears as some terms that are limitations on the parameters of placing of objects at implementation of which it is necessary to achieve put objective. Under achievement of purpose the receipt of the best quality or optimum quantity is understood, that are expressed by correlations and relied on the parameters of placing of objects. It is known, that such correlations in the mathematical programming are named functions or functions of quality having a special purpose.

7

Heurystyczny algorytm planowania rozdziału zadań dla systemu z maszynami równoległymi o ograniczonych zasobach

Buchalski Z.

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

|

2007

|

T. 11, z. 1-2

61-69

PL

Praca dotyczy zagadnienia czasowo-optymalnego przydziału n zadań niezależnych i zasobu nieodnawialnego do m maszyn równoległych. Dla zadanej funkcji czasu realizacji zadań sformułowano model matematyczny zagadnienia oraz zaprezentowano algorytm heurystyczny dla rozwiązania postawionego problemu. Przedstawiono wyniki badań komputerowych wykonanych na bazie zaproponowanego algorytmu heurystycznego.

EN

In the paper problem of time-optimal allocation of n independent tasks and nonrenewable resources to m parallel machines is considered. For some tasks execution time function the mathematical model of this problem is formulated and an heuristic algorithm for solution this problem is presented. Some results of executed computer research for basis of proposed heuristic algorithm are presented.

8

Zastosowanie binaryzacji okresów zadań w systemach wieloprocesorowych

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2006

|

Vol. 52, z. 4

545-561

PL

Artykuł dotyczy zastosowania techniki binaryzacji okresów zadań w systemach wieloprocesorowych. Binaryzacja okresów zadań jest techniką polegającą na takiej transformacji wartości okresów zadań periodycznych, aby były wielokrotnościami (będącymi naturalną potęga liczby 2) pewnego okresu bazowego r. Zatem w systemie o okresach binarnych szeregowaniu podlegają zadania o wartościach okresów r, 2r, 4r, 8r, 16r, 32r itd. Binaryzacja okresów zadań ułatwia znalezienie ich planu szeregowania, gwarantującego dotrzymanie ograniczeń czasowych przez wszystkie zadania. Binaryzacja jest stosowana powszechnie w systemach czasu rzeczywistego o ostrych ograniczeniach czasowych. Obecnie binaryzacji wartości okresów podlegają głównie zadania przeznaczone do realizacji w systemach jednoprocesorowych. Artykuł niniejszy stanowi propozycję rozszerzenia obszaru stosowalności techniki binaryzacji okresów zadań na systemy zbudowane z większej liczby jednostek obliczeniowych. Zgodnie z propozycją autora zastosowanie binaryzacji okresów zadań wieloprocesorowych stanowi klucz do zastosowania do ich szeregowania popularnego algorytmu Rate Monotonie Scheduling. Przedstawione w artykule rozważania teoretyczne zostały zilustrowane przykładem szeregowania zadań wieloprocesorowych o okresach binarnych dla systemu zbudowanego z czterech jednostek obliczeniowych.

EN

Nowadays the real-time systems find application in many branches of industry, science and transport. The most important factor in the real-time systems is the time of execution of tasks. The results that are correct but delivered with the violation of task deadline are useless. In the case of hard real-time systems the violation of task deadline can lead to a catastrophe or even loss of human life. This is the reason why the task scheduling theory developed strongly over the last years. In the computer systems with hard real-time constraints the most popular task scheduling algorithm is Rate Monotonie Scheduling (RMS). In RMS all tasks are assigned priorities. The rule is the shorter is task period the higher priority the task obtains. In a given moment the task that is read for execution and has the highest priority is executed. If any other task with higher priority arrives the task that is executed is pre-empted and the task that came is then executed. Together with RMS binarisation is often used. Binarisation is a technique that transforms the periods of tasks in the way that only tasks with harmonic values of periods exist. Up till now binarisation was used only for a uniprocessor systems. This author proposed a new solution in which binarisation is used for multiprocessor systems as well. Scheduling and allocation of multiprocessor tasks in a multiprocessor system is NP - complete optimisation problem. This is the reason why the optimal solution for scheduling of multiprocessor task can not be found in a reasonable time. In such case only suboptimal solutions can be found. This author proposed evolutionary algorithm as a solution to multiprocessor tasks allocation and scheduling. The way in which the order of execution of task is coded on the genetic material was illustrated on the example of scheduling the tasks for four processor systems. The genetic material also allows to code the way in which the proper binarisation is chosen. There are very few tasks scheduling algorithms that could be used for a general class of tasks. There are different scheduling algorithms for uniprocessor task and multiprocessor task and for tasks that are executed on arbitrary or dedicated processors. The algorithm of tasks scheduling and allocation that was proposed by this author is a general one, because it can be used for uniprocessor and multiprocessor tasks and for dedicated, arbitrary and partially arbitrary processors.

9

Heurystyczny algorytm szeregowania zadań w systemie maszyn równoległych z równoczesnym rozdziałem zasobów

Buchalski Z.

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

|

2005

|

T. 9, z. 1-2

37-45

PL

Praca dotyczy zagadnienia czasowo-optymalnego przydziału n zadań niezależnych i zasobu nieodnawialnego do m maszyn równoległych. Dla zadanej funkcji czasu realizacji zadań sformułowano model matematyczny zagadnienia oraz zaprezentowano algorytm heurystyczny dla rozwiązania postawionego problemu. Przedstawiono wyniki eksperymentów obliczeniowych wykonanych na bazie zaproponowanego algorytmu heurystycznego.

EN

In the paper problem of time-optimal allocation of n independent tasks and nonrenewable resources to m parallel machines is considered. For some tasks execution time function the mathematical model of this problem is formulated and an heuristic algorithm for solution this problem is presented. Some results of executed numerical experiment for basis of proposed heuristic algorithm are presented.

10

Szeregowanie zadań wielowariantowych i wieloprocesorowych metodą programowania ewolucyjnego

Ciecholewski M.

Elektrotechnika i Elektronika

|

2004

|

T. 23, z. 2

89-97

PL

W artykule zaprezentowano pewien model algorytmu ewolucyjnego, który umożliwia otrzymywanie przybliżonych rozwiązań dla zagadnienia szeregowania zadań wielowariantowych na procesorach równoległych. Poszczególne etapy działania algorytmu zawierają przykłady. Model algorytmu został w pełni zaimplementowany w postaci programu komputerowego, w związku z czym został też przedstawiony opis działania aplikacji oraz przykładowe wyniki uzyskane dzięki przeprowadzonym eksperymentom komputerowym.

EN

This article presents a model of the evolution strategy which enables to obtain approximate solutions to scheduling of the multi-variant tasks problem on multiple and parallel processors. Each step of the performed algorithm has been illustrated by examples. The algorithm was fully implemented, in that case the article includes the specification of the programm. Moreover, it includes the sample results of the conducted computer experiments.

11

Algorytmy szeregowania zadań wielowariantowych na procesorach równoległych

Ciecholewski M.

Elektrotechnika i Elektronika

|

2004

|

T. 23, z. 2

98-104

PL

W artykule przedstawiono algorytm szeregowania zadań wielowariantowych na procesorach równoległych (o nazwie szereguj_2). Wchodzi on w skład programu komputerowego zaprezentowanego w pracy [3]. W pracy szczegółowo omówiono operacje zastosowane w algorytmie, umożliwiające przydzielanie zadań wielowariantowych do procesorów w jak najwcześniejszym terminie, a także pozwalające eliminować sytuacje konfliktowe, czyli przydzielanie zadań w danym czasie do tych samych procesorów.

EN

This paper presents an algorithm for scheduling of the multi-variant tasks problem on parallel processors (defined as szereguj_2). The algorithm is included in the computer program which has been presented in [3]. The paper fully details implemented operations, applicable to allocate multi-variant tasks to processors under the hard-time constraints. It also covers a solution how to avoid conflicts between resources.

12

Algorytmy szeregowania operacji i wyboru sekwencji montażowych dla elastycznego gniazda montażowego

Magiera M.

Zagadnienia Techniczno-Ekonomiczne

|

2003

|

T. 48, z. 3

887--898

PL

W pracy przedstawiono metodę planowania i harmonogramowania montażu w elastycznych gniazdach montażowych. W opracowanym podejściu monolitycznym zastosowano modele programowania dyskretnego. Dla każdego produktu montowanego w gnieździe wybierana jest tylko jedna sekwencja spośród danych alternatywnych sekwencji montażowych. Szeregowane są operacje montażowe wybranych sekwencji. Dla tych problemów zbudowano algorytmy heurystyczne. Zamieszczono wyniki przeprowadzonych eksperymentów obliczeniowych.

EN

The paper presents a method of planning and task scheduling for flexible assembly cell. The mixed integer programming is used in the monolithic approach. The alternative assembly sequences are given for each product. The selection of the best assembly sequences and scheduling of assembly tasks are the essence of the created mathematical models. The heuristics are proposed to reduce CPU time required for mixed integer programming. Results of computational experiments with the proposed approaches are included.

13

Wybrane metody i algorytmy szeregowania zadań w serwerze WWW

Prokopski G.

Studia Informatica

|

2003

|

Vol. 24, nr 2B

35-44

PL

Przedstawiono wymagania stawiane nowoczesnym serwerom WWW ze względu na zastosowania biznesowe. Na podstawie literatury określono specyfikę ich obciążenia związaną ze zjawiskiem długiego ogona. Stworzono listę głównych cech rozwiązań szeregowania m.in. ze względu na rodzaj kryterium optymalizacji. Dla dwóch przykładowych rozwiązań wskazano cechy ze stworzonej listy. Zaproponowano dalsze kierunki rozwoju.

EN

Requirements for modern web servers in business applications is introduced. Based on a literature the specific of their heavy tailed burden is defined. A list of main features of scheduling solutions, among others - because of the optimalisation criteria, is created. For two example solutions their features from the list are pointed out. Future research directions are proposed.