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

The solution of MRSLP with the use of heuristic algorithms

Kochańska Joanna, Burduk Anna, Łapczyńska Dagmara, Musiał Kamil

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2024

|

Vol. 72, nr 1

art. no. e146407

EN

Improving production processes includes not only activities concerning manufacturing itself, but also all the activities that are necessary to achieve the main objectives. One such activity is transport, which, although a source of waste in terms of adding value to the product, is essential to the realization of the production process. Over the years, many methods have been developed to help manage supply and transport in such a way as to reduce it to the necessary minimum. In the paper, the problem of delivering components to a production area using trains and appropriately laid-out carriages was described. It is a milk run stop locations problem (MRSLP), whose proposed solution is based on the use of heuristic algorithms. Intelligent solutions are getting more and more popular in the industry because of the possible advantages they offer, especially those that include the possibility of finding an optimum local solution in a relatively short time and the prevention of human errors. In this paper, the applicability of three algorithms – tabu search, genetic algorithm, and simulated annealing – was explored.

3

Solving scheduling problems with integrated online sustainability observation using heuristic optimization

Burduk Anna, Musiał Kamil, Balashov Artem, Batako Andre, Safonyk Andrii

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2022

|

Vol. 70, nr 6

art. no. e143830

EN

The paper deals with the issue of production scheduling for various types of employees in a large manufacturing company where the decision-making process was based on a human factor and the foreman’s know-how, which was error-prone. Modern production processes are getting more and more complex. A company that wants to be competitive on the market must consider many factors. Relying only on human factors is not efficient at all. The presented work has the objective of developing a new employee scheduling system that might be considered a particular case of the job shop problem from the set of the employee scheduling problems. The Neuro-Tabu Search algorithm and the data gathered by manufacturing sensors and process controls are used to remotely inspect machine condition and sustainability as well as for preventive maintenance. They were used to build production schedules. The construction of the Neuro-Tabu Search algorithm combines the Tabu Search algorithm, one of the most effective methods of constructing heuristic algorithms for scheduling problems, and a self-organizing neural network that further improves the prohibition mechanism of the Tabu Search algorithm. Additionally, in the paper, sustainability with the use of Industry 4.0 is considered. That would make it possible to minimize the costs of employees’ work and the cost of the overall production process. Solving the optimization problem offered by Neuro-Tabu Search algorithm and real-time data shows a new way of production management.

4

Research on optimization of unrelated parallel machine scheduling based on IG-TS algorithm

Chi Xinfu, Liu Shijing, Li Ce

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2022

|

Vol. 70, nr 4

art. no. e141724

EN

This issue is a typical NP-hard problem for an unrelated parallel machine scheduling problem with makespan minimization as the goal and no sequence-related preparation time. Based on the idea of tabu search (TS), this paper improves the iterative greedy algorithm (IG) and proposes an IG-TS algorithm with deconstruction, reconstruction, and neighborhood search operations as the main optimization process. This algorithm has the characteristics of the strong capability of global search and fast speed of convergence. The warp knitting workshop scheduling problem in the textile industry, which has the complex characteristics of a large scale, nonlinearity, uncertainty, and strong coupling, is a typical unrelated parallel machine scheduling problem. The IG-TS algorithm is applied to solve it, and three commonly used scheduling algorithms are set as a comparison, namely the GA-TS algorithm, ABC-TS algorithm, and PSO-TS algorithm. The outcome shows that the scheduling results of the IG-TS algorithm have the shortest manufacturing time and good robustness. In addition, the production comparison between the IG-TS algorithm scheduling scheme and the artificial experience scheduling scheme for the small-scale example problem shows that the IG-TS algorithm scheduling is slightly superior to the artificial experience scheduling in both planning and actual production. Experiments show that the IG-TS algorithm is feasible in warp knitting workshop scheduling problems, effectively realizing the reduction of energy and the increase in efficiency of a digital workshop in the textile industry.

5

Comparison of the Classical Algorithm with the Training Algorithm in Scheduling Problem ADI Production

Wilk-Kołodziejczyk D., Chrzan K., Jaśkowiec K., Pirowski Z., Żuczek R., Bitka A., Machulec D.

Archives of Foundry Engineering

|

2022

|

Vol. 22, iss. 1

5--12

EN

A classical algorithm Tabu Search was compared with Q Learning (named learning) with regards to the scheduling problems in the Austempered Ductile Iron (ADI) manufacturing process. The first part comprised of a review of the literature concerning scheduling problems, machine learning and the ADI manufacturing process. Based on this, a simplified scheme of ADI production line was created, which a scheduling problem was described for. Moreover, a classic and training algorithm that is best suited to solve this scheduling problem was selected. In the second part, was made an implementation of chosen algorithms in Python programming language and the results were discussed. The most optimal algorithm to solve this problem was identified. In the end, all tests and their results for this project were presented.

