A rescheduling problem with controllable processing times:trade-off between number of disrupted jobs and reschedulingcosts

Download

index.pdf

Date

2011

Author

Cincioğlu, Derya

Metadata

Show full item record

Item Usage Stats

264
views

145
downloads

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 ine cient and sometimes infeasible. In order to generate a new and feasible schedule, we are dealing with two conflicting measures called the e ciency and stability measures simultaneously. The e ciency 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 e ciency 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 e fficient 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 di culty in finding optimal integer solutions in this problem, but applying strengthened conic reformulation has eliminated this di culty. 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.

Subject Keywords

Production management.

URI

http://etd.lib.metu.edu.tr/upload/12613950/index.pdf
https://hdl.handle.net/11511/20972

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Workload smoothing in assembly lines İmat, Sadullah; Azizoğlu, Meral; Department of Industrial Engineering (2014) In this thesis, we consider a simple assembly line balancing problem with fixed number of workstations and predefined cycle time. Our objective is to minimize the sum of the squared deviations of the workstation loads from the cycle time. We first present pure integer nonlinear programming model and then convert the model into mixed integer linear program. We develop several optimality properties and bounding mechanisms, and use them in our branch and bound algorithm. The results of our computational study ...
Evolutionary algorithms for deterministic and stochastic unconstrained function optimization Koçkesen, Talip Kerem; Özdemirel, Nur Evin; Department of Industrial Engineering (2004) Most classical unconstrained optimization methods require derivative information. Different methods have been proposed for problems where derivative information cannot be used. One class of these methods is heuristics including Evolutionary Algorithms (EAs). In this study, we propose EAs for unconstrained optimization under both deterministic and stochastic environments. We design a crossover operator that tries to lead the algorithm towards the global optimum even when the starting solutions are far from t...
A heuristic approach for the single machine scheduling tardiness problems Özbakır, Saffet İlker; Kırca, Ömer; Department of Industrial Engineering (2011) In this thesis, we study the single machine scheduling problem. Our general aim is to schedule a set of jobs to the machine with a goal to minimize tardiness value. The problem is studied for two objectives: minimizing total tardiness value and minimizing total weighted tardiness value. Solving optimally this problem is difficult, because both of the total tardiness problem and total weighted tardiness problem are NP-hard problems. Therefore, we construct a heuristic procedure for this problem. Our heuristi...
Batch scheduling duling of incompatible jobs on a single reactor with dynamic arrivals Korkmaz, Gediz; Kayalıgil, Sinan; Department of Industrial Engineering (2004) In this study, a single machine batch-scheduling problem with incompatible jobs and dynamic arrivals is examined. The objective function is the minimization of the total flow time of the jobs. For solving problems a case specific branch and bound algorithm with a heuristic upper bound scheme and two alternative lower bound procedures is used. An extensive computational experiment is conducted to investigate the effects of certain parameters on the computation time. For the most difficult parameter combinati...
Analyzing cost structure in logistics sector : a sytem dynamics approach Kuzucu, Ayşegül; Sayın, Erol; Department of Industrial Engineering (2005) In today's conditions, systems that surround individuals have evolved in structure such that, nature of variable interactions are much more complex and changing continuously. Logistics systems, which constitute an example for such systems, have also necessitated fast management and decision-making in a fast paced environment, under limited sources with the additional effect of increasing customer requirements and competition. In this study, system dynamics approach was shown to be a competent alternative to...

Citation Formats

D. Cincioğlu, “A rescheduling problem with controllable processing times:trade-off between number of disrupted jobs and reschedulingcosts,” M.S. - Master of Science, Middle East Technical University, 2011.