A stochastic programming approach to the single machine makespan problem with random breakdowns

Download

10512931 - Tarık Gürel.pdf

Date

2022-12

Author

Gürel, Tarık

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

177
views

82
downloads

In this thesis, we consider a single machine scheduling problem with random breakdowns. There is a single breakdown whose occurrence times follow a discrete distribution with known probabilities. We aim to minimize the expected makespan and propose a stochastic programming approach. We propose two stage stochastic programming models and a branch and bound algorithm. We enhance the performance of the branch and bound algorithm with an efficient branching scheme and powerful lower bounds. The results of our computational experiments have shown that the stochastic programming models can solve small-sized instances and the branch and bound algorithm is capable of solving medium sized instances in reasonable times.

Subject Keywords

Single Machine Sequencing, Makespan, Stochastic Programming Models, Branch and Bound Algorithm, Random Breakdown

URI

https://hdl.handle.net/11511/101263

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A simulated annealing approach to bicriteria scheduling problems on a single machine Karasakal, Esra (2000-08-01) In this paper, we apply a simulated annealing approach to two bicriteria scheduling problems on a single machine. The first problem is the strongly NP-hard problem of minimizing total flowtime and maximum earliness. The second one is the NP-hard problem of minimizing total flowtime and number of tardy jobs. We experiment on different neighbourhood structures as well as other parameters of the simulated annealing approach to improve its performance. Our computational experiments show that the developed appro...
A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem Tozkapan, A; Kirca, O; Chung, CS (2003-02-01) In this paper, a two-stage assembly scheduling problem is considered with the objective of minimizing the total weighted flowtime. A lower bounding procedure and a dominance criterion are developed and incorporated into a branch and bound procedure. A heuristic procedure is also used to derive an initial upper bound. Computational results of the algorithm are presented.
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...
On the minimization of total weighted flow time with identical and uniform parallel machines Azizoğlu, Meral (1999-02-16) We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total weighted flow time. We discuss the properties that characterize the structure of an optimal solution, present a lower bound and propose a branch and bound algorithm. The algorithm is superior to prior methods presented in the literature. We also extend the algorithm to uniform parallel machines and solve medium-sized problem instances.
A two-level variational multiscale method for convection-dominated convection-diffusion equations Volker, John; Kaya Merdan, Songül; Layton, William (2006-01-01) This paper studies the error in, the efficient implementation of and time stepping methods for a variational multiscale method (VMS) for solving convection-dominated problems. The VMS studied uses a fine mesh C-O finite element space X-h to approximate the concentration and a coarse mesh discontinuous vector finite element space L-H for the large scales of the flux in the two scale discretization. Our tests show that these choices lead to an efficient VMS whose complexity is further reduced if a (locally) L...

Citation Formats

T. Gürel, “A stochastic programming approach to the single machine makespan problem with random breakdowns,” M.S. - Master of Science, Middle East Technical University, 2022.