Bounded variable and combinatorial optimization problems some aspects

Abstract

The present thesis analyzes some important aspects of bounded variable problems and combinatorial optimization problems, specially the assignment and the transportation problem. newlineThree important programming problems, namely, linear fractional programming problem with bounded variables, quadratic fractional integer programming problem with bounded variables and linear programming problem with bounded variables have been studied. newlineA two stage time minimization assignment problem has been considered. For finding its optimal solution, a polynomial time iterative algorithm has been developed and coded in MATLAB. An algorithm for complete ranking and scanning of all feasible assignments of this problem has been proposed. Further, an algorithm for solving a bi-objective two stage assignment problem, in which one objective is the conventional total completion time and the other objective is a non-linear cost function, has been developed. The thesis also contains a study on unbalanced variant of time minimization assignment problem consisting of a lesser number of persons than jobs. An unbalanced constrained time minimization assignment problem has been introduced and a lexicographic search technique has been developed for its solution. Using this, an iterative algorithm for solving an unbalanced two stage time minimization assignment problem has been proposed. A three stage time minimization assignment problem has been studied and an iterative algorithm based on generating special type of triplets has been developed and coded. An iterative algorithm for solving a three phase time minimization transportation problem, in which the set of all origin-terminal links is partitioned into three phases, has been developed. newline