Return to search

A Heuristic Approach For The Single Machine Scheduling Tardiness Porblems

ABSTRACT



A HEURISTIC APPROACH FOR THE SINGLE MACHINE SCHEDULING TARDINESS PROBLEMS




&Ouml / zbakir, Saffet Ilker
M.Sc., Department of Industrial Engineering
Supervisor : Prof. Dr. &Ouml / mer Kirca


September 2011, 102 pages



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.

Identiferoai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12613742/index.pdf
Date01 September 2011
CreatorsOzbakir, Saffet Ilker
ContributorsKirca, Omer
PublisherMETU
Source SetsMiddle East Technical Univ.
LanguageEnglish
Detected LanguageEnglish
TypeM.S. Thesis
Formattext/pdf
RightsTo liberate the content for public access

Page generated in 0.0018 seconds