Sıra bağımlı hazırlık süreleriyle tekli makina çizelgeleme

In this thesis, we study a single machine scheduling problem with sequence dependent-setup times where the jobs are processed in shifts with constant length. There is a certain amount of time between each pair of consecutive shifts for periodic maintenance, the machine does not work in maintenance but this time can also be used for the setup. Our goal is to complete the jobs in minimum amount of time. The setting considered in this thesis has applications in different industries including beverage and chemical industries. The problem can be solved with a small number of jobs by using some mathematical models in computer environment. However, as the number of jobs increases, the difficulty of solving the problem increases exponentially. In order to overcome the problem, we proposed heuristic algorithms, and they provided us to find good solutions for the problem. The new heuristic algorithm is based on the First Fit Algorithm (FF) that is used for solution of bin packing problems. Firstly, First Fit Decreasing (FFD) Algorithm has been applied to the problem, and jobs were assigned to shifts. For each shift in the result of FFD algorithm, used setup times were reduced by changing the orders of jobs in shift. The gaps occurred in some shifts with decrease in setup time used. All shifts were combined to fill in the gaps and FF algorithm was run. This process was repeated until there is no more improvement to be achieved for completion time of last job. This algorithm was named as Improved First Fit Heuristic (IFFH) algorithm. Then, according the result of IFFH algorithm, binary combinations of shifts and last shift were concatenated. The IFFH algorithm was repeated three times for the triple combinations of shifts. The minimum completion time was accepted as a solution. This algorithm was named as Improved First Fit Heuristic-2 (IFFH-2) algorithm. Consequently, the algorithms were compared with benchmarks in the literature.