Show simple item record

dc.contributor Ph.D. Program in Industrial Engineering.
dc.contributor.advisor Altınel, İ. Kuban.
dc.contributor.advisor Aras, Necati.
dc.contributor.author Şuvak, Zeynep.
dc.date.accessioned 2023-03-16T10:35:25Z
dc.date.available 2023-03-16T10:35:25Z
dc.date.issued 2019.
dc.identifier.other IE 2019 S88 PhD
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/13576
dc.description.abstract It is a commonly used approach to model real life problems as network flow prob lems and they appear in a wide range of areas including telecommunication, wireless networks, transportation, healthcare and scheduling. Our focus in this thesis is on an extension of network flow problems with conflict constraints that prevent the simul taneous usage of some arc pairs to send flow. We particularly concentrate on four of them: the minimum cost noncrossing flow problem on layered networks, the minimum cost flow problem with conflicts, the maximum flow problem with conflicts and the assignment problem with conflicts. The minimum cost noncrossing flow problem on layered networks, which emerges from the quay crane scheduling problem in container terminals, is proven to be NP-hard. Further complexity results including the strong NP-hardness and the non-existence of polynomial time approximation algorithm for the the minimum cost flow problem with conflicts on general networks are also pro vided. Moreover, polynomially solvable special cases for the minimum cost noncrossing flow problem on layered networks and the assignment problem with conflicts, which is known to be NP-hard, are explored. Similarly, the conditions which limit the number of feasible solutions with a polynomial number are indicated for the minimum cost flow problem with conflicts and the maximum flow problem with conflicts taking ad vantage of the conflict graph representation. Alternative mathematical representations for these problems are developed. Pre-optimization procedures to reduce the problem size and to find an initial feasible solution are defined. Exact solution algorithms in cluding a branch-and-bound algorithm enriched with the subroutines that exploit the special structure of the considered problem, an improved Russian doll search algorithm and a Benders decomposition with strengthened cuts are proposed. The methods are tested on a large set of test instances and they are shown to be superior than solving the underlying mathematical formulations with a commercial optimization solver.
dc.format.extent 30 cm.
dc.publisher Thesis (Ph.D.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2019.
dc.subject.lcsh Network analysis (Planning)
dc.subject.lcsh Mathematical optimization.
dc.title Network flows with conflict constraints
dc.format.pages xix, 189 leaves ;


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search Digital Archive


Browse

My Account