6

Optimal vehicle route schedules in picking up and delivering cargo containers considering time windows in logistics distribution networks: A case study

Le Thi Diem Chau, Nguyen Duy Duc, Oláh Judit, Pakurár Miklós

Production Engineering Archives

|

2020

|

Vol. 26, Iss. 4

174--184

EN

This study describes a pickup and delivery vehicle routing problem, considering time windows in reality. The problem of tractor truck routes is formulated by a mixed integer programming model. Besides this, three algorithms - a guided local search, a tabu search, and simulated annealing - are proposed as solutions. The aims of our study are to optimize the number of internal tractor trucks used, and create optimal routes in order to minimize total logistics costs, including the fixed and variable costs of an internal vehicle group and the renting cost of external vehicles. Besides, our study also evaluates both the quality of solutions and the time to find optimal solutions to select the best suitable algorithm for the real problem mentioned above. A novel mathematical model is formulated by OR tools for Python. Compared to the current solution, our results reduced total costs by 18%, increased the proportion of orders completed by internal vehicles (84%), and the proportion of orders delivered on time (100%). Our study provides a mathematical model with time constraints and large job volumes for a complex distribution network in reality. The proposed mathematical model provides effective solutions for making decisions at logistics companies. Furthermore, our study emphasizes that simulated annealing is a more suitable algorithm than the two others for this vehicle routing problem.

7

Two meta-heuristic algorithms for scheduling on unrelated machines with the late work criterion

Wang Wen, Chen Xin, Musial Jędrzej, Blazewicz Jacek

International Journal of Applied Mathematics and Computer Science

|

2020

|

Vol. 30, no. 3

573--584

EN

A scheduling problem in considered on unrelated machines with the goal of total late work minimization, in which the late work of a job means the late units executed after its due date. Due to the NP-hardness of the problem, we propose two meta-heuristic algorithms to solve it, namely, a tabu search (TS) and a genetic algorithm (GA), both of which are equipped with the techniques of initialization, iteration, as well as termination. The performances of the designed algorithms are verified through computational experiments, where we show that the GA can produce better solutions but with a higher time consumption. Moreover, we also analyze the influence of problem parameters on the performances of these metaheuristics.

8

Tabu Search Against Permutation Based Stream Ciphers

Polak I., Boryczka M.

International Journal of Electronics and Telecommunications

|

2018

|

Vol. 64, No. 2

137--145

EN

Encryption is one of the most effective methods of securing data confidentiality, whether stored on hard drives or transferred (e.g. by e-mail or phone call). In this paper a new state recovery attack with tabu search is introduced. Based on research and theoretical approximation it is shown that the internal state can be recovered after checking 2⁵² internal states for RC4 and 2¹⁸⁰ for VMPC.

9

Tabu search for the RNA partial degradation problem

Rybarczyk A., Hertz A., Kasprzak M., Blazewicz J.

International Journal of Applied Mathematics and Computer Science

|

2017

|

Vol. 27, no. 2

401--415

EN

In recent years, a growing interest has been observed in research on RNA (ribonucleic acid), primarily due to the discovery of the role of RNA molecules in biological systems. They not only serve as templates in protein synthesis or as adapters in the translation process, but also influence and are involved in the regulation of gene expression. The RNA degradation process is now heavily studied as a potential source of such riboregulators. In this paper, we consider the so-called RNA partial degradation problem (RNA PDP). By solving this combinatorial problem, one can reconstruct a given RNA molecule, having as input the results of the biochemical analysis of its degradation, which possibly contain errors (false negatives or false positives). From the computational point of view the RNA PDP is strongly NP-hard. Hence, there is a need for developing algorithms that construct good suboptimal solutions. We propose a heuristic approach, in which two tabu search algorithms cooperate, in order to reconstruct an RNA molecule. Computational tests clearly demonstrate that the proposed approach fits well the biological problem and allows to achieve near-optimal results. The algorithm is freely available at http://www.cs.put.poznan.pl/arybarczyk/tabusearch.php.

10

Heuristic algorithms for joint optimization of unicast and anycast traffic in elastic optical network-based large-scale computing systems

Markowski M.

International Journal of Applied Mathematics and Computer Science

|

2017

|

Vol. 27, no. 3

605--622

EN

In recent years elastic optical networks have been perceived as a prospective choice for future optical networks due to better adjustment and utilization of optical resources than is the case with traditional wavelength division multiplexing networks. In the paper we investigate the elastic architecture as the communication network for distributed data centers. We address the problems of optimization of routing and spectrum assignment for large-scale computing systems based on an elastic optical architecture; particularly, we concentrate on anycast user to data center traffic optimization. We assume that computational resources of data centers are limited. For this offline problems we formulate the integer linear programming model and propose a few heuristics, including a meta-heuristic algorithm based on a tabu search method. We report computational results, presenting the quality of approximate solutions and efficiency of the proposed heuristics, and we also analyze and compare some data center allocation scenarios.

