Wyniki wyszukiwania - BazTech

1

Scheduling battery charging jobs with linearly decreasing power demands to minimize the total time

Różycki R., Waligóra G., Węglarz J.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2020

|

Vol. 68, nr 2

299--306

EN

In this work we consider a problem from the field of power- and energy-aware scheduling, in which a set of batteries have to be charged in a minimum time. The formulated problem is to schedule independent and nonpreemptable jobs to minimize the schedule length, where each job requires some amount of power and consumes a certain amount of energy during its processing. We assume that the power demand of each job linearly decreases with time, as it is the case when Li-ion batteries are being charged. For the assumed job model we prove that each next job should be started as soon as the required amount of power is available. Basing on the proven theorem we formulate a procedure generating a minimum-length schedule for an assumed order of jobs. We also analyze the case of identical jobs, and show some interesting properties of this case.

2

Improving energy efficiency of supercomputer systems through software-aided liquid cooling management

Januszewski R., Różycki R., Waligóra G.

Foundations of Computing and Decision Sciences

|

2018

|

Vol. 43, No. 2

89--103

EN

Many fields of modern science rely more and more on the immense computing power of supercomputers. Modern, multi-thousand node systems can consume megawatts of electrical energy in highly uneven manner, challenging the data center infrastructure, both power and cooling coils. The traditional way of managing the infrastructure makes each subsystem of a data center (e.g. cooling) independent from all other in the way it relies only on local sensors to manage the infrastructure. The erratic nature of computing in a large data center makes this approach suboptimal. In the paper we show that by challenging the traditional split between the infrastructure and the computing equipment, one can gain significant boost in energy efficiency of the entire ecosystem. A solution that predicts cooling power demand basing on the information from a supercomputer resource manager, and then sets up the parameters of the cooling loop, is presented along with potential benefits in terms of reduction of the power draw.

3

Scheduling preemptable jobs on identical processors under varying availability of an additional continuous resource

Różycki R., Waligóra G., Węglarz J.

International Journal of Applied Mathematics and Computer Science

|

2016

|

Vol. 26, no. 3

693--706

EN

In this work we consider a problem of scheduling preemptable, independent jobs, characterized by the fact that their processing speeds depend on the amounts of a continuous, renewable resource allocated to jobs at a time. Jobs are scheduled on parallel, identical machines, with the criterion of minimization of the schedule length. Since two categories of resources occur in the problem: discrete (set of machines) and continuous, it is generally called a discrete-continuous scheduling problem. The model studied in this paper allows the total available amount of the continuous resource to vary over time, which is a practically important generalization that has not been considered yet for discrete-continuous scheduling problems. For this model we give some properties of optimal schedules on a basis of which we propose a general methodology for solving the considered class of problems. The methodology uses a two-phase approach in which, firstly, an assignment of machines to jobs is defined and, secondly, for this assignment an optimal continuous resource allocation is found by solving an appropriate mathematical programming problem. In the approach various cases are considered, following from assumptions made on the form of the processing speed functions of jobs. For each case an iterative algorithm is designed, leading to an optimal solution in a finite number of steps.

4

Discrete-continuous project scheduling with preemptable activities

Różycki R., Waligóra G., Węglarz J.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2016

|

Vol. 64, nr 2

383--393

EN

In this paper, discrete-continuous project scheduling problems with preemptable activities are considered. In these problems, activities of a project simultaneously require discrete and continuous resources for their execution. The activities are preemptable, and the processing rate of each activity is a continuous, increasing function of the amount of a single continuous resource allotted to the activity at a time. The problem is to find a precedence- and discrete resource-feasible schedule and, simultaneously, continuous resource allocation that would minimize the project duration. Convex and concave processing rate functions are considered separately. We show that for convex functions the problem is simple, whereas for concave functions a special methodology has to be developed. We discuss the methodology for three cases of the problem: no discrete resource constraints, one discrete resource being a set of parallel, identical machines, and an arbitrary number of discrete resources. In each case we analyze separately independent and precedence-related activities. Some conclusions and directions for future research are given.

