% Template article for preprint document class `elsart'
% SP 2001/01/05
% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/
% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}
% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}
% The amssymb package provides various useful mathematical symbols


\documentclass{ctwart}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amssymb}


\begin{document}


\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{New Fully Polynomial Time Approximation Scheme for the makespan minimization with positive tails on a single machine with a fixed non-availability interval}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Imed Kacem}

\address{LITA, Université Paul Verlaine--Metz, Ile du Saulcy. Metz 57000 cedex, France. (Email address: kacem@univ-metz.fr).}

\begin{keyword}
% keywords here, in the form: keyword \sep keyword

scheduling \sep non-availability constraint \sep approximation \sep makespan

\end{keyword}

\end{frontmatter}

% main text

\section{Introduction}

The studied problem ($\mathcal{P}$) can be formulated as follows. We have to
schedule a set $J$ of $n$ jobs on a single machine, where every job $j$ has
a processing time $p_{j}$ and a tail $q_{j}$. The machine can process at
most one job at a time and it is unavailable between $T_{1}$\ and $T_{2}$\
(i.e., $\left[ T_{1},T_{2}\right) $\ is a forbidden interval)\textbf{.}
Preemption of jobs is not allowed (jobs have to be performed under the
non-resumable scenario). All jobs are ready to be performed at time $0$.
With no loss of generality, we consider that all data are integers and that
jobs are indexed according to Jackson's rule \cite{CARLIER} (i.e., jobs are
indexed in nonincreasing order of tails). Therefore, we assume that $%
q_{1}\geq q_{2}\geq ...\geq q_{n}$. The consideration of tails is motivated
by the large set of scheduling problems such that jobs have delivery times
after their processing. As an example, it is well-known that the
minimization of makespan with tails is equivalent to the minimization of the
maximum lateness with due dates \cite{dessouky}. Let $C_{j}\left( S\right) $
denote the completion time of job $j$ in a feasible schedule $S$ for the
problem and let $\mathcal{\varphi }_{S}(\mathcal{P})$ be the makespan
yielded by schedule $S$ for instance $\mathcal{I}$ of ($\mathcal{P}$):

\begin{equation}
\mathcal{\varphi }_{S}(\mathcal{I})=\max_{1\leq j\leq n}\left( C_{j}\left(
S\right) +q_{j}\right)
\end{equation}%
The aim is to find a feasible schedule $S$ by minimizing the makespan. Due
to the dominance of Jackson's order, an optimal schedule is composed of two
sequences of jobs scheduled in nondecreasing order of their indexes.

If all the jobs can be inserted before $T_{1}$, the instance studied ($%
\mathcal{I}$) has obviously a trivial optimal solution obtained by Jackson's
rule. We therefore consider only the problems in which all the jobs cannot
be scheduled before $T_{1}$.

In the remainder\ of this paper $\mathcal{\varphi }^{\ast }(\mathcal{I})$
denotes the minimal makespan for instance $\mathcal{I}$.

This type of problems has been studied in the literature under various
criteria (a sample of these works includes Lee \cite{lee96}, Kacem \cite%
{kacem}, Kubzin and Strusevich \cite{kubzin}, Qi \textit{et al.} \cite{Qi}-%
\cite{qct99}, Schmidt \cite{sch00}, He \textit{et al.} \cite{HeZhongGu}).
However, few papers studied the problem we consider in this paper. Lee \cite%
{lee96} explored the Jackson's sequence $JS$ and proved that its deviation
to the optimal makespan cannot exceed $\max_{1\leq j\leq n}\left(
p_{j}\right) $, which is equivalent to state that $\mathcal{\varphi }_{JS}(%
\mathcal{I})\leq 2\mathcal{\varphi }^{\ast }(\mathcal{I})$. Recently, Yuan
et al. developed an interesting PTAS for the studied problem \cite{yuan}%
\textbf{.} That is why this paper is a good attempt to design more efficient
approximation heuristics and approximation schemes to solve the studied
problem.

\section{New FPTAS}

Now, let describe our FPTAS. It uses a simplification technique based on
merging small jobs \cite{KK}. First, we simplify the instance $\mathcal{I}$
as follows. Given an arbitrary $\varepsilon >0$, we split the interval $%
[0,\max_{j\in J}\{q_{j}\}]$ in $1/\varepsilon $ equal lenght intervals and
we round up every tail $q_{j}$ to the next multiple of $\varepsilon 
\overline{q}$ ($\overline{q}=\max_{j\in J}\{q_{j}\}$). Then, we obtain a new
instance $\mathcal{I}^{\prime }$ with no ($1+\varepsilon $)-loss. Thus, $J$
can be divided into $1/\varepsilon $ subsets $J(k)$ ($1\leq k\leq
1/\varepsilon $) where jobs in $J(k)$ have identical tails of $k\varepsilon 
\overline{q}$. The second modification consists in reducing the number of
small jobs in every subset $J(k)$. Small jobs are those having processing
times $<\varepsilon P/2$ where $P=p_{1}+p_{2}+...+p_{n}$. The reduction is
done by merging the small jobs in each $J(k)$ so that we obtain new greater
jobs having processing times between $\varepsilon P/2$ and $\varepsilon P$.
At most, for every subset $J(k)$, a single small job remains. We show that
this reduction cannot increase the optimal solution value by more than ($%
1+\varepsilon $)-factor. We re-index jobs according to nondecreasing order
of their tails. The new instance we obtain is denoted as $\mathcal{I}%
^{\prime \prime }$. Clearly, the number of jobs remaining in the simplified
instance $\mathcal{I}^{\prime \prime }$ is less than $3/\varepsilon $.

Our FPTAS is based on two steps. First, we use the Jackson's sequence $JS$
obtained for the initial instance $\mathcal{I}$. Then, we apply a modified
dynamic programming algorithm $APS_{\varepsilon }^{\prime }$ on instance $%
\mathcal{I}^{\prime \prime }$. The main idea of $APS_{\varepsilon }^{\prime
} $ is to remove a special part of the states generated by a dynamic
programming algorithm (See Kacem \cite{kacem}). Therefore, the modified
algorithm becomes faster and yields an approximate solution instead of the
optimal schedule.

Given an arbitrary $\varepsilon >0$, we define $\overline{n}=\min
\{n,3/\varepsilon \}$, $\omega _{1}=\left\lceil \frac{4\overline{n}}{%
\varepsilon }\right\rceil $, $\omega _{2}=\left\lceil \frac{2\overline{n}^{2}%
}{\varepsilon }\right\rceil $, $\delta _{1}=\frac{\mathcal{\varphi }%
_{JS}\left( \mathcal{I}\right) }{\omega _{1}}$and $\delta _{2}=\frac{T_{1}}{%
\omega _{2}}$.

We split $\left[ 0,\mathcal{\varphi }_{JS}\left( \mathcal{I}\right) \right) $%
\ into $\omega _{1}$\ equal subintervals $I_{m}^{1}=\left[ (m-1)\delta
_{1},m\delta _{1}\right) _{1\leq m\leq \omega _{1}}$. We also split $\left[
0,T_{1}\right) $\ into $\omega _{2}$\ equal subintervals $I_{s}^{2}=\left[
(s-1)\delta _{2},s\delta _{2}\right) _{1\leq s\leq \omega _{2}}$\ of length $%
\delta _{2}$. Moreover, we define the two singletons $I_{\omega
_{1}+1}^{1}=\left\{ \mathcal{\varphi }_{JS}\left( \mathcal{I}\right)
\right\} $\ and $I_{\omega _{2}+1}^{2}=\left\{ T_{1}\right\} $. Our
algorithm $APS_{\varepsilon }^{\prime }$ generates reduced sets $\mathcal{X}%
_{k}^{\#}$ of states $\left[ t,f\right] $ where $t$ is the total processing
time of jobs assigned before $T_{1}$ in the associated partial schedule and $%
f$ is the makespan of the same partial schedule. It can be described as
follows:

\begin{itemize}
\item[ \ \ \ ] \textbf{Algorithm }$APS_{\varepsilon }^{\prime }$

\item[(i). ] Set $\mathcal{X}_{0}^{\#}=\{[0,0]\}$.

\item[(ii). ] For $k\in \left\{ 1,2,3,...,\overline{n}\right\} $,

\begin{itemize}
\item[ ] For every state $\left[ t,f\right] $ in $\mathcal{X}_{k-1}^{\#}$: 
\newline
1) Put $\left[ t,\max \left( f,T_{2}+\sum_{i=1}^{k}p_{i}-t+q_{k}\right) %
\right] $ in $\mathcal{X}_{k}^{\#}$ \newline
2) Put $\left[ t+p_{k},\max \left( f,t+p_{k}+q_{k}\right) \right] $ in $%
\mathcal{X}_{k}^{\#}$ if $t+p_{k}\leq T_{1}$

\item[ ] Remove $\mathcal{X}_{k-1}^{\#}$

\item[ ] Let $\left[ t,f\right] _{m,s}$ be the state in $\mathcal{X}%
_{k}^{\#} $ such that $f\in I_{m}^{1}$ and $t\in I_{s}^{2}$\ with the
smallest possible $t$ (ties are broken by choosing the state of the smallest 
$f$). \newline
\textbf{Set }$\mathcal{X}_{k}^{\#}=\left\{ \left[ t,f\right] _{m,s}|1\leq
m\leq \omega _{1}+1,1\leq s\leq \omega _{2}+1\right\} $\textbf{.}
\end{itemize}

\item[(iii). ] $\mathcal{\varphi }_{APS_{\varepsilon }^{\prime }}\left( 
\mathcal{I}\right) =\min_{\left[ t,f\right] \in \mathcal{X}_{n}^{\#}}\left\{
f\right\} $.
\end{itemize}

\begin{theorem}
Given an arbitrary $\varepsilon >0$, algorithm $APS_{\varepsilon }^{\prime }$
yields an output $\mathcal{\varphi }_{APS_{\varepsilon }^{\prime }}\left( 
\mathcal{I}^{\prime \prime }\right) $ such that: 
\begin{equation}
\mathcal{\varphi }_{APS_{\varepsilon }^{\prime }}\left( \mathcal{I}^{\prime
\prime }\right) -\mathcal{\varphi }^{\ast }\left( \mathcal{I}^{\prime \prime
}\right) \leq \varepsilon \mathcal{\varphi }^{\ast }\left( \mathcal{I}%
^{\prime \prime }\right) .  \label{eq3}
\end{equation}
\end{theorem}

\begin{proof}
It will be presented at the conference.
\end{proof}

\begin{lemma}
Given an arbitrary $\varepsilon >0$, algorithm $APS_{\varepsilon }^{\prime }$
can be implemented in $O\left( n\log n+\min \{n,1/\varepsilon
\}^{4}/\varepsilon ^{2}\right) $ time.
\end{lemma}

The schedule obtained by $APS_{\varepsilon }^{\prime }$ for instance $%
\mathcal{I}^{\prime \prime }$ can be easily converted into a feasible one
for instance $\mathcal{I}$. This can be done in $O\left( n\right) $ time.
>From the previous lemma and theorem, the main result is proved and the
following corollary holds.

\begin{corollary}
Algorithm $APS_{\varepsilon }^{\prime }$ is an FPTAS and it can be
implemented in $O\left( n\log n+\min \{n,1/\varepsilon \}^{4}/\varepsilon
^{2}\right) $ time.
\end{corollary}

\section{Conclusion}

In this paper, we considered the non-resumable case of the single machine
scheduling problem with a fixed non-availability interval. Our aim is to
minimize the makespan\textbf{\ }when every job has a positive tail. We
showed that the problem has an FPTAS (Fully Polynomial Time Approximation
Scheme). Such an FPTAS is strongly polynomial. The obtained results
outperform the previous polynomial approximation algorithms for this problem.

\begin{thebibliography}{99}
\bibitem{CARLIER} Carlier, J., 1982. The one-machine sequencing problem. 
\textit{European Journal of Operational Research} 11, 42-47.

\bibitem{dessouky} Dessouky, M.I., Margenthaler, C.R., 1972. The one-machine
sequencing problem with early starts and due dates. \textit{AIIE Transactions%
} 4:3, 214-222.

\bibitem{HeZhongGu} He, Y., Zhong, W., Gu, H., 2006. Improved algorithms for
two single machine scheduling problems. \textit{Theoretical Computer Science}
363, 257-265.

\bibitem{kacem} Kacem, I., 2009. Approximation algorithms for the makespan
minimization with positive tails on a single machine with a fixed
non-availability interval. \textit{Journal of Combinatorial Optimization}
17:2, 117-133.

\bibitem{KK} Kacem, I., Kellerer, H., 2010. No-Wait Scheduling of a
Single-Machine to Minimize the Maximum Lateness, \textit{Proceedings of the
24}$^{\mathit{th}}$\textit{\ Annual Conference of the Belgian Operational
Society}, Li\`{e}ge, January 28-29.

\bibitem{kubzin} Kubzin, M.A., Strusevich, V.A., 2006. Planning machine
maintenance in two machine shop scheduling. \textit{Operations Research\ }%
54, 789-800.

\bibitem{lee96} Lee, C.Y., 1996. Machine scheduling with an availability
constraints. \textit{Journal of Global Optimization} 9, 363-384.

\bibitem{Qi} Qi, X., 2007. A note on worst-case performance of heuristics
for maintenance scheduling problems. \textit{Discrete Applied Mathematics}
155, 416-422.

\bibitem{qct99} Qi, X., Chen, T., Tu, F., 1999. Scheduling the maintenance
on a single machine. \textit{Journal of the Operational Research Society}
50, 1071-1078.

\bibitem{sch00} Schmidt, G., 2000. Scheduling with limited machine
availability. \textit{European Journal of Operational Research} 121, 1-15.

\bibitem{yuan} Yuan, J.J., Shi, L., and Ou, J.W., 2008. Single machine
scheduling with forbidden intervals and job delivery times. \textit{%
Asia-Pacific Journal of Operational Research }25:3, 317-325.
\end{thebibliography}

\end{document}