Ph.D Student | Raviv Tal |
---|---|

Subject | Fluid Approximation and other Methods for Hard Combinatorial Optimization Problems |

Department | Department of Industrial Engineering and Management |

Supervisors | Professor Michal Penn |

Professor Shmuel Onn |

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