ABSTRACT
A HEURISTIC APPROACH FOR THE SINGLE MACHINE SCHEDULING TARDINESS PROBLEMS
Ö / zbakir, Saffet Ilker
M.Sc., Department of Industrial Engineering
Supervisor : Prof. Dr. Ö / 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.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12613742/index.pdf |
| Date | 01 September 2011 |
| Creators | Ozbakir, Saffet Ilker |
| Contributors | Kirca, Omer |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | M.S. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for public access |
Page generated in 0.0018 seconds