Wyniki wyszukiwania - Biblioteka Nauki

1

Możliwości wykorzystania algorytmów opartych na ewolucji populacji do problemów szeregowania zadań

100%

Forkiewicz M.

Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej

|

2000

|

tom nr 15

51-58

PL

Zaprezentowano i porównano algorytmy: ewolucyjny, uczenia populacji i kolo-nii mrówek. Przedstawiono możliwości ich zastosowania do problemów szeregowania zadań deterministycznych oraz wyniki eksperymentu dla wybranego problemu

2

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.

Foundations of Computing and Decision Sciences

|

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.

3

Metoda tabu w problemach szeregowania zadań produkcyjnych.

80%

Nowicki E.

Prace Naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej. Monografie

|

1999

|

tom Vol. 101, nr 27

3-252

PL

W pracy przedstawia się metodologię projektowania i konstrukcji efektywnych algorytmów popraw dla obszernej klasy problemów szeregowania zadań produkcyjnych o średnim i dużym rozmiarze, bazując na ogólnym szkielecie techniki tabu i wykorzystując przy tym szereg nowych metod. Skuteczność tych metod została potwierdzona dowiedzionymi własnościami teoretycznymi i wynikami wszechstronnych badań testowych. W pracy można wyodrębnić dwie części. W pierwszej części prezentuje się poszczególne elementy techniki tabu, zwracając głównie uwagę na nowe metody, takie jak; konstrukcja pamięci krótkoterminowej opartej na oryginalnym pojęciu atrybutów rozwiązania i ruchu, strategia przeglądania sąsiedztw bazująca na pojęciu reprezentantów oraz techniki intensyfikacji i dywersyfikacji poszukiwań wykorzystując tzw. metodę skoku powrotnego. Następnie proponuje się reprezentacje rozwiązań dla wielu problemów szeregowania, określa ruchy, ich własności oraz metodologię konstrukcji odpowiednich dla nich atrybutów wraz z przedstawieniem efektywnych czasowo metod określających status danego ruchu. Wszystkie te elementy połączone w całość pozwalają na zbudowanie ogólnego oryginalnego schematu poszukiwań, który umożliwia projektowanie efektywnych algorytmów popraw z punktu widzenia jakości produkowanych rozwiązań oraz czasu obliczeń. W drugiej części pracy, korzystając z ogólnego narzędzia przedstawionego w części pierwszej, podaje szczegółową metodologię projektowania algorytmów popraw wraz z konkretnymi algorytmami dla poszczególnych grup problemów szeregowania zadań produkcyjnych. Przy wyborze tych grup kierowano się przede wszystkim ich praktyczną przydatnością oraz aktualnym stanem badań. W szczególności skupiono się na klasycznych zagadnieniach, do których należą problem przepływowy, gniazdowy i otwarty. Następnie rozważono problemy przepływowe z dodatkowymi ograniczeniami, takimi, jak: limitowana liczba palet oraz ograniczona pojemność buforów. Z kolei badano problem gniazdowy z maszynami wielofunkcyjnymi oraz niezerowymi czasami transportu i przezbrojeń. Na koniec skupiono się na problemie gniazdowym z operacjami wielomaszynowymi. Dla każdej grupy problemów podano oryginalne modele grafowe szczególnie przydatne przy konstrukcji algorytmów popraw, wykazano ich własności, skonstruowano sąsiedztwa oraz podano efektywne czasowe metody ich przeglądania. Dodatkowo w celu generowania rozwiązań początkowych zaproponowano szereg nowych algorytmów konstrukcyjnych; dal niektórych z nich oprócz analizy eksperymentalnej przeprowadzono także analizę najgorszego przypadku. Dla wszystkich analizowanych grup zagadnień przeprowadzono badania testowe algorytmów popraw bazujących na zaprezentowanych metodach. Do badań wykorzystano szereg przykładów adekwatnych dla danej grupy zagadnień i powszechnie wykorzystanych w literaturze do badania każdej nowej generacji algorytmów. Otrzymane wyniki wskazują na znaczną przewagę proponowanych tutaj algorytmów w stosunku do najlepszych algorytmów stosowanych dotychczas i to zarówno w aspekcie jakości produkowanych rozwiązań, jak i czasu obliczeń. W przypadku problemów, dla których są znane algorytmy popraw, proponowane algorytmy produkują rozwiązania od kilku do kilkunastu procent lepsze, w czasie od kilkunastu do kilkudziesięciu razy krótszym na komputerach o porównywalnej mocy obliczeniowej. Z kolei dla problemów, dla których nie ma w literaturze algorytmów popraw, proponowane algorytmy poprawiają rozwiązania dostarczane przez algorytmy konstrukcyjne, od kilkunastu do kilkudziesięciu procent w sensie wartości funkcji celu. Do otrzymania takich rozwiązań potrzebują one od kilku sekund do kilkunastu minut (w zależności od typu problemu i rozmiaru badanych instalacji) czasu pracy komputera klasy PC.

