Wyniki wyszukiwania - BazTech

1

Assignment of tasks to machines under data replication with a tie to Steiner systems

Wojciechowski Paweł, Kasprzak Marta

International Journal of Applied Mathematics and Computer Science

|

2024

|

Vol. 34, no. 2

263--275

EN

In the paper a problem of assignment of tasks to machines is formulated and solved, where a criterion of data replication is used and a large size of data imposes additional constraints. This problem is met in practice when dealing with large genomic files or other types of vast data. The necessity of comparing all pairs of files within a big set of DNA sequencing results, which we collected, maintained, and analyzed within a national genomic project, brought us to the proposed results. This problem resembles that of generating a particular Steiner system, and a mechanism observed there is employed in one of our algorithms. Based on the problem complexity, we propose two heuristic algorithms, which work very well even for instances with tight constraints and a heterogeneous environment defined. In addition, we propose a simplified method, nevertheless capable of finding very good solutions and surpassing the algorithms in some special cases. The methods are validated in tests on a wide set of instances, where values of parameters reflect our real-world application and where their usefulness is proven.

2

The SEKO assignment : efficient and fair assignment of students to multiple seminars

Hoßfeld Tobias

Operations Research and Decisions

|

2023

|

Vol. 33, No. 3

1--25

EN

Seminars are offered to students for education in various disciplines. The seminars may be limited in terms of the maximum number of participants, e.g., to have lively interactions. Due to capacity limitations, those seminars are often offered several times to serve the students’ demands. Still, some seminars are more popular than others and it may not be possible to grant access to all interested students due to capacity limitations. In this paper, a simple, but efficient random selection using key objectives (SEKO) assignment strategy is proposed which achieves the following goals: (i) efficiency by utilizing all available seminar places, (ii) satisfying all students by trying to assign at least one seminar to each student, and (iii) fairness by considering the number of assigned seminars per student. We formulate various theoretical optimization models using integer linear programming (ILP) and compare their solutions to the SEKO assignment based on a real-world data set. The real-world data set is also used as the basis for generating large data sets to investigate the scalability in terms of demand and number of seminars. Furthermore, the first-in first-out (FIFO) assignment, as a typical implementation of fair assignments in practice, is compared to SEKO in terms of utilization and fairness. The results show that the FIFO assignment suffers in realworld situations regarding fairness, while the SEKO assignment is close to the optimum and scales regarding computational time in contrast to the ILP.

3

Post-optimal analysis for multicriteria integer linear programming problem with parametric optimality

Emelichev Vladimir, Nikulin Yury

Control and Cybernetics

|

2020

|

Vol. 49, No. 2

163--178

EN

This paper addresses a multicriteria problem of integer linear programming with parametric optimality. Parameterizations is introduced by dividing a set of objectives into a family of disjoint subsets, within each Pareto optimality is used to establish dominance between alternatives. The introduction of this principle allows us to connect such classical optimality sets as Pareto and extreme. The parameter space of admissible perturbations in such problem is formed by a set of additive matrices, with arbitrary Hölder’s norms specified in the solution and criterion spaces. The attainable lower and upper bounds for the radii of quasistability are obtained.

4

Heuristic energy-saving virtual network embedding algorithm based on Katz centrality

Zhu Qiang, Wang Qing-Jun, Zang Mu-Jun, Wang Zhen-Dong, Xiao Chang

Archives of Electrical Engineering

|

2020

|

Vol. 69, nr 3

595--608

EN

Current networks are designed for peak loads leading to low utilization of power resources. In order to solve this problem, a heuristic energy-saving virtual network embedding algorithm based on the Katz centrality (Katz-VNE) is proposed. For solving an energy-saving virtual network embedding problem, we introduce the Katz centrality to represent the node influence. In order to minimize the energy consumption of the substrate network, the energy-saving virtual network embedding problem is formulated as an integer linear program, and the Katz-VNE is used to solve this problem. The Katz-VNE tries to embed the virtual nodes onto the substrate nodes with high Katz centrality, which is effective, and uses the shortest paths offering the best factor of bandwidths to avoid the hot nodes. The simulation results demonstrate that the long-term average energy consumption of the substrate network is reduced significantly, and the long-term revenue/cost ratio, the acceptance rate of virtual network requests, and the hibernation rate of substrate nodes as well as links are improved significantly.

