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

Znaleziono wyników: 14

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  maszyny równoległe
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Highly efficient scheduling algorithms for identical parallel machines with sufficient conditions for optimality of the solutions
Telenyk Sergii, Nowakowski Grzegorz, Pavlov Oleksandr, Misura Olena, Melnikov Oleg, Khalus Olena
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2024
|
Vol. 72, nr 1
art. no. e148939
EN
This paper aims to develop new highly efficient PSC-algorithms (algorithms that contain a polynomial-time sub-algorithm with sufficient conditions for the optimality of the solutions obtained) for several interrelated problems involving identical parallel machine scheduling. These problems share common basic theoretical positions and common principles of their solving. Two main intractable scheduling problems are considered: (“Minimization of the total tardiness of jobs on parallel machines with machine release times and a common due date” (TTPR) and “Minimising the total tardiness of parallel machines completion times with respect to the common due date with machine release times” (TTCR)) and an auxiliary one (“Minimising the difference between the maximal and the minimal completion times of the machines” (MDMM)). The latter is used to efficiently solve the first two ones. For the TTPR problem and its generalisation in the case when there are machines with release times that extend past the common due date (TTPRE problem), new theoretical properties are given, which were obtained on the basis of the previously published ones. Based on the new theoretical results and computational experiments the PSC-algorithm solving these two problems is modified (sub-algorithms A1, A2). Then the auxiliary problem MDMM is considered and Algorithm A0 is proposed for its solving. Based on the analysis of computational experiments, A0 is included in the PSC-algorithm for solving the problems TTPR, TTPRE as its polynomial component for constructing a schedule with zero tardiness of jobs if such a schedule exists (a new third sufficient condition of optimality). Next, the second intractable combinatorial optimization problem TTCR is considered, deducing its sufficient conditions of optimality, and it is shown that Algorithm A0 is also an efficient polynomial component of the PSC-algorithm solving the TTCR problem. Next, the case of a schedule structure is analysed (partially tardy), in which the functionals of the TTPR and TTCR problems become identical. This facilitates the use of Algorithm A1 for the TTPR problem in this case of the TTCR problem. For Algorithm A1, in addition to the possibility of obtaining a better solution, there exists a theoretically proven estimate of the deviation of the solution from the optimum. Thus, the second PSC-algorithm solving the TTCR problem finds an exact solution or an approximate solution with a strict upper bound for its deviation from the optimum. The practicability of solving the problems under consideration is substantiated.
2
Content available remote Measure of adequacy for the supercomputer job management system model
Baranov Anton, Lyakhovets Dmitriy, Savin Gennady, Shabanov Boris, Telegin Pavel
Annals of Computer Science and Information Systems
|
2019
|
Vol. 18
423--426
EN
In this paper we investigate the problem of modelling modern supercomputer job management systems (JMS). When modelling the JMS, one of the main issues is the adequacy of the model used in experimental studies. The paper attempts to determine the measure of the JMS model adequacy by comparing the characteristics of two job streams, one of which was acquired from a real supercomputer and the other is obtained from the JMS model. We show that the normalized Euclidean distance between vectors of jobs residence times obtained from the job streams of the real system and the JMS model can serve as a measure of the adequacy of the JMS model. The paper also defines the reference value of the measure of adequacy corresponding to the JMS model with virtual nodes.
3
Content available remote A no-wait scheduling method for assembly operations concerning multi-option electric devices
Magiera M.
Przegląd Elektrotechniczny
|
2018
|
R. 94, nr 4
187--190
EN
The monolithic method of no-wait scheduling is presented. The individual requirements of recipients of the electric devices are regarded. The method is for assembly lines with parallel machines, without intermediate buffers. The mathematical models of integer programming are constructed for this configuration of assembly lines – for no-wait scheduling. The results of computational experiments with the proposed method are presented – fixed and alternative assembly routes are compared, among others.
PL
Przedstawiono monolityczną metodę szeregowania operacji montażowych dotyczących sprzętu elektrycznego uwzgledniającego indywidualne wymagania odbiorców. Metodę zbudowano dla linii montażowych z maszynami równoległymi, bez buforów międzyoperacyjnych. Skonstruowane modele matematyczne zadań programowania całkowitoliczbowego, w których uwzględniono opisane konfiguracje linii montażowych, przeznaczone są do budowy harmonogramów montażu zgodnie z ideą szeregowania „bez czekania”. Zamieszczono wyniki eksperymentów obliczeniowych – porównano m.in. dwie różne organizacje przepływów produktów dotyczące sztywnych i alternatywnych marszrut montażu.
4
Content available remote Heurystyczny algorytm szeregowania operacji dla elastycznych linii montażowych z maszynami równoległymi
Magiera M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
157-163
PL
W artykule przedstawiony został heurystyczny algorytm szeregowania operacji dla elastycznych linii montażowych (ELM) z maszynami równoległymi i z buforami międzystadialnymi. W takim wielostadialnym systemie przepływowym operacje wykonywane są na kolejnych maszynach, należących do poszczególnych stadiów - zbiorów maszyn pracujących równolegle. Produkt może pomijać niektóre stadia. W każdym ze stadiów produkt może obciążyć co najwyżej jedną maszynę, spośród maszyn pracujących równolegle. W algorytmie wykorzystany został model matematyczny szeregowania operacji dla ELM z maszynami równoległymi, w którym przydzielane są operacje montażowe do maszyn. W tym liniowym modelu (zawierającym binarne zmienne decyzyjne) zastosowana została funkcja, dzięki której można aproksymować minimalizację długości uszeregowania. Opracowana heurystyka służy do rozwiązania zadania sformułowanego w postaci wymienionego modelu matematycznego, w którym usunięte zostały warunki całkowitoliczbowości zmiennych decyzyjnych. Jest to więc heurystyka relaksacyjna. Dzięki zastosowaniu relaksacji zmiennych, zadanie szeregowania operacji rozwiązywane jest w czasie znacznie krótszym niż w przypadku rozwiązywania zadania programowania całkowitoliczbowego. Opisane są zasady zaokrąglania uzyskiwanych ułamkowych wyników do wartości całkowitych oraz reguły modyfikacji i weryfikacji budowanego w kolejnych iteracjach harmonogramu. Algorytm heurystyczny został przetestowany. Uzyskiwane rozwiązania heurystyczne porównane zostały z rozwiązaniami optymalnymi. W artykule zamieszczone są wyniki przeprowadzonych eksperymentów obliczeniowych.
EN
The paper presents relaxation heuristic of tasks scheduling for flexible assembly lines with parallel machines and with intermediate buffers. Each assembly stage consists of one or several parallel machines. The flow is unidirectional. Each product loads no more than one machine of the assembly stage. The assembly sequences and the assignment of operations to assembly stages with limited working space are the starting point of the described heuristic. Linear mathematical models for tasks scheduling are used in the method. The schedule is divided into time intervals in the algorithm. Approximation to time criterion is used. A linear relaxation - based heuristic is created to reduce the CPU time required for mixed integer programming. The heuristic starts from the optimal solution of a linear relaxation of the mixed integer program. The rules of rounding of fractions to integers and the procedures of modification and verification of constructed heuristic in the following steps of algorithm are described. Results of computational experiments with the proposed heuristic algorithm are included. The computer processing times for heuristic and the algorithm with integer decision variables (optimal solution) are compared.
5
Content available remote Analiza porównawcza dwóch dwupoziomowych metod sterowania przepływem produktów przez elastyczną linię montażową z maszynami równoległymi
Magiera M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
147-156
PL
W artykule przedstawione są dwie dwupoziomowe metody sterowania przepływem produktów przez elastyczną linię montażową (ELM) z maszynami równoległymi. Każdy z wielu montowanych równocześnie produktów wymaga wykonania operacji na kolejnych, specjalistycznych maszynach. Przechodząc przez dane stadium, produkt obciąża tylko jedną maszynę spośród maszyn pracujących równolegle. Pomiędzy każdymi dwoma stadiami znajdują się bufory międzyoperacyjne. Na pierwszym poziomie każdej z przedstawionych metod wybierana jest tylko jedna sekwencja montażowa dla każdego produktu, spośród danych, alternatywnych sekwencji. W tym celu rozwiązywany jest problem optymalizacyjny - zadanie równoważenia obciążeń maszyn. Na drugim poziomie szeregowane są operacje montażowe. Narzędziem służącym do rozwiązania tych zadań jest programowanie matematyczne. Zadania te zostały sformułowane w postaci liniowych modeli matematycznych, zawierających binarne zmienne decyzyjne. W metodzie I na pierwszym poziomie równoważone są obciążenia poszczególnych stadiów, a operacje montażowe przydzielane są do maszyn (należących do wybranych na poziomie I stadiów) na poziomie II. W metodzie II natomiast na pierwszym poziomie równoważone są obciążenia wszystkich maszyn, przydział operacji do maszyn ma również miejsce na tym poziomie i poprzedza on szeregowanie operacji montażowych (poziom II). W celu porównania obu metod przeprowadzone zostały eksperymenty obliczeniowe. Porównane zostały m. in. długości uszeregowań oraz czasy uzyskiwania rozwiązań dla różnych rozmiarów zadań. W artykule przedstawione są wyniki tych eksperymentów.
EN
This paper presents two hierarchical, two-level methods of flow control in a flexible assembly line with parallel machines. A flexible assembly line consists of a set of assembly stations of various types each. The assembly line is capable of producing simultaneously a mix of product types. Each product loads no more than one machine of the assembly stage (collection of parallel machines). The intermediate buffers are placed between each two assembly stages. The alternative assembly sequences are given for each product. The selection of the best assembly sequences is at the top level. The problem objective is to select the assembly sequence for each product so as to balance the assembly stage work­loads (method I) or to balance the machine workloads (method II). The base-level is an scheduling of assembly operations. The problem of determination of the assignment of assembly tasks and part feeders to assembly machines with limited working space is solved at the base level in the method I, and at the top level - in the method II. Linear mathematical models with binary decision variables are created for described methods. The models are constructed for two different types of routes: fixed and alternative assembly routes. Results of computational experiments with the proposed approaches for flow control in a flexible assembly line are presented. The described methods are compared.
6
Modele matematyczne i heurystyki relaksacyjne szeregowania operacji dla elastycznych linii montażowych z maszynami równoległymi
Magiera M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
275-285
PL
W artykule przedstawiono nowe modele matematyczne szeregowania operacji dla elastycznych linii montażowych z maszynami równoległymi. Uwzględniony został przypadek, w którym między stadiami znajdują się bufory międzystadialne, oraz sytuacja, gdy nie ma tych buforów i ich rolę pełnią maszyny. W celu skrócenia czasu rozwiązywania zadań szeregowania operacji opracowano heurystyki relaksacyjne. Artykuł zawiera wyniki przeprowadzonych eksperymentów obliczeniowych.
EN
The paper describes new mixed integer programming models for operation scheduling for flexible assembly lines with parallel machines. The assembly line with intermediate buffers and the configuration without intermediate buffers are considered. Relaxation heuristics are proposed to reduce CPU time required for mixed integer programming. Results of computational experiment with the proposed MIP models and heuristics are included.
7
Dwupoziomowa metoda sterowania przepływem produktów przez elastyczną linię montażową z maszynami równoległymi
Magiera M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
265-274
PL
Na pierwszym poziomie opracowanej metody rozwiązywane jest zadanie równoważenia obciążeń maszyn, sformułowane dla elastycznej linii montażowej z maszynami równoległymi. Rozwiązanie tego zadania umożliwia wybór tylko jednej sekwencji montażowej dla każdego produktu, spośród danych alternatywnych sekwencji. Rozpatrzone zostały dwa przypadki: sztywnych, alternatywnych marszrut montażu. Na drugim poziomie szeregowane są operacje montażowe. W artykule zaprezentowano modele matematyczne oraz algorytmy heurystyczne (heurystyki relaksacyjne).
EN
The top-level of presented approach is a machine loading problem, allocation of assembly operations and part feeders among the stations and selection of best assembly sequences for all products so as to balance the station workloads. Fixed or alternative assembly routes are considered. The base-level is a scheduling of assembly operations. The paper presents new mathematical models and heuristic algorithms.
8
Algorytmy przybliżone dla wybranych problemów równoległego przydziału zasobów
Janczewski R., Małafiejski M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
299-312
PL
W pracy analizowane są własności uszeregowań dla wprowadzonego modelu systemu równoległego. W szczególnym przypadku, dla systemów równoległych z zadaniami dedykowanymi, ustaloną alokację zasobów możemy zamodelować wykorzystując tzw. grafy konfliktów. W chromatycznym modelu uporządkowań w czasie możemy sprowadzić znajdowanie uszeregowań optymalnych do znajdowania tych spośród multipokolorowań grafu konfliktów, których suma kolorów jest minimalna. Autorzy podają wstępną analizę własności modelu, wprowadzają algorytmy zachłanne oraz na podstawie uzyskanych lub cytowanych oszacowań pokazują algorytmy przybliżone.
EN
In the paper we consider the problem of scheduling multiprocessor tasks on dedicated processors. Assuming that there is only one alocation of resources the proposed general model can be reduced to the chromatic model of sequencing of tasks. The authors analyze the properties of the sum multicoloring problem of conflicting graphs and give some new bounds on the (multi) chromatic sum. Based on the introduced greedy algorithm we propose approximation algorithms to the problem P | fix j, G, r j | Sigma Cj.
9
Content available remote Algorytmy lokalnego przeszukiwania dla zagadnienia przepływowego z maszynami równoległymi i wymaganiami bez magazynowania
Bożejko W., Grabowski J., Pempera J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2001
|
T. 5, z. 1/2
87-93
PL
W niniejszej pracy rozważa się dwustanowiskowy problem przepływowy z maszynami równoległymi oraz ograniczeniami bez magazynowania z kryterium Cmax. Przedstawiono warunki związane z dopuszczalną kolejnością wykonywania zadań oraz nową definicję ruchu, tzw. ruch z korekcją. Proponowany ruch może być zastosowany w algorytmach lokalnego przeszukiwania. W pracy przedstawia się algorytmy bazujące na technikach przeszukiwania z zabronieniami, przeszukiwania genetycznego oraz symulowanego wyżarzania. Test komputerowy pokazuje przewagę zaproponowanego ruchu nad standardowymi ruchami stosowanymi do przepływowych problemów szeregowania zadań z maszynami równoległymi.
EN
The paper deals with two stages flow-shop scheduling problem with parallel machines, no store constrains and the makespan criterion. There are presented and discussed some conditions associated with the processing order and new definition of the move i.e. the move with correction. This move can be applied in any local search algorithms. The algorithms based on tabu search, genetic search and simulated annealing are presented. Computational experiments shown advantage proposed move over standards moves intend to flow-shop scheduling problem with parallel machines.
10
Szeregowanie zadań na dwóch stanowiskach z maszynami równoległymi ze specyficznymi wymaganiami
Grabowski J., Pempera J.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
101-109
PL
Praca poświęcona jest zagadnieniu szeregowania zadań w systemie przepływowym z ograniczeniami "bez czekania", który składa się z dwóch stanowisk zawierających po kilka maszyn w każdym stanowisku. W pracy przedstawia się algorytmy popraw, bazujące na technice przeszukiwania genetycznego, z zabronieniami oraz symulowanego wyżarzania. Przedstawiono wyniki obliczeniowe algorytmów oraz analizę porównawczą.
EN
In the paper two stages flow-shop problem with the "no-wait" requirements and parallel machines is considered. Some approximation algorithms, computational results and discussion of the performance of algorithms are presented.
11
Szeregowanie zadań na różnych maszynach równoległych z rozdziałem ograniczonych zasobów
Buchalski Z.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 123
77-84
PL
W pracy rozważany jest problem czasowo-optymalnego szeregowania zadań i rozdziału zasobów na różnych maszynach równoległych. Założono, że zadania są niezależne i niepodzielne. Liczna zadań do wykonania jest większa od liczby maszyn. Sformułowano model matematyczny problemu i podano algorytm heurystyczny. Przedstawiono wyniki eksperymentów obliczeniowych.
EN
In the paper we describe and solve time-optimal tasks scheduling and resources allocation problem on different, parallel machines. We assume that all tasks are independent nonpreemtive and number of tasks is greater than number of machines. The mathematical model of the problem is formulated and heuristic algorithm is presented. Some results of executed numerical experiments are presented.
12
System doradczy dla problemu optymalnego wyboru zestawu maszyn w dyskretnym systemie produkcyjnym.
Grabowski J., Smutnicki Cz., Wodecki M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 125
135-143
PL
W pracy rozważa się zagadnienie kolejnościowe, w którym, należy dokonać wyboru zestawu maszyn do wykonania zadania produkcyjnego w określonym terminie, aby koszt zakupu i eksploatacji maszyn był minimalny. Przedstawiono system ekspertowy, wspomagający proces podejmowania decyzji, tj. dobór optymalnej struktury wyposażenia (maszyn i urządzeń) oraz określenie kolejności wykonywanych operacji na wybranych maszynach (harmonogramowanie produkcji).
13
Problem przepływowy z maszynami równoległymi i przezbrojeniami. Algorytm tabu search.
Nowicki E.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 125
67-78
PL
W pracy przedstawia się szybki aproksymacyjny algorytm oparty na technice tabu dla problemu przepływowego z maszynami równoległymi i przezbrojeniami z kryterium minimalizującym moment wykonania wszystkich zadań. Specjalna metoda implementacji istotnie zwiększa prędkość algorytmu.
EN
A fast approximation algorithm for a problem of finding the minimum makespan in a flow shop with parallel machines and setup times is presented. The algorithm is based on a tabu search technique. A special method of implementation increases the speed of the algorithm significantly.
14
Harmonogramowanie pracy komórki produkcyjnej z kryterium dokładności dostarczania.
Smutnicki Cz.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 125
101-110
PL
W pracy rozważono problem dostarczania dokładnie na czas różnych elementów produkowanych przez komórkę produkcyjną, wyposażoną w pewną liczbę niejednorodnych, równoległych maszyn. Problem jest modelowany i rozwiązywany przy wykorzystaniu pewnych szczególnych własności oraz standardowych pojęć z klasycznej teorii szeregowania. Podejście zaproponowane i rozwijane w pracy może być stosowane do rozwiązywania bardziej złożonych problemów tego typu. Podejście to odwołuje się do klasycznych problemów szeregowania własności grafowych, tzw. własności blokowych oraz algorytmów lokalnych poszukiwań. Szczególną uwagę zwrócono na te własności teoretyczne, które są najbardziej użyteczne dla metody Poszukiwań z Pamięcią Adaptacyjną.
EN
In this paper we discuss a problem of perfect supply of various items produced by a manufacturing cell having a number of unrelated parallel machines. The problem is modelled and solved applying some special properties and a lot of conventional notions from the classic scheduling theory. The proposed and developed approach can be applied to solve more complex problems of this type. The base of this approach refers to classic scheduling problems, graph properties (including generalisation of so called block properties) and local search algorithms. A significant attention has been paid to these theoretical properties which are the most useful for the Adaptive Memory Search (AMS) algorithm.
first rewind previous Strona / 1 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ć.