A heuristic approach for the single machine scheduling tardiness problems

Özbakır, Saffet İlker
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.


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...
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 ...
A Computational study on a time-sensitive multiobjective flexible job shop scheduling problem
Oğuzkan, Caner; Çavdar, Bahar; Department of Industrial Engineering (2017)
In this thesis we focus on a time-sensitive flexible job shop scheduling problem. In time-sensitive systems, the main concern is more on the total completion time, which includes time spent during the computation-only phase and the implementation of the solution, rather than finding a solution which will take the least time to implement. However, the conventional solution approaches do not directly address the computation time. In this study, we employ a Computation-Implementation Parallezation (CIP) approa...
A conwip application in an electronics company
Güngörer, Elif; Özdemirel, Nur Evin; Department of Industrial Engineering (2010)
In this thesis, a real world application of the constant work in process (Conwip) system in an electronics company is realized. The aim of the application is to reduce the work in process (WIP) inventory while maintaining the same throughput level. A model is developed to determine the constant work in process level of the Conwip system for the production lines in this company. The approximated mean value analysis approach is used for the solution. Real system data are collected before and after the Conwip ...
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.