Wyniki wyszukiwania - BazTech

1

Optimization of a task schedule for teams with members having various skills

Bazan Marek, Smutnicki Czesław, Marchwiany Maciej E.

International Journal of Electronics and Telecommunications

|

2024

|

Vol. 70, No. 1

59--69

EN

We consider the real-life problem of planning tasks for teams in a corporation, in conditions of some restrictions. The problem takes into account various constraints, such as for instance flexible working hours, common meeting periods, time set aside for self-learning, lunchtimes and periodic performance of tasks. Additionally, only a part of the team may participate in meetings, and each team member may have their own periodic tasks such as self-development. We propose an algorithm that is an extension of the algorithm dedicated for scheduling on parallel unrelated processors with the makespan criterion. Our approach assumes that each task can be defined by a subset of employees or an entire team. However, each worker is of a different efficiency, so task completion times may differ. Moreover, the tasks are prioritized. The problem is NP-hard. Numerical experiments cover benchmarks with 10 instances of 100 tasks assigned to a 5-person team. For all instances, various algorithms such as branch-and-bound, genetic and tabu search have been tested.

2

Accelerating backtrack search with a best-first-search strategy

Mann Z. Á., Szép T.

International Journal of Applied Mathematics and Computer Science

|

2014

|

Vol. 24, no. 4

901--916

EN

Backtrack-style exhaustive search algorithms for NP-hard problems tend to have large variance in their runtime. This is because “fortunate” branching decisions can lead to finding a solution quickly, whereas “unfortunate” decisions in another run can lead the algorithm to a region of the search space with no solutions. In the literature, frequent restarting has been suggested as a means to overcome this problem. In this paper, we propose a more sophisticated approach: a best-first-search heuristic to quickly move between parts of the search space, always concentrating on the most promising region. We describe how this idea can be efficiently incorporated into a backtrack search algorithm, without sacrificing optimality. Moreover, we demonstrate empirically that, for hard solvable problem instances, the new approach provides significantly higher speed-up than frequent restarting.

3

A Parallel Branch and Bound Approach to Optimal Power Flow with Discrete Variables

Moreira J. C., Míguez E., Vilachá C., Otero A. F.

Przegląd Elektrotechniczny

|

2013

|

R. 89, nr 3a

47--52

EN

An optimal power flow (OPF) with discrete variables is a non-convex, nonlinear combinatorial problem. Usually the discrete variables present in an OPF are treated as continuous variables. The solution obtained using this method is clearly infeasible, but it is considered to be close to the discrete real solution and can be attained easily without producing an excessive degradation in optimality. These hypotheses can easily be refuted by demonstrating the need for a more robust general mechanism for treating the discrete variables in the OPF. Finding the exact solution is intractable due to the high computing cost it requires--this fact causes the heuristic techniques to be seen as a natural way to obtain good solutions quickly. This article presents an algorithm based on a branch and bound technique that, with the help of the parallel computing power a personal computer (PC) provides, allows pseudo-optimal solutions to be attained with good calculating times. The numerical results obtained by applying the technique proposed in IEEE networks of 118 and 300 nodes and a real size network derived from the Spanish transport network, demonstrate that the algorithm proposed has good execution times, provides solutions close to the optimum, and naturally manages the infeasibilities that are produced during the process.

PL

Obliczenie optymalnego rozpływu mocy dla zmiennych dyskretnych jest problemem nieliniowym kombinacyjnym. Zwykle zakłada się, że zmienne dyskretne są traktowane jak zmienne ciągłe. Ta metoda uniemożliwia uzyskanie dokładnego wyniku w akceptowalnym czasie. Stąd powstało wiele technik heurystycznych, umożliwiających szybkie uzyskanie wyniku o dobrej dokładności. W artykule zaprezentowano algorytm na podstawie techniki podziału i ograniczeń, która, przy zastosowaniu obliczeń równoległych w nowoczesnych komputerach PC, pozwala na szybkie uzyskanie wyniku sub-optymalnego. Algorytm zastosowano do obliczeń sieci IEEE o 118 I 300 węzłach oraz rzeczywistej sieci, uzyskując krótkie czasy obliczeń i wyniki bliskie optymalnym.