EN

The book presents the methodology of designing and constructing efficient local search algorithms recommended for medium- and large-size instances of a broad class pf job scheduling problems. The methodology is based on the general tabu search scheme extended next in the creative way by introduced new methods. The efficiency f the proposed methods has been confirmed by their theoretical properties as well as by the wide, careful experimental research. The books consists principally of two parts. The first part presents details of the tabu search technique, taking chiefly account of new original methods: short-term memory based on the notion of attributes of solution and move, strategy of the single neighbourhood search with the notion of representatives, intensification and diversification strategies with the use of back jumps on the search trajectory. After the introduction to extended tabu search approach, there have been proposed combinatorial representations of solutions for those scheduling problems that have been considered the most frequent. For these representations there have been presented moves, their characteristic properties, methodology of constructing suitable attributes, and efficient algorithms for tabu status examination. All these elements composed properly allow us to introduce a new general and original scheme of the local search which, in order, allow us to design solution algorithms efficient from two points of view: the quality of generated solutions and algorithm's running time. In the second part of the book, by applying the general tool introduced and developed in the former part, there has been presented detailed methodology of designing local search algorithms as well as practical implementations of such algorithms constructed for various groups of job scheduling problems. The selection of problems considered has been made taking attention of their practical applicability and the current state of scheduling research. In particular, consideration have been focused on classic versions of scheduling problems known as flow-, job- and open-shop. Further, these basic models have been extended by adding some real-life constraints. Precisely, the flow-shop problem has been analysed in the context of the limited number of pallets and the limited size of intermediate machine buffers; the job-shop problem has been considered in the in the context of multipurpose machines, transport times and set-up times; operations performed on multiple have also been considered. For each group problems, original models (very useful in the construction of local search algorithms) have been shown, the peculiar properties have been proved, the neighbourhoods constructed and efficient search methods given. Additionally, for the aim of generating starting solutions, there have been proposed several new constructive algorithms, for which experimental analyses as well as the worst case analyses have been carried out. Computer tests have been carried out for all improving algorithms designed for analysed groups of problems. Tests have been performed with the use of many common benchmark test instances known in the literature, adequate for each group. The results obtained show the superiority of the proposed algorithms over the best known ones taking account of both quality of generated solutions as well as running time. In the case of problems for which improving methods are known, the algorithms proposed provide solutions that are better by a few to over ten per cent at a time from 10 to 100 times shorter as compared to computers of comparable speed. For problems for which there are no improving algorithms in the literature, the algorithms designed improve solutions obtained from constructive algorithms in the range of a dozen to several dozen per cent in terms of the goal function value. In order to obtained such solutions they need from a few seconds to a dozen or so minutes (depending on the type of problem and instance size) of a PC running time.

4

PLA-based permutation-scheduling

80%

Jędrzejowicz J. , Jędrzejowicz P.

Foundations of Computing and Decision Sciences

|

2003

|

tom Vol. 28, No. 3

159-177