5

Computational Experiments for Scheduling Workflow Applications in Grid Environment

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

Computational Methods in Science and Technology

|

2011

|

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.

6

Maksymalizacja zaktualizowanej wartości netto w dyskretno-ciągłych problemach rozdziału zasobów

Waligóra G.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2008

|

z. 151

73-78

PL

W pracy rozważany jest dyskretno-ciągły problem rozdziału zasobów ze zdyskontowanymi dodatnimi przepływami gotówkowymi. Kryterium jest maksymalizacja zaktualizowanej wartości netto. Rozważane są wypukłe i wklęsłe funkcje szybkości wykonywania czynności w zależności od przydzielonej ilości zasobu ciągłego. Przedstawiona jest metodyka podejścia do rozwiązania problemu w przypadku obu klas funkcji.

EN

A discrete-continuous project scheduling problem with positive discounted cash flows is considered. The objective is the maximization of the net present value. Convex and concave processing rate functions of activities are analyzed. Methodology for solving the problem in the cases of both considered classes of functions is presented.

7

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

Józefowska J., Waligóra G.

Foundations of Computing and Decision Sciences

|

2004

|

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.

8

Probabilistic tabu search for makespan minimization discrete-continuous scheduling

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

Foundations of Computing and Decision Sciences

|

2003

|

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.

9

Maksymalizacja zaktualizowanej wartości netto w problemach rozdziału zasobów z wieloma sposobami wykonywania czynności

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

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

z. 134

255-264

PL

W pracy rozważa się problem rozdziału zasobów z wieloma sposobami wykonywania czynności. Z terminem zakończenia każdej czynności związany jest dodatni przepływ gotówkowy. Celem jest znalezienie zasobowe i kolejnościowo dopuszczalnego uszeregowania, które maksymalizuje sumaryczną zaktualizowaną wartość netto wszystkich przepływów gotówkowych projektu. Zaproponowano dwa algorytmy metaheurystyczne: algorytm symulowanego wyżarzania oraz algorytm przeszukiwania tabu. Obszerny eksperyment obliczeniowy stanowi podstawę do porównania obydwu algorytmów.

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 completion of each activity. The objective is the maximization of the net present value of all cash flows, subject to precedence and resource constraints. Local search metaheuristics: simulated annealing and tabu search are proposed to solve this problem. Both algorithms are compared on the basis of an extensive computational experiment.

10

Maksymalizacja zaktualizowanej wartości netto w problemach rozdziału zasobów - przegląd modeli i algorytmów

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

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

z. 134

243-254

PL

Rozważane są problemy rozdziału zasobów z kryterium maksymalizacji zaktualizowanej wartości netto. Praca zawiera przegląd modeli i algorytmów dotyczących rozważanej klasy problemów szeregowania i jednocześnie jest próbą podsumowania aktualnego stanu badań w tym zakresie oraz ukazania na tym tle nowych kierunków badawczych.

EN

Project scheduling problems with the maximization of the net present value (NPV) criterion are considered. The paper surveys models and algorithms concerning this class of problems. The state-of-the-art in this area and the future research directions are presented.

11

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

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

Foundations of Computing and Decision Sciences

|

2002

|

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.

12

Rozwiązywanie dyskretno-ciągłych problemów rozdziału zasobów przez dyskretyzację zasobu ciągłego

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

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

z. 129

221-229

PL

W artykule rozważa się dyskretno-ciągły problem rozdziału zasobów. W problemach tego typu do wykonania zadań konieczne są jednocześnie zasoby ciągłe i dyskretne, przy czym wszystkie zasoby są odnawialne. Szybkość wykonania każdej czynności zależy od przydzielonej jej w danej chwili ilości zasobu ciągłego. Czynności są niepodzielne, a celem jest minimalizacja długości uszeregowania. W pracy zaproponowano metodę rozwiązania polegającą na transformacji powyższego problemu do klasycznego problemu rozdziału zasobów z wieloma sposobami wykonywania czynności.