4

Scatter Search based algorithms for min-max regret task scheduling problems with interval uncertainty

Józefczyk J., Siepak M.

Control and Cybernetics

|

2013

|

Vol. 42, no. 3

667--698

EN

Uncertain versions of three task scheduling problems: P║Cmax, F2║Cmax, R║Σ Cj are investigated. Parametric uncertainty is only considered which is represented by intervals. It is assumed that values of execution times of tasks are not a priori given, and they belong to the intervals of known bounds. No distributions additionally characterizing the uncertain parameters are assumed. The regret is used as the basis for a criterion evaluating the uncertainty. In a consequence, min-max regret combinatorial problems are solved. Heuristic algorithms based on Scatter Search are proposed. They are evaluated via computational experiments and compared to a simple middle intervals heuristics and to exact solutions for small instances of the problems considered.

5

Szeregowanie zadań o zmiennych wartościach z różnymi terminami dostępności – algorytmy rozwiązania

Janiak A., Kołodka P., Krysiak T.

Przegląd Elektrotechniczny

|

2010

|

R. 86, nr 9

91-96

PL

Praca dotyczy problemu szeregowania zadań o zmiennych wartościach i niezerowych terminach dostępności na pojedynczej maszynie. Analizowano potęgowy model wartości zadań, a jako kryterium – maksymalizację sumy wartości wszystkich zadań. Problem powyższy jest co najmniej NP-trudny. Do jego rozwiązania skonstruowano algorytm dokładny typu podziału i ograniczeń oraz szereg algorytmów heurystycznych typu konstrukcyjnego, a także jeden typu popraw. Efektywność skonstruowanych algorytmów przebadano eksperymentalnie.

EN

The paper deals with a problem of scheduling jobs with changeable job values and non-zero release dates on a single machine. A power model of job values and the criterion of maximization of the total job values are analyzed. The above problem is at least NP-hard. Thus, a branch and bound exact algorithm and some heuristic algorithms (constructive and improving type) have been developed. Their efficiency have been examined experimentally.

6

Integrating pivot based search with branch and bound for binary MIPs

Lokketangen A., Woodruff D.

Control and Cybernetics

|

2000

|

Vol. 29, no 3

741-759

EN

This paper examines integration of a sophisticated, pivot-based tabu search into branch and bound for 0-1 MIPS and global diversification tests using chunking. Issues related to behavior of a tabu search within a branch and bound algorithm are analyzed using computational experiments. Results are presented showing that the inclusion of the local search sometimes results in fewer and nodes and lower CPU times even when used in a callback mode. The main benefit in incorporating a pivot based heuristic is that an integer feasible solution can be found earlier in the branching process. Computational experiments are presented showing that for some instances the overall search time is improved, while for some others the tabu search can find good solutions quickly.

7

Parallel Branch and Bound Algorithms for the Two-machine Flow Shop Problem with Limited Machine Availability

Błażewicz J., Formanowicz P., Kubiak W., Przysucha M., Schmidt G.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2000

|

Vol. 48, nr 1

105-115

EN

The paper presents parallel versions of a branch and bound algorithm for scheduling jobs in the two-machine flow shop were machines have some periods of limited availability. A problem of minimizing makespan in such a flow shop is NP-hard in the strong sense. Moreover, no polynomial time heuristic with finite relative error exists for the problem unless P = NP. One of the standard approaches for solving intractable problems is a branch and bound method. In this paper, a parallel implementation of the branch and bound algorithm solving the problem considered, and the results of computational experiments, are presented. Surprisingly, the tests carried out showed that the best results in case of parallel computations were obtained when a simple depth first search strategy was used.