EN

The paper proposes the implementation of population learning algorithm (PLA) for solving three well-known NP-hard permutation-scheduling problems. PLA is a recently developed method belonging to the class of the population-based algorithms. One of possible applications of the PLA is solving difficult optimization problems. The first of the discussed problems involves scheduling tasks on a single machine against common due date with earliness and tardiness penalties. The second is known as the permutation flow shop problem. The third one involves scheduling tasks on a single machine with total weighted tardiness as a criterion. To evaluate the proposed implementations computational experiments have been carried. They involved solving available sets of benchmark problems and comparing the results with the optimum or best-known solutions. PLA has found better upper bounds on several benchmark instances. Experiments have also helped to identify some behavioral characteristics of the proposed algorithms.

5

Probabilistic tabu search for makespan minimization discrete-continuous scheduling

80%

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

Foundations of Computing and Decision Sciences

|

2003

|

tom Vol. 28, No. 4

211-222

EN

A problem of scheduling jobs on parallel, identical machines under an additional continuous resource to minimize the makespan is considered. Jobs are non-preemtable and independent, and all are available at the start of the process. The total amount of the continuous resource available at a time is limited, and the resource is a renewable one. Each job simultaneously requires for its processing a machine, and an amount (unknown in advance) of the continuous resource. Processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the makespan. The tabu search metaheuristic is presented to attack the problem. Probabilistic implementations of tabu search are discussed and examined. A computational experiment is described, and the results obtained for the probabilistic version of tabu search are compared to optimal solutions. A few conclusions and final remarks are presented.

6

h-Relation personalized communication strategy

80%

Paszyński M.

Computer Science

|

2010

|

tom Vol. 11

81-98

EN

This paper considers the communication patterns arising from the partition of geometrical domain into sub-domains, when data is exchanged between processors assigned to adjacent sub-domains. It presents the algorithm constructing bipartite graphs covering the graph representation of the partitioned domain, as well as the scheduling algorithm utilizing the coloring of the bipartite graphs. Specifically, when the communication pattern arises from the partition of a 2D geometric area, the planar graph representation of the domain is partitioned into not more than two bipartite graphs and a third graph with maximum vertex valency 2, by means of the presented algorithm. In the general case, the algorithm finds h — 1 or fewer bipartite graphs, where h is the maximum number of neighbors. Finally, the task of message scheduling is reduced to a set of independent scheduling problems over the bipartite graphs. The algorithms are supported by a theoretical discussion on their correctness and efficiency.

PL

W artykule omówiono problem szeregowania komunikacji pomiędzy procesorami przypisanymi do poddziedzin otrzymanych w wyniku podziału obszaru na podobszary, przy założeniu, że dane wymieniane są pomiędzy sąsiadującymi podobszarami. W artykule przedstawiony został algorytm tworzenia grafów dwudzielnych w oparciu o grafową reprezentację obszaru podzielonego na podobszary. Przedstawiono również algorytm szeregowania bazujący na kolorowaniu skonstruowanych grafów dwudzielnych. W szczególności, kiedy rozważamy komunikację w obrębie obszarów dwuwymiarowych, graf reprezentujący podzielony obszar dwuwymiarowy jest grafem planarnym, i rozważany algorytm zdekomponuje go na dwa grafy dwudzielne oraz trzeci graf o maksymalnej walencji wierzchołka równej 2. W ogólnym przypadku (np. gdy rozważamy obszary trójwymiarowe) przedstawiony algorytm znajdzie h — 1 lub mniej grafów dwudzielnych, gdzie h oznacza maksymalną liczbę sąsiadujących podobszarów. Zadanie szeregowania komunikatów zostało zredukowane do niezależnych zadań szeregowania na grafach dwudzielnych. Artykuł podsumowuje analiza teoretyczna poprawności i efektywności omówionych algorytmów.

7

Wybrane aspekty zarządzania operacjami lotniskowymi

80%

Kwasiborska A.

Logistyka

|

2007

|