5

An optimization approach to the intermodal transportation network in fruit cold chain, considering cost, quality degradation and carbon dioxide footprint

Ma Q., Wang W., Peng Y., Song X.

Polish Maritime Research

|

2018

|

nr 1

61--69

EN

This model optimizes port hinterland intermodal refrigerated container flows , considering both cost and quality degradation, which is distinctive from the previous literature content in a way that it quantifies the influence of carbon dioxide (CO2) emission in different setting temperature on intermodal network planning. The primary contribution of this paper is that the model is beneficial not only to shippers and customers for the novel service design, but also offer , for policy-makers of the government, insights to develop inland transport infrastructures in consideration of intermodal transportation. The majority of models of multimodal system have been established with an objective of cost minimization for normal commodities. As the food quality is possible to be influenced by varying duration time required for the storage and transportation, and transportation accompanied with refrigeration producing more CO2 emission, this paper aims to address cost minimization and quality degradation minimization within the constraint of CO2 footprint. To achieve this aim, we put the quality degradation model in a mixed-integer linear programming model used for intermodal network planning for cold chain. The example of Dalian Port and Yingkou Port offer insight into trade-offs between transportation temperature and transport mode considering CO2 footprint. Furthermore, the model can offer a useful reference for other regions with the demand for different imported food, which requires an uninterrupted cold chain during the transportation and storage.

6

Post-optimal analysis for multicriteria integer linear programming problem of ﬁnding extreme solutions

Emelichev V. A., Nikulin Y.

Control and Cybernetics

|

2018

|

Vol. 47, no. 3

225--238

EN

We consider a multicriteria problem of integer linear programming and study the set of all individual criterion minimizers (extreme solutions) playing an important role in determining the range of Pareto optimal set. In this work, the lower and upper attainable bounds on the stability radius of the set of extreme solutions are obtained in the situation where solution and criterion spaces are endowed with various H¨older’s norms. In addition, the case of the Boolean problem is analyzed. Some computational challenges are also discussed.

7

Optymalizacja wielokryterialna w procesie produkcji mebli

Kłosowski G., Kozłowski E.

Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska

|

2017

|

T. 7, nr 4

101--106

PL

Opracowanie dotyczy zastosowania programowania liniowego całkowitoliczbowego w optymalizacji wielokryterialnej. Celem badań było opracowanie modelu sterownika decyzyjnego umożliwiającego jednoczesną minimalizację poziomu zapasów półfabrykatów wygenerowanych w procesie cięcia, jak i odpadów po rozkroju. Zadaniem sterownika było dobranie odpowiedniego programu rozkroju z uwzględnieniem zamówień produkcyjnych, bieżących zapasów półfabrykatów i ograniczeń odnośnie dopuszczalnych poziomów zapasów.

EN

This paper concerns the use of integer linear programming in a multi-criteria optimization. The aim of the research was to develop a model of the decision support system allowing simultaneous minimization of the intermediate products stocks level and waste generated in the process of cutting. The goal of controller was to select the appropriate cutting program, including production orders, the current inventory and limits on permissible stocks levels.

8

Exact and heuristic approaches to solve the Internet shopping optimization problem with delivery costs

Lopez-Loces M. C., Musial J., Pecero J. E., Fraire-Huacuja H. J., Blazewicz J., Bouvry P.

International Journal of Applied Mathematics and Computer Science

|

2016

|

Vol. 26, no. 2

391--406

EN

Internet shopping has been one of the most common online activities, carried out by millions of users every day. As the number of available offers grows, the difficulty in getting the best one among all the shops increases as well. In this paper we propose an integer linear programming (ILP) model and two heuristic solutions, the MinMin algorithm and the cellular processing algorithm, to tackle the Internet shopping optimization problem with delivery costs. The obtained results improve those achieved by the state-of-the-art heuristics, and for small real case scenarios ILP delivers exact solutions in a reasonable amount of time.