11

A Meta-Heuristic Algorithm Combining Between Tabu and Variable Neighborhood Search for the Minimum Latency Problem

Ban H. B., Nguyen D. N.

Fundamenta Informaticae

|

2017

|

Vol. 156, nr 1

21--41

EN

Minimum Latency Problem (MLP) is a class of NP-hard combinatorial optimization problems which has many practical applications. In this paper, we investigate the global structure of the MLP solution space to propose a suitable meta-heuristic algorithm for the problem, which combines Tabu search (TS) and Variable Neighborhood Search (VNS). In the proposed algorithm, TS is used to prevent the search from getting trapped into cycles, and guide VNS to escape local optima. In a cooperative way, VNS is employed to generate diverse neighborhoods for TS. We also introduce a novel neighborhoods’ structure for VNS and present a constant time operation for calculating the latency cost of each neighboring solution. Extensive numerical experiments and comparisons with the state of the art meta-heuristic algorithms in the literature show that the proposed algorithm is highly competitive, providing the new best solutions for several instances.

12

Stable scheduling of single machine with probabilistic parameters

Bożejko W., Rajba P., Wodecki M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2017

|

Vol. 65, nr 2

219--231

EN

We consider a stochastic variant of the single machine total weighted tardiness problem jobs parameters are independent random variables with normal or Erlang distributions. Since even deterministic problem is NP-hard, it is difficult to find global optimum for large instances in the reasonable run time. Therefore, we propose tabu search metaheuristics in this work. Computational experiments show that solutions obtained by the stochastic version of metaheuristics are more stable (i.e. resistant to data disturbance) than solutions generated by classic, deterministic version of the algorithm.

13

Porównanie algorytmów genetycznego i przeszukiwania tabu wykorzystanych do szeregowania zadań w budownictwie

Rosłon J.

Materiały Budowlane

|

2016

|

nr 6

44--45

PL

W artykule przedstawiono obecnie stosowane metody szeregowania zadań i harmonogramowania w budownictwie. Zaprezentowano przykładowe zadanie budowlane o charakterze deterministycznym, z którym borykać się może firma wykonawcza, podano jego rozwiązanie za pomocą algorytmu genetycznego i przeszukiwania tabu. Dokonano analizy i porównania uzyskanych wyników.

EN

The paper contains literature study for task sequencing methods and schedule optimization in construction. The author presents sample, determinative construction company problem. The sample problem is solved with the use of genetic algorithm and tabu search. Results are compared and analyzed.

14

Off-line and dynamic production scheduling - a comparative case study

Bożek A., Wysocki M.

Management and Production Engineering Review

|

2016

|

Vol. 7, No. 1

21--32

EN

A comprehensive case study of manufacturing scheduling solutions development is given. It includes highly generalized scheduling problem as well as a few scheduling modes, methods and problem models. The considered problem combines flexible job shop structure, lot streaming with variable sublots, transport times, setup times, and machine calendars. Tabu search metaheuristic and constraint programming methods have been used for the off-line scheduling. Two dynamic scheduling methods have also been implemented, i.e., dispatching rules for the completely reactive scheduling and a multi-agent system for the predictivereactive scheduling. In these implementations three distinct models of the problem have been used, based on: graph representation, optimal constraint satisfaction, and Petri net formalism. Each of these solutions has been verified in computational experiments. The results are compared and some findings about advantages, disadvantages, and suggestions on using the solutions are formulated.

15

Automatic parametric fault detection in complex analog systems based on a method of minimum node selection

Bilski A., Wojciechowski J.

International Journal of Applied Mathematics and Computer Science

|

2016

|

Vol. 26, no. 3

655--668

EN

The aim of this paper is to introduce a strategy to find a minimal set of test nodes for diagnostics of complex analog systems with single parametric faults using the support vector machine (SVM) classifier as a fault locator. The results of diagnostics of a video amplifier and a low-pass filter using tabu search along with genetic algorithms (GAs) as node selectors in conjunction with the SVM fault classifier are presented. General principles of the diagnostic procedure are first introduced, and then the proposed approach is discussed in detail. Diagnostic results confirm the usefulness of the method and its computational requirements. Conclusions on its wider applicability are provided as well.

16

SO(3) matrix transformation for rapid polarization search and coding in a three-plate polarizer

Huang C, Wang X

Optica Applicata

|

2015

|

Vol. 45, nr 1

101--112

EN

