A heuristic approach for the single machine scheduling tardiness problems

Download

index.pdf

Date

2011

Author

Özbakır, Saffet İlker

Metadata

Show full item record

Item Usage Stats

191
views

79
downloads

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 heuristic procedure is divided to two parts: construction part and improvement part. The construction heuristic is based on grouping the jobs, solving these groups and then fixing some particular number of jobs. Moreover, we used three type improvement heuristics. These are sliding forward method, sliding backward method and pairwise interchange method. Computational results are reported for problem size = 20, 40, 50 and 100 at total tardiness problem and for problem size = 20 and 40 at total weighted tardiness problem. Experiments are designed in order to investigate the effect of three factors which are problem size, tardiness factor and relative range of due dates on computational difficulties of the problems. Computational results show that the heuristic proposed in this thesis is robust to changes at these factors.

Subject Keywords

Scheduling., Industrial engineering., Production scheduling.

URI

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

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A heuristic approach for profit oriented disassembly lot-sizing problem Kaya, Melike; Bayındır, Zeynep Pelin; Çetinkaya, Ferda Can; Department of Industrial Engineering (2011) In this thesis, we work on adisassembly lot-sizing problem for multiple products with parts commonality,i.e., general product structure. We assume that supply of discarded products is infinite. When a product (or a subassembly) is disassembled, all its immediate child items are obtained,i.e., complete disassembly case.Intermediate and leaf items obtained are demandedbyexternal suppliers or remanufacturers. The maximum possible salesfor each intermediate and leaf item are known.Sales of the intermediate and ...
Disassembly line balancing problem with fixed number of workstations and finite supply Göksoy, Eda; Azizoğlu, Meral; Department of Industrial Engineering (2010) In this thesis, we consider a Disassembly Line Balancing Problem (DLBP) with fixed number of workstations. We aim to maximize the total value of the recovered parts. We assume that there is a limited supply for the products to be disassembled. Different components can be obtained by disassembling different units of the product. Our aim is to assign the tasks to the workstations of the disassembly line so as to maximize the total value of the recovered parts. We present several upper and one lower bounding p...
A comparison of orthogonal cutting data from experiments with three different finite element models Bil, H; Kilic, SE; Tekkaya, AE (Elsevier BV, 2004-07-01) The aim of this study is to compare various simulation models of orthogonal cutting process with each other as well as with the results of various experiments. Commercial implicit finite element codes MSC.Marc, Deform2D and the explicit code Thirdwave AdvantEdge have been used. In simulations, a rigid tool is advanced incrementally into the deformable workpiece which is remeshed whenever needed. In simulations with MSC.Marc and Thirdwave AdvantEdge, there is no separation criterion defined since chip format...
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 rescheduling problem with controllable processing times:trade-off between number of disrupted jobs and reschedulingcosts Cincioğlu, Derya; Gürel, Sinan; Department of Industrial Engineering (2011) 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 ev...

Citation Formats

S. İ. Özbakır, “A heuristic approach for the single machine scheduling tardiness problems,” M.S. - Master of Science, Middle East Technical University, 2011.