טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentRaviv Tal
SubjectFluid Approximation and other Methods for Hard Combinatorial
Optimization Problems
DepartmentDepartment of Industrial Engineering and Management
Supervisors Professor Michal Penn
Professor Shmuel Onn


Abstract

In the first two chapters of the dissertation we study unreliable serial production lines with known failure probabilities for each operation. Each such production line consists of a series of stations; existing machines and optional quality control stations (QCS). Our aim is to decide where and if to install the QCSs on the line, so as to maximize the expected net profit per time unit from the system. In the first chapter we present an approximation scheme while holding costs are not taken into account. In the second chapter we introduce holding costs and present a branch and bound solution strategy.


In the third chapter we use the fluid approximation to maximize the long run average profit per time unit obtained from a given job shop system. A fluid counterpart model is presented and solved as a simple linear program model. A dispatching rule based on the fluid solution is presented and proved to be optimal once sufficient safety stocks are provided.  Methods to calculate and reduce the minimum required safety stocks are then presented.


In the fourth chapter we deal with the following problem: Given a pair of disjoint subsets S and T of some universe U (which is typically a finite set of point in some Euclidean space), construct a collection of rules that for any given point p in U determines whether or not p is close to S and far from T in some suitable (typically geometric) sense. Applications of this problem arise in the design of decision support systems for medical diagnostic, risk assessment of credit and for repeated solution of hard combinatorial optimization problems after preprocessing.


approach to solve the problem of constructing optimal product mix and cyclic dispatching rule simultaneously in order