Doctoral Dissertations
Recent Submissions
-
Anokić, Ana (Beograd , 2017)[more][less]
Abstract: Optimization problems arise from many real-life situations. The development of adequate mathematical models of optimization problems and appropriate solution methods are of great importance for performance of real systems. The subject of this doctoral dissertation is a novel vehicle scheduling problem (VSP) that arises from optimizing the transport of agricultural raw materials. The organization of transport of raw materials is of great importance in the initial phase of production. This is particularly evident in the case of agricultural raw materials, because their price in the market is very low, and therefore, the costs of their transport represent the largest part of the total production cost. For this reason, any reduction of time and money spent in this early production stage directly increases the company’s profitability. The considered variant of VSP arises from optimizing the transport of sugar beet in a factory for sugar production in Serbia, but it can also be applied in a wider context, i.e., to optimize the transport of raw materials or goods in large companies under the same or similar conditions. The considered problem involves a number of specific constraints that distinguish it from existing variants of the vehicle scheduling problem. Therefore, mathematical models proposed in the literature for other variants of VSP do not describe adequately the considered problem. The complexity of the newly introduced VSP is analyzed. It is proven that the introduced VSP belongs to the class of NP-hard problems by comparing its relaxation with the Parallel Machine Scheduling Problem (PMSP). PMSP is known to be NP-hard, as it is equivalent to the Partitioning problem. From the established analogy between the relaxation of the considered VSP and PMSP, it is concluded that the VSP introduced in this dissertation is NP-hard. New mathematical models of the considered problem that involve all problem specific properties, are developed. The proposed mathematical models are compared in sense of efficiency by using Lingo 17 and CPLEX MIP 12.6.2 solvers. Experimental results showed that both exact solvers provided optimal or feasible solutions only for small-size real-life problem instances. However, this was expectable, having in mind the NP-hardness of the considered problem. Therefore, heuristic and metaheuristic method seem to be appropriate approaches for solving problem instances of larger dimension. Due to specific properties of the considered problem, the existing implementations of heuristic and metaheuristic methods for vehicle routing and scheduling problems can not be directly applied. For this reason, different variants of well-known Variable Neighborhood Search (VNS) metaheuristic, as well as Greedy Randomized Adaptive Search Procedure (GRASP), are designed. The constructive elements of the proposed VNS and GRASP implementations are adapted to the characteristics of the considered vehicle scheduling problem. A subproblem of the proposed variant of vehicle scheduling problem, denoted as VSP-P is considered first. VSP-P is obtained from the initial VSP by excluding problem specific constraints regarding vehicle arriving times to each location and to the factory area. Two metaheuristic algorithms are designed as solution methods for this subproblem: Basic Variable Neighborhood Search - BVNS, and Greedy Randomized Adaptive Search Procedure - GRASP. Both proposed approaches were tested on instances based on real-life data and on the set of generated instances of lager dimensions. Experimental results show that BVNS and GRASP reached all optimal solutions obtained by exact solvers on small-size real-life problem instances. On medium-size real-life instances, BVNS reached or improved upper bounds obtained by CPLEX solver under time limit of 5 hours. BVNS showed to be superior compared to GRASP in the sense of solution quality on medium size real-life instances, as well as on generated large-size problem instances. However, general conclusion is that both proposed methods represent adequate solution approaches for the subproblem VSP-P. BVNS provides solutions of better quality compared to GRASP, while GRASP outperforms BVNS regarding the average CPU time required to produce its best solutions. For the initial vehicle scheduling problem (VSP) that includes all problem specific constraints, three VNS-based metaheuristic methods are designed and implemented: Basic Variable Neighborhood Search - BVNS, Skewed Variable Neighborhood Search - SVNS, and Improved Basic Variable Neighborhood Search - BVNSi. BVNS and SVNS use the same neighborhood structures, but different search strategies in local search phase: BVNS uses Best improvement strategy, while SVNS uses First improvement strategy. All three VNS-based methods are tested on real-life and generated problem instances. As it was expected, experimental results showed that BVNS outperformed SVNS regarding solution quality, while SVNS running time was significantly shorter compared to BVNS. The third designed algorithm BVNSi represents a variant of BVNS that uses more general neighborhood structures compared to the ones used in BVNS and SVNS. The use of such neighborhood structures lead to the simplicity of BVNSi and shorter running times compared to BVNS. Two variants of BVNSi method that exploit different strategies in Local search phase are designed: BVNSiB with best improvement strategy and BVNSiF with First improvement strategy. The results of computational experiments for all proposed VNS-based methods for VSP are analyzed and compared. Regarding the quality of the obtained solutions, BVNS method shows the best performance, while SVNS needed the shortest average running times to produce its best solutions. Two variants of BVNSi method succeeded to find new best solutions on two medium size real life instances and to solve large size instances in shorter running time compared to BVNS and SVNS, respectively. However, both BVNSiB and BVNSiF turn out to be less stabile than BVNS and SVNS on real-life and generated inatances. In the case of one large-size generated instance, both BVNSi variants had significantly worse performance compared to BVNS and SVNS, which had negative impact on their average objective values and average running times. The proposed vehicle scheduling problem is of great practical importance for optimizing the transport of agricultural raw materials. It is planned to use the obtained results in practice (partially or completely), as a support to decision makers who organize transportation of in the early production phase. From the theoretical point of view, the developed mathematical models represent a scientific contribution to the fields of optimization and mathematical modeling. The variants of VNS methods that are developed and adapted to the problem, as well as comparison of their performances, represent a scientific contribution to the field of metaheuristic methods for solving NP-hard optimization problems. URI: http://hdl.handle.net/123456789/4664 Files in this item: 1
Anokic_Ana_disertacija.pdf ( 2.688Mb ) -
Vučković, Bojan (Beograd , 2017)[more][less]
Abstract: We present original results from the following fields of discrete mathematics: chromatic graph theory, extremal set theory and Boolean matrix theory. From the chromatic graph theory we investigate edge and total colorings satisfying the condition that neighboring vertices of a graph possess different values of multi-set, set or sum, induced by the giving coloring. Multi-set neighbor-distinguishing edge coloring of a graph is an assignment of colors to edges such that, for every edge uv of a graph, multi-set of the edges incident with the vertex u differs from the multi-set of the edges incident with the vertex v. The previous best result concerning the minimum number of colors required for such a coloring of an arbitrary graph states that four colors are sufficient. The author’s contribution is a proof that such a coloring is always possible with only three colors, which is in general case the optimal number of colors. We construct a graph for which we subsequently prove that a different number of colors is required to obtain a multi-set neighbor-distinguishing coloring and neighbor-distinguishing coloring by sum. As far as we know, this is the first example of such a graph. A few results concerning the neighbor expended sum distinguishing coloring are given. The main contribution is a proof that for an arbitrary graph there exists a total coloring from the set f1; 2; 3g, such that every two adjacent vertices have different sums of its adjacent vertices and incident edges. Also, for certain classes of graphs is proved that there exists such a coloring using only the colors from the set f1; 2g. Neighbor-distinguishing edge coloring of a graph G requires that every two adjacent edges receive different colors, while the sets of the edges incident with the vertices u and v differ for every edge uv of G. The author presents a procedure of edge coloring for an arbitrary graph without isolated edges, where we a smaller number of colors is used compared to all known results. For the adjacent vertex distinguishing total coloring of a graph G the condition is that every two adjacent and incident elements of V (G) [ E(G) receive different colors, while for every edge uv of G the set composed from the colors assigned to the edges incident with u together with the color of u, differs from such a set for v. The author improves the upper bound of the minimum number of colors needed for such a coloring, relative to the maximal degree of a graph. Frankl’s conjecture from the extremal set theory states that for every family closed under union there exists an element contained in at least half of the sets of the family. We give a proof that Frankl’s conjecture holds for every family contained from 12 elements, while it is known that this is true for families contained from 11 or less elements. Our proof is based on the efficient algorithm that exhausts all the possibilities, while using the results for subfamilies that eventual counter-example cannot contain, which we obtained in a number of consecutive steps. Family of sets G is an FC-family if for every family F containing G there exists an element from S G that appears in at least half of the sets of F. NonFC-family is every family that is not FC. The author’s contribution is the complete classification of all families consisting of 6 or less elements into FC and NonFC-families. From the Boolean matrices theory we present our results concerning the row space cardinality. Boolean matrices are the matrices whose all components are from the set f0; 1g, while the row space of a Boolean matrix is the set of vectors that can be obtained by disjunction from the rows of a matrix. We present the set consisted of all values a from the interval [2n2 + 2n3; 2n2] such that there exists a matrix of dimension n n having the row space cardinality equal to a. For the least positive integer an for which there exists no matrix of dimension n n having the row space cardinality equal to an, the author gives a lower bound that is an improvement over the previously known results. All proofs for the main results in the dissertation are constructive. Proofs of some of them require the use of computers where there is a calculation of a great number of possibilities. For other proofs this was not necessity, though algorithms following the steps of the proofs can be implemented to obtain a graph coloring or a matrix with the desired properties. URI: http://hdl.handle.net/123456789/4661 Files in this item: 1
Disertacija_-_Bojan_Vuckovic.pdf ( 1.143Mb ) -
Milošević, Stefan (Beograd , 2017)[more][less]
Abstract: In this paper we present some norm inequalities for certain elementary operators and inner product type transformers, specially for Schatten norms, if the families of operators generating those transforms consists of arbitrary operators, and Q norms if at least one of those families consists of mutually commuting normal operators. Among others, we present inequalities that are generalizing the inequality p IA AX p IB B 6 X AXB ; from [11, Th. 2.3], for normal contractions and arbitrary unitarily invariant norm, to the case of Schatten norms and arbitrary contractions, as well as Q norms if at least one of the contractions A or B is normal. Also, by applying norm inequalities for operator monotone and operator convex functions, some refined Cauchy - Schwarz operator inequalities, as well as Minkowski and Landau - Gruss norm inequalities for operators are obtained as well. URI: http://hdl.handle.net/123456789/4656 Files in this item: 1
Stefan_Milosevic_Disertacija.pdf ( 2.544Mb ) -
Mikić, Marija (Beograd , 2017)[more][less]
Abstract: The subject of this dissertation is the investigation of asymptotic properties of solutions for di erential equations of Emden-Fowler type and their generalizations. The eld to which this dissertation belongs is a Qualitative theory of ordinary di e- rential equations. Emden-Fowler di erential equation has the form (t u0(t))0 t u (t) = 0 ; where ; ; 2 R. With some changes of the variables, this di erential equation can be reduced to the equations y00 xay = 0 and y00 + xay = 0. Firstly, in this dissertation, the di erential equation y00 = xay ; where a; 2 R was observed. The conditions, which provide that this equation has in nitely many solutions de ned in some neighborhood of zero, were described here, both with the conditions, which guarantee the existence of in nitely many solutions with certain asymptotic behavior. Also, a complete picture of asymptotic behavior of solutions of equation along the positive parts of both axes is given. The conditions, which assure existence and unique solvability of solution of the Cauchy problem for this equation, were shown in the cases when the familiar theory can't be applied. In some cases, asymptotic formulas for solutions were obtained. The di erential equation y00 = xay ; where a 2 R i < 0 ; has also been taken into consideration. The conditions, which assure the existence of in nitely many solutions of observed equation tending to zero as x ! 0+, were obtained. The conditions, which assure the unique solvability of the Cauchy problem for generalized Emden-Fowler equation y00 = q(x)f(y(x)); lim x!0+ y(x) = 0; lim x!0+ y0(x) = ; were described, for any > 0 and functions f and q which satisfy certain conditions. The given results generalize the results both for sublinear Emden-Fowler di erential equation (i.e. case when 0 < < 1) and the case when < 0. In literature, it is very rare to nd the conditions for di erent values of the para- metar which appears in the equations of Emden-Fowler type. In this dissertation, the results for sublinear and superlinear di erential equation Emden-Fowler, as well as the case when < 0, are presented. Therefore, the story of the asymptotic be- havior of solutions of the observed equation is "almost complited". URI: http://hdl.handle.net/123456789/4655 Files in this item: 1
Marija_Mikic_disertacija_MTF.pdf ( 1.461Mb ) -
Milić Žitnik, Ivana (Beograd , 2017)[more][less]
Abstract: The subje t of this dissertation is intera tion between the mean motion resonan- es and the Yarkovsky e e t. This intera tion o urs when an asteroid due to the hanges of its orbital semi-major axis ( aused by the Yarkovsky e e t) rea h the re- sonan e. The resonan e indu es a periodi os illations in the asteroid's semi-major axis around its enter. The Yarkovsky e e t exa tly auses the permanent (se ular) evolution of the orbital semi-major axis. As a result of their intera tion the mean semi-major axis drift speed is modi ed with respe t to the one aused solely by Yarkovsky. One of the main goals of this investigation was to study this intera tion, and to establish and de ne how the time that an asteroid spend in the resonan e depends on some hara teristi s of this resonan e, as well as of the asteroid itself. So far, the impa t of the resonan e on the semi-major axis drift speed has not been studied to that extent neither from that point of view. In order to study the afo- rementioned intera tion the orbital motion of test parti les a ross the resonan es is numeri ally simulated using ORBIT9 integrator. The most important result of this dissertation ertainly is determination of fun tional relation between on one side the time-period that obje ts spend inside a resonan e, and, on the other side, the semi- majors axis drift speed, the orbital e entri ity and the resonan e strength. In this work not only that existen e of the above-mentioned relationship is on rmed, but for the rst time it was expli itly de ned. Two the most interesting results are that the time spent in the resonan e is inversely proportional to the semi-major axis drift speed aused by the Yarkovsky e e t, and that this time is dire tly proportional to the resonan e strength. URI: http://hdl.handle.net/123456789/4651 Files in this item: 1
Milic-Zitnik_Ivana.pdf ( 40.69Mb )