In this thesis, we consider a rescheduling problem on non-identical parallel machines with controllable processing times. A period of unavailability occurs on one of the machines due
to a machine failure, material shortage or broken tool. These disruptions may cause the original schedule to become inecient and sometimes infeasible. In order to generate a new and
feasible schedule, we are dealing with two conflicting measures called the eciency and stability measures simultaneously. The eciency measure evaluates the satisfaction of a desired objective function value and the stability measure evaluates the amount of change between
the schedule before and after the disruption. In this study, we measure stability by the number of disrupted jobs. In this thesis, the job is referred as a disrupted job if it completes processing after its planned completion time in the original schedule. The eciency is measured by the additional manufacturing cost of jobs. Decreasing number of disrupted jobs requires compressing the processing time of a job which cause an increase in its additional manufacturing cost. For that reason we cannot minimize these objectives at the same time. In order to handle this, we developed a mixed integer programming model for the considered problem by applying the epsilon-constraint approach. This approach makes focusing on the single objective possible to get efficient solutions. Therefore, we studied the problem of minimizing additional
manufacturing cost subject to a limit on the number of disrupted jobs. We also considered a convex compression cost function for each job and solved a cost minimization problem by applying conic quadratic reformulation for the model. The convexity of cost functions is a major source of diculty in finding optimal integer solutions in this problem, but applying
strengthened conic reformulation has eliminated this diculty. In addition, we prepare an improvement search algorithm in order to find good solution in reasonable CPU times. We use our heuristic procedure on optimality properties we showed for a single machine subproblem. We made computational experiments on small and medium scale test problems. Afterwards, we compare the performance of the improvement search algorithm and mathematical model for their solution quality and durations.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12613950/index.pdf |
| Date | 01 December 2011 |
| Creators | Cincioglu, Derya |
| Contributors | Gurel, Sinan |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | M.S. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for METU campus |
Page generated in 0.0017 seconds