Wyniki wyszukiwania - BazTech

1

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

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

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

Algorithms Using List Scheduling and Greedy Strategies for Scheduling in the Flowshop with Resource Constraints

Figielska E.

Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki

|

2014

|

nr 11

29--39

EN

The paper addresses the problem of scheduling in the two-stage flowshop with parallel unrelated machines and renewable resource constraints. The objective is minimization of makespan. The problem is NP-hard. Fast heuristic algorithms using list scheduling and greedy strategies are proposed. For evaluation of the performance of the algorithms computational experiments are performed on randomly generated test problems, and results are reported.

5

Linear programming & metaheuristic approach for scheduling in the hybrid flowshop with resource constraints

Figielska E.

Control and Cybernetics

|

2011

|

Vol. 40, no 4

1209-1230

EN

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines and additional renewable resources. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which join the linear programming based procedures with metaheuristic algorithms: genetic, simulated annealing and tabu search algorithm. The performance of the proposed algorithms is experimentally evaluated by comparing the solutions with a lower bound on the optimal makespan. Results of a computational experiment show that these algorithms are able to produce good solutions in short computation time and that the metaheuristics significantly improve the results for the most difficult problems.

6

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.

7

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 workloads (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.

8

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.

9

Parallel tabu search algorithms for scheduling independent jobs on parallel machines to minimize the makespan

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

Foundations of Computing and Decision Sciences

|

1999

|

Vol. 24, No. 3

119-140

EN

In this paper implementations of parallel Tabu Search algorithms for solving the problem of scheduling nonpreemtable, independent jobs on parallel, identical machines to minimize the makespan are presented. F our different types of parallel Tabu Search based on Michael J. Flynn , s computer architectural classification scheme are considered. A computational experiment is described performed in two different parallel computer architectures: multiprocessor scalar system with shared memory and scalable supercomputing system with distributed memory .A comparison of results obtained for sequential versions of the algorithm as well as parallel ones in both the architectures is presented. Some conclusions and final remarks are included.