Research On Single Machine Scheduling Under Availability And Due Indices

In the practical production, as we all know, machines are not continuously available for processing throughout the planning horizon. Many reasons, such as maintenance re-quirements and breakdowns, can cause a machine not to be available for processing. In this thesis, the machine unavailability means that the machine has one specified unavailable interval. For the job position restrictions, we mean that each job must be processed at a position no later than its due index which is a specific position for this job. In this thesis,we investigate some single machine scheduling problems with both availability constraints and positional due indices.The main contents in our research can be divided into two parts. In the first part we discuss preemptive scheduling problems with an unavailable interval [R, D] and positional due indices. In the second part we study unpreemptive single machine total completion time scheduling problem with an unavailable interval [R, D] and positional due indices.We use h1 to denote the restriction that there is one unavailable interval during the processing on the machine and use σ[Jj]≤kj to denote the restriction that job Jj can only be processed in the first kj positions on the machine.In Chapter 2, we study the following three scheduling problems:· The single machine preemptive scheduling problem to minimize the maximum lateness:1,h1|σ[Jj]≤kj,pmtn|Lmax.· The single machine preemptive scheduling problem to minimize the total completion time: 1,h1|σ[Jj]≤kj, pmtn|Σ Cj.· The single machine preemptive scheduling problem to minimize the maximum scheduling cost: 1,h1|σ[Jj] ≤kj,pmtn|fmax.For the above three problems, we present three polynomial-time algorithms, respec-tively.In Chapter 3, we study the following scheduling problem:· The single machine unpreemptive scheduling problem to minimize the total completion time:1,h1|σ[Jj]≤kj|ΣCj.For this problem, we present an approximation algorithm with a worst-case ratio of 2 in Section 3.2. Then, in Section 3.3, we show that if we restrict the lengthes of some specific jobs, then there is an approximation algorithm with a worst-case ratio of 20/17.In Section 3.4, we present a polynomial-time approximation scheme under the same condition with Section 3.3.