A SO(3) transformer of a three-plate polarizer is adopted to rapidly achieve the transformation of the polarized state. The polarization coding based on Stokes components S2 and S3 is analyzed and demonstrated. Tabu search algorithm is used to accelerate the transformation of the polarized state by utilizing Mueller matrix roots decomposition to decompose the SO(3) matrix, and substituting first order Taylor series approximations for the trigonometric functions in the SO(3) matrix. The results show that bias voltage is less than 120 V in the coding zone. The search speed of our algorithm is faster than the one without first order Taylor series approximations by 4 times.

17

Assigning NMR spectra of irregular RNAs by heuristic algorithms

Szachniuk M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2015

|

Vol. 63, nr 1

329--338

EN

Computer-aided analysis and preprocessing of spectral data is a prerequisite for any study of molecular structures by Nuclear Magnetic Resonance (NMR) spectroscopy. The data processing stage usually involves a considerable dedication of time and expert knowledge to cope with peak picking, resonance signal assignment and calculation of structure parameters. A significant part of the latter step is performed in an automated way. However, in peak picking and resonance assignment a multistage manual assistance is still essential. The work presented here is focused on the theoretical modeling and analyzing the assignment problem by applying heuristic approaches to the NMR spectra recorded for RNA structures containing irregular regions.

18

Using tabu search for feature selection in discriminant analysis

Stąpor K.

Studia Informatica

|

2014

|

Vol. 35, nr 4

45--58

EN

The well known statistical software packages like STATISTICA [11] continue to use classic variable selection methods in stepwise Discriminant Analysis such as the sequential forward/backward ones. Such stepwise procedures suffer from the nesting effect. Moreover, due to the criterion used for evaluation of variable subsets they are designed for descriptive purposes, not for predictive ones. We propose the new solution to the mentioned problems, the feature selection algorithm based on metaheuristic tabu search. After performing some tests it is found that our tabu search-based algorithm obtains significantly better results than stepwise procedures of statistical package.

PL

W znanych szeroko pakietach do obliczeń statystycznych (np. STATISTICA [11]) selekcja zmiennych wejściowych w module krokowej Analizy Dyskryminacyjnej wykonywana jest z wykorzystaniem klasycznych metod sekwencyjnych w przód/w tył, których wadą jest efekt zagnieżdżania. Również kryterium ewaluacyjne w tychże metodach jest dostosowane do celów deskryptywnych, a nie predyktywnych. Artykuł proponuje nowe rozwiązania wspomnianych problemów – algorytm selekcji z wykorzystaniem metaheurystyki przeszukiwania z tabu. Wykonane, wstępne testy wykazały znacznie lepszą sprawność klasyfikacji w porównaniu z metodami krokowymi.

19

Cluster Based Optimization of Routing in Distributed Sensor Networks Using Bayesian Networks with Tabu Search

Bhajantri L. B., Nalini N.

International Journal of Electronics and Telecommunications

|

2014

|

Vol. 60, No. 2

199-208

EN

Distributed Sensor Networks (DSNs) have attracted significant attention over the past few years. A growing list of many applications can employ DSNs for increased effectiveness especially in hostile and remote are as. In all application salargen umber of sensors are expected and requiring careful architecture and management of the net work. Grouping nodes in toclusters has been the most popular approach for support scalability in DSN. This paper proposes acluster based optimization of routing in DSN by employing a Bayesi an network (BN) with Tabu search (TS) approach. BN based approach is used to select efficient cluster head sand construction of BN for the proposed scheme. This approach in corporates energy level of each node, band width and link efficiency. The optimization of routing is considered as a design issue in DSN due to lack of energy consumption, delay and maximum time required for data transmission between source nodes (cluster heads) to sink node. In this work optimization of routing takes place through cluster head nodes by using TS. Simulations have been conducted to compare the performance of the proposed approach with LEACH protocol. The objective of the proposed work is to improve the performance of network in terms of energy consumption, through put, packet delivery ratio, and time efficiency of optimization of routing. The results hows that the proposed approach perform better than LEACH protocol that utilizes minimum energy, latency for cluster formation and reduce over head of the protocol.

20

A support vector machine with the tabu search algorithm for freeway incident detection

Yao B., Hu P., Zhang M., Jin M.

International Journal of Applied Mathematics and Computer Science

|

2014

|

Vol. 24, no. 2

397--404

EN

Automated Incident Detection (AID) is an important part of Advanced Traffic Management and Information Systems (ATMISs). An automated incident detection system can effectively provide information on an incident, which can help initiate the required measure to reduce the influence of the incident. To accurately detect incidents in expressways, a Support Vector Machine (SVM) is used in this paper. Since the selection of optimal parameters for the SVM can improve prediction accuracy, the tabu search algorithm is employed to optimize the SVM parameters. The proposed model is evaluated with data for two freeways in China. The results show that the tabu search algorithm can effectively provide better parameter values for the SVM, and SVM models outperform Artificial Neural Networks (ANNs) in freeway incident detection.