Erteleme kısıtlı tek makine çizelgeleme

In a single machine problem a set of tasks has to be processed without preemption on a machine in such a way that at most one task is processed at any time and a given objective function is optimized. This thesis examines the single machine scheduling problems with timelag constraints. In these problems, precedence relations exist among the tasks that are to be scheduled. In a precedence relation, successor task is not allowed to start before the processing of the predecessor task is completed. Precedence relations may be generalized by adding the timelag constraints. In this thesis, timelags are assumed to be minimal timelags. Timelag constraint necessitates delaying the start time of the successor task after the completion time of the preceding task. Precedence constraints between tasks that have to be respected in every feasible schedule generally increase the computational complexity of a scheduling problem. Occasionally, their introduction may turn a problem that is solvable within polynomial time into an NP-complete one (Lenstra and Rinnoy Kan, 1978). Generalizing the problems with precedence constraints by introducing the timelag constraint makes problems harder. In addition to precedence and timelag constraints, the release time constraint is considered in this thesis. Even though there exists a wide variety of results on the complexity of scheduling problems with precedence and timelag constraints, there are still some problems for which the complexity status remains open. In this thesis, two scheduling problems with open complexity status are proven to be polynomially solvable. Also, a scheduling problem which is the generalization of two strongly NP-hard problems is considered and a branch and bound algorithm is proposed. Furthermore, for each problem, integer programming model is given. Finally, computational results are provided.