EN

In this paper a discrete-continuous project scheduling problem is considered. In this problem activities simultaneously require for their processing discrete and continuous resources. The processing rate of each activity depends on the amount of the continuous resource allotted to this activity at a time. All the resources are renewable ones. The activities are nonpreemtable and the objective is to minimize the makespan. Discretization of this problem leading to a classical (i.e. discrete) project scheduling problem in the multimode version is presented.

13

Algorytm symulowanego wyżarzania dla problemu rozdziału zasobów z wieloma sposobami wykonywania czynności

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

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

z. 129

211-220

PL

W pracy rozważa się problem rozdziału zasobów z wieloma sposobami wykonywania czynności. Celem jest znalezienie takiego uszeregowania dopuszczalnego, które minimalizuje czas trwania projektu. Zaproponowano algorytm symulowanego wyżarzania dla tego problemu oraz przedstawiono wyniki eksperymentu obliczeniowego.

EN

In this paper a multi-mode resource-constrained project scheduling problem is considered. The objective is to find a feasible solution which minimizes the makespan. A simulated annealing algorithm is developed to solve this problem and a performance analysis of this algorithm is presented on the basis of a comprehensive computational experiment.

14

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.

15

Optymalizacja przydziału zasobów ciągłych i dyskretnych w kompleksie operacji niepodzielnych

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

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

1998

|

z. 123

211-220

PL

W niniejszej pracy rozważa się zbiór operacji niepodzielnych, w którym określono relację częściowego porządku oraz zbiór zasobów odnawialnych, podzielonych w sposób dyskretny i jeden zasób podzielony w sposób ciągły. Chwilowa szybkość wykonywania operacji jest ciągłą, niemalejącą funkcją ilości zasobu ciągłego przydzielonego do tej operacji w danej chwili. Przedstawiono ogólne własności i sposoby wyznaczania rozwiązań optymalnych ze względu na czas realizacji całego zbioru operacji, oraz trzy algorytmy przybliżone wykorzystujące ideę lokalnego przeszukiwania, których efektywność porównano na podstawie wyników eksperymentu obliczeniowego.

EN

We consider a project consisting of precedence and resource-constrained activities which require renewable resources of two types: discrete and continuous ones. The processing rate of an activity is a continuous, nondecreasing and concave function of the amount of a continuous resource allotted to this activity at a time. The problem is to find an assignment of discrete resources and, simultaneously, a continuous resource allocation which minimize the project duration. We give basic properties and methods of constructing optimal schedules and present local search metaheurstics adopted for the considered problem. Finally, we provide results of computational experiments.

16

Minimalizacja maksymalnego opóźnienia w dyskretno-ciągłych problemach szeregowania - algorytmy heurystyczne

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

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

1998

|

z. 123

221-231

PL

W pracy rozważa się dyskretno - ciągłe problemy szeregowania zadań z kryterium minimalizacji maksymalnego opóźnienia. Zakłada się, że zadania są niezależne i niepodzielne. Zasób dyskretny stanowią identyczne i równoległe maszyny, zasób ciągły jest odnawialny, a chwilowa prędkość wykonywania zadania zależy od ilości zasobu ciągłego przydzielonego zadaniu w danej chwili. Zaproponowano algorytmy przybliżone, które porównano na podstawie eksperymentu obliczeniowego.

EN

In this paper we consider discrete- continuous scheduling problems with the objective to minimize the maximum lateness. We assume that jobs are independent and nonpreemptable and there are two types of resourses. The discrete resource is represented by a set of identical and parallel machines, the continuous one is renewable and the processing rate of a job at time t depends of the amount of the continuous resource allotted to this job at time t. Simple heuristic algorithms are proposed and compared on a basis of a computational experiment. The algorithms are also compared with other heuristics proposed in the literature. Their main advantage is short computational time. They are outperformed by metaheuristic algorithms (Tabu Search, Simulated Annealing and Genetic Algorithms), however at a cost of much larger computational effort.