Abstract

Most of the applied and interesting problems in industry and real world are difficult to solve. These problems are often NP-hard and the problem in this paper is strongly NP-hard. Approximation and metaheuristic algorithms are used to find a solution to these problems. In this paper we have used a polynomial time approximation algorithm, this algorithm is a suboptimal approach that provably works fast and that provably yields solutions of very high quality. In this paper, the problem of scheduling jobs on a single machine with controllable processing times is considered. The fact that the n jobs have controllable processing times means that it is possible to reduce the processing time of the jobs by paying a certain cost. In this paper, each job has a release date when it becomes available for processing, and, after completing its processing, requires an additional delivery time. Furthermore, preemption is allowed. The preemptive version allows an operation to be interrupted and continued at a later time. Feasible schedules are further restricted by job precedence constraints. The algorithm in this paper gives a substantial improvement for the special case without controllable processing times obtained by Hall et al. (1989) and the special case with controllable processing times by Mastrolilli (2009). In this paper we added controllable processing time instead fixed processing time and preemption to the problem. Moreover, we develop a polynomial time approximation scheme whose running time depends only linearly on the input size. This improves and generalize the previous 3/2+ε-approximation algorithm by Mastrolilli (2009). At last it will be shown that the problem with its constraints has a polynomial time approximation scheme. It means that for any given ε, a polynomial algorithm exists for the problem. It will be shown by a numerical example finally.

Key words: Scheduling, controllable processing times, polynomial time approximation scheme (PTAS), metaheuristic methods, computational complexity, intractable problems