tom nr 3

CD-CD

PL

Artykuł omawia wybrane aspekty organizacji operacji naziemnych samolotów w porcie lotniczym. Spostrzeżenia są podstawą do szczegółowej analizy operacji lotniskowych, które znacząco wpływają na przepustowość portu lotniczego. Ocena zarządzania procesem realizacji naziemnego ruchu lotniczego, pozwoli na wyznaczenie optymalnej konfiguracji startów dla znanych operacji lądowania samolotów. Dzięki dobrej koordynacji startów i kołowania przed startem można uzyskać wzrost przepustowości portu lotniczego oraz bezpieczeństwa na drogach startowych.

EN

In summary, this paper described possibilities the research in the field of optimal planning of airport ground operations, with a focus on runway operations, especially departures. Airport environment is a dynamic system, where people are involved in operations planning, decision-making and control. Airport departure management includes several control tasks, i.e. pushback, "engine start" time, taxiway entry, runway assignment and takeoff clearances and air traffic controllers exercise.

8

Wybrane algorytmy szeregowania na przykładzie obsługi pętli tramwajowej

80%

Gudowski B. , Wąs J.

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

|

2007

|

tom T. 11, z. 3

425-431

PL

W artykule opisano wybrane algorytmy szeregowania pociągów tramwajowych przybywających na pętlę z dostępnymi kilkoma peronami. Położony został nacisk na rozwiązania charakteryzujące się niedużą złożonością obliczeniową. Zaprezentowane algorytmy zostały przetestowane symulacyjnie i w artykule przedstawiono przykładowe wyniki tychże testów.

EN

In the article some algorithms of trams scheduling have been described. Trams arrive to terminus, where several platforms are available. The article focuses on solutions with Iow computational complexity. Presented algorithms has been tested using simulation and exemplary results has been included.

9

The combinatorics in divisible load scheduling

80%

Drozdowski M. , Lawenda M.

Foundations of Computing and Decision Sciences

|

2005

|

tom Vol. 30, No. 4

297-308

EN

Divisible load scheduling problem is studied in this work. Though tractability of this problem in the practical cases is considered as its great advantage, we show that it has a hard combinatorial core. Computational hardness and polynomial time solvability of some special cases are shown.

10

Heuristic procedures for allocating the continuous resource in discrete-continuous scheduling problems

80%

Józefowska J. , Waligóra G.

Foundations of Computing and Decision Sciences

|

2004

|

tom Vol. 29, No. 4

315-328

EN

A problem of scheduling jobs on parallel, identical machines under an additional continuous resource to minimize the makespan is considered. Jobs are non-preemtable and independent, and all are available at the start of the process. The total amount of the continuous resource available at a time is limited, and the resource is a renewable one. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. Processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the makespan. A heuristic approach to allocating the continuous resource is proposed. Four heuristic procedures are presented and discussed. A computational experiment is described, and the results produced by the heuristics are compared with optimal solutions. Some conclusions and directions for further research are given.

11

Nowe własności harmonogramów cyklicznych w systemie przepływowym

60%

Smutnicki C. , Smutnicki A.

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

|

2007

|

tom T. 11, z. 1-2

275-285

PL

Praca omawia deterministyczny wariant problemu optymalizacji przebiegu cyklu wytwórczego w przepływowym systemie wytwarzania powtarzalnego z ograniczeniami składowania pomiędzy stanowiskami. Wychodząc od wcześniejszych prac autora dotyczących tego problemu, w niniejszej pracy przedstawiono pewne, także nowe, własności wraz z niepublikowanymi dotychczas dowodami, efektywne algorytmy wyznaczania harmonogramu dla ustalonej kolejności realizacji zadań w cyklu oraz pewne wyniki badań eksperymentalnych.

EN

This paper deals with the deterministic variant of the problem of optimization cycle run in flow shop repetitive manufacturing system with no store constraints. Starting from earlier papers of the author on this subject, in this paper there are presented some, also new, properties with unpublished yet proofs, efficient algorithms of finding schedule for fixed order of processing tasks in the cycle as well as some experimental results.

12

Scheduling problems with a common due window assignment: a survey

60%

Janiak A. , Kwiatkowski T. , Lichtenstein M.

International Journal of Applied Mathematics and Computer Science

|

2013

|

tom Vol. 23, no. 1

231--241

EN

In this article a survey of studies on scheduling problems with a common due window assignment and earliness/tardiness penalty functions is presented. A due window is a generalization of the classical due date and describes a time interval in which a job should be finished. If a job is completed before or after the due window, it incurs an earliness or a tardiness penalty, respectively. In this survey we separately analyse the classical models with job-independent and job-dependent earliness/tardiness penalty functions and some other more complicated models. We describe the computational complexity of the problems and the main features of the approaches developed to solve them. Particular attention is paid to practical applications of the analysed models. As turns out, some complicated models combining classical scheduling problems with, e.g., learning and aging effects have no reasonable practical justification in the literature.

13

Zautomatyzowane szeregowanie zadań produkcyjnych w małym systemie wytwórczym

60%

Cechowicz R.

Inżynieria Maszyn

|

2006

|

tom R. 11, z. 1

66-72

PL

W artykule przedstawiono praktyczny przykład rozwiązania problemu szeregowania zadań produkcyjnych w małym zakładzie produkcyjnym zarządzanym przez system MRP. Zadaniem systemu szeregowania było przetworzenie listy zamówień systemu MRP tak, aby stała się ona planem, który da się wykonać oraz minimalizacja tego planu. Wygenerowany w ten sposób nowy plan obowiązywał aż do następnej aktualizacji listy zamówień w systemie MRP. W systemie przewidziano możliwość korekty planu na podstawie danych z monitoringu produkcji oraz uwzględnienia preferencji lokalnego nadzorcy systemu (priorytety zamówień, maszyny alternatywne). Dzięki zastosowaniu dwustopniowego algorytmu szeregowania do tworzenia kolejnych wersji harmonogramu produkcji były wykorzystywane najlepsze rozwiązania otrzymane w przeszłości. Artykuł został zilustrowany przykładami harmonogramów. Opisywane rozwiązanie nie zostało zaimplementowane w zakładzie ze względu na zmianę sposobu przekazywania zamówień przez zleceniodawcę.

EN

A job shop scheduling system for a small enterprise was presented in this article. The system provided local scheduling for orders retrieved from a remote MRP database. A two-stage scheduling algorithm consisting of operation dispatching and schedule optimization stages was employed. The proposed solution performed well in laboratory tests and allowed for continuous plan optimization during subsequent updates of the information stored in the MRP system.

14

Szeregowanie zadań cyklicznych z wykorzystaniem algorytmów priorytetowych

60%

Jamroż L. , Raszka J.

Czasopismo Techniczne. Nauki Podstawowe

|

2011

|

tom R. 108, z. 1-NP

141-150

PL

W artykule przedstawione jest zagadnienie szeregowania zadań cyklicznych w systemach czasu rzeczywistego. Oprogramowanie aplikacyjne systemów, najczęściej składa się z tego typu zadań o różnych ograniczeniach czasowych, które nie mogą być przekroczone. Stosowaną metodą szeregowania niezależnych zadań cyklicznych jest przydzielanie im priorytetów. Strategia doboru priorytetów oraz zasada posługiwania się nimi określona jest algorytmem szeregowania. Rozważane są priorytetowe algorytmy RMS, DMS oraz EDF, dla których przedstawione są warunki szeregowalności.

EN

This paper is devoted to the scheduling of cyclic tasks in real-time systems. The application programs of such systems have been defined as those containing cyclic tasks that have deadlines that cannot be missed. The priority algorithms: RMS, DMS and EDF for scheduling set of independent cyclic tasks are considered. There are several rules basing on which the priorities are assigned to the tasks and then the tasks are being scheduled. Schedulability constrains are considered which guarantee the deadlines of cyclic tasks.

