Verileri aralık sayılar olan bazı en iyileme problemleri üzerine denemeler

ABSTRACT ESSAYS ON SOME COMBINATORIAL OPTIMIZATION PROBLEMS WITH INTERVAL DATA Hande Yaman M.S. in Industrial Engineering Supervisor: Assoc. Prof. Mustafa Ç. Pınar June, 1999 In this study, we investigate three well-known problems, the longest path problem on directed acyclic graphs, the minimum spanning tree problem and the single machine scheduling problem with total flow time criterion, where the input data for all problems are given as interval numbers. Since optimal solutions depend on the realization of the data, we define new optimality concepts to aid decision making. We present characterizations for these "optimal" solutions and suggest polynomial time algorithms to find them in some special cases. Key words: Longest Path Problem on Directed Acyclic Graphs, Minimum Spanning Tree Problem, Single Machine Scheduling Problem with Total Flow Time Criterion, Interval Data, Polynomial Time Algorithms