In this study, a single machine scheduling problem with one flexible availability constraint has been studied. In real world situations, the machine is not continuously available andthe unavailability arises from such issues as breakdowns, tool changes or maintenance activities. In most of previous studies, the start and finish times of availability constraint are considered to be fixed. This study assumes that this constraint is placed in a time window. In other words, the earliest possible start time and the latest possible finish time of availability constraint are specified. Since, solve of most optimization problems optimally in real sizes and reasonable time is almost impossible, researchers usually resort to simpler suboptimal but efficient approaches. Approximation approaches are a justify; MARGIN: 0in 0in 8pt" For the objective of minimizing total completion time, an approximation algorithm based on the shortest processing time rule is presented and it is shown that its worst case error bound is equal to and tight. As well as, forsolvingthisproblemoptimally, two pseudo polynomial dynamic programming algorithms are introduced. The first algorithmconsiders all possible values for the start time window of availability constraint, and for each value, solves the problem with fixed availability constraint.But, in the second algorithm the problem is solved directly. Then, by structuring these two dynamic programming algorithms, two fully polynomial-time approximation schemes are presented for this problem. Also, for the objective of minimizing total weighted completion time, an approximation algorithm with tight worst case error bound of 2 is introduced. In addition, one of the two previous dynamic programming algorithms is generalized for this objective function and is transformed to a fully polynomial-time approximation scheme.