15

Runway scheduling with holding pattern and service priority

60%

Martyna J.

Automatyka / Automatics

|

2012

|

tom Vol. 16, no. 2

137-144

EN

In this paper, we have studied a scheduling problem associated with air-traffic control, in which a set of airerafts are about to land on a single runway. The objectives are to maximize the minimum time elapsed between any two consecutive landings, minimize the maximum number of times a plane enters a holding time, likewise including the priority of aircraft landings. We use the mixed integer three dimensional problem formulation that allows us to solve large instances of the general problem. Our numerical results validated the effectiveness of the proposed method.

PL

W artykule przedstawiono problem szeregowania samolotów podchodzących do lądowania i startujących na drodze startowej. Przyjęto, że celem szeregowania jest minimalizacja maksymalnej liczby samolotów oczekujących w powietrzu na lądowanie przy uwzględnieniu ich priorytetów. Problem sformułowano jako trójwymiarowe mieszane programowanie całkowitoliczbowe. Dostarczone przykłady potwierdziły efektywność proponowanej metody rozwiązania tego problemu.

16

Using a vision cognitive algorithm to schedule virtual machines

51%

Zhao J. , Mhedheb Y. , Tao J. , Jrad F. , Liu Q. , Streit A.

International Journal of Applied Mathematics and Computer Science

|

2014

|

tom Vol. 24, no. 3

535--550

EN

Scheduling virtual machines is a major research topic for cloud computing, because it directly influences the performance, the operation cost and the quality of services. A large cloud center is normally equipped with several hundred thousand physical machines. The mission of the scheduler is to select the best one to host a virtual machine. This is an NP-hard global optimization problem with grand challenges for researchers. This work studies the Virtual Machine (VM) scheduling problem on the cloud. Our primary concern with VM scheduling is the energy consumption, because the largest part of a cloud center operation cost goes to the kilowatts used. We designed a scheduling algorithm that allocates an incoming virtual machine instance on the host machine, which results in the lowest energy consumption of the entire system. More specifically, we developed a new algorithm, called vision cognition, to solve the global optimization problem. This algorithm is inspired by the observation of how human eyes see directly the smallest/largest item without comparing them pairwisely. We theoretically proved that the algorithm works correctly and converges fast. Practically, we validated the novel algorithm, together with the scheduling concept, using a simulation approach. The adopted cloud simulator models different cloud infrastructures with various properties and detailed runtime information that can usually not be acquired from real clouds. The experimental results demonstrate the benefit of our approach in terms of reducing the cloud center energy consumption.

17

Dynamic scheduling for agent based manufacturing systems

51%

Madejski J.

Journal of Achievements in Materials and Manufacturing Engineering

|

2010

|

tom Vol. 40, nr 1

66-69

EN

Purpose: Development of the decision making architecture for the multi-agent societies with temporal restrictions. General ideas for the necessary architecture based on the blackboard one is presented. Design/methodology/approach: Fuzzy logic approach that makes it possible to reach suboptimal solutions within the acceptable timeframe. Development of the relevant systems calls for compiling the experience gathered over the years in the system served by human ‘agents’. Multiagent systems negotiation needs were analysed and cooperation issues in the form of clustering, cloning, and learning were analysed in search for the relevant tools. Findings: Detailed review of the approach to development of the agent based Intelligent Manufacturing from the fundamental considerations to the latest hands-on developments. Research limitations/implications: Many presented technologies call for detailed study before they can be implemented in practice. Originality/value: Analysis of the local interactions among agents meeting the real-time reaction requirements.

18

Mean Squared Load Criteria for Scheduling Independent Tasks

51%

Dzemyda G.

International Journal of Applied Mathematics and Computer Science

|

1999

|

tom Vol. 9, no 4

939-954

EN

Results of this paper extend the set of criteria which characterize the scheduling quality as well as the set of possible scheduling strategies. A new view on the minimum makespan criterion is presented in terms of the mean squared load of processing units. This leads in turn to the development of new scheduling algorithms. The interaction between processes of minimizing the new criteria and the maximum finishing time (makespan of the schedule) was discovered. We show the possibility of minimizing the maximum finishing time by minimizing the new criteria that characterize the mean squared load of processing units. Moreover, the optimal workload of processing units determined with the use of the proposed criteria is usually smoother (more balanced) than that found for traditional ones.

19

Comparative analysis of two hierarchical methods of assembly planning for producers of electric and electronic equipment

51%

Magiera M.

Przegląd Elektrotechniczny

|

2015

|

tom R. 91, nr 4

86--90

PL

Porównano dwie dwupoziomowe metody planowania montażu, przeznaczone dla producentów sprzętu elektrycznego i elektronicznego. Zbudowano je dla elastycznych linii montażowych z maszynami równoległymi. Na górnym poziomie opracowanych metod rozwiązywane jest zadanie równoważenia obciążeń maszyn (w metodzie I) lub równoważenia obciążeń stadiów (w metodzie II). Równocześnie dla każdego produktu wybierana jest jedna sekwencja montażowa. Na dolnym poziomie szeregowane są operacje montażowe. Przedstawiono wyniki eksperymentów obliczeniowych.

EN

The two two-level methods of assembly planning for producers of electric and electronic equipment are compared. The methods are constructed for flexible assembly lines with parallel machines. At the upper level of the prepared methods, a task is solved for balancing machine workload (in the method I) or a task for balancing assembly stages workload (in the method II). Simultaneously, only one assembly plan is selected for each product type. At the lower level, assembly tasks are scheduling. The results of calculation experiments are presented.

20

Sposób szeregowania zadań dla jednej maszyny o ograniczonych zasobach

51%

Cechowicz R.

Pomiary Automatyka Kontrola

|

2011

|

tom R. 57, nr 9

1093-1096

PL

W artykule opisano system szeregowania zadań niepodzielnych na jednej maszynie. System pozwala zoptymalizować plan produkcji poprzez ograniczenie ilości operacji transportowych i pomocniczych oraz poprzez poszukiwanie takiej kolejności realizacji zadań, dla której łączny czas wykonania będzie możliwie najmniejszy. Zastosowano zmodyfikowany algorytm genetyczny pozwalający na częściowe dostrojenie procesu do struktury danych. Testy przeprowadzone zarówno na danych dostępnych publicznie, jak i na danych pochodzących ze środowiska wytwórczego udowodniły skuteczność przyjętych rozwiązań.

EN

A system for scheduling indivisible tasks on a single, periodically accessible machine is presented in this paper. Because of the constrains existing in the environment, the scheduling problem presented here is similar to the one-dimensional bin-packing. The tasks, stacked on a palettes (Fig.1), were transported to the machine. The palette caould be replaced by another one only after completing all the tasks assigned to it. Each task was defined by an execution time Tz and an auxiliary time Tp. The transportation time To was added to the last task from each palette and to the last task executed within the machine availability period Tm (Fig.2). A modified genetic algorithm was used for the scheduling, where the parameter K defined the number of gene changeovers (representing changing the sequence of palettes and changing the sequence of tasks within a palette) during one mutation. The results obtained for the data available in public [13] and in selected publications are presented in Tab.1. It was noted that the distribution of scheduling results (fitness=Cmax) could be modified by changing the parameter K (Figs.4 and 6). The observation was proved statistically for the data from the manufacturing system by means of the median test run for the set of 500 results, 50 for each K=1..10 (χ2=19, df=9, p=0,0254<0,05). The results of the test proved that the scheduling algorithm could be tuned for speed by adjusting the value of K. Assuming that the process was random, it could be calculated that for K=5 the expected time of getting the solution Cmax<2050, expressed in the number of generations, was the shortest (assumed confidence level 0.99). The scheduling system allowed the definition of individual machine availability periods and taking into account the restrictions of the transport system (the allowed sequences of palette retrieval).