An approximation algorithm for the two identical parallel machine problem under machine availability constraints

ABSTRACT

This study addresses the scheduling problem of two identical parallel machines with the objective of minimizing the total completion time under the machine availability constraints. To the best of our knowledge, this study is the first to develop a fully polynomial-time approximation scheme (FPTAS), a solution method which has been neglected in past studies, to solve the studied problem. The FPTAS, which is based on a dynamic programming algorithm is developed by applying a trimming-the-state-space approach. Theoretical proofs of the error bound and the time complexity for the proposed FPTAS are also provided. The computational results indicate that the proposed FPTAS performs more efficiently than a dynamic programming algorithm in terms of both run time and problem size. The error bound of the FPTAS is demonstrated to be within the pre-specified error bound.

KEYWORDS:

• Parallel machine scheduling
• machine availability constraints
• dynamic programming algorithm
• fully polynomial-time approximation scheme
• trimming-the-state-space approach

Disclosure statement

No potential conflict of interest was reported by the author(s).

Condition 4

Based on the definitions for $F_h\left(p_k,S\right)$, $H_{F_h}\left(p_k,S\right)$, $G$, $\mathcal{F}$, and the Dynamic Programming algorithm, it can be seen that

$F_h\left(p_k,S\right)$ and $H_{F_h}\left(p_k,S\right)$ ($h=1,\dots ,4$) are evaluated by mathematical operations including addition, subtraction, and multiplication which can be performed in polynomial time. Function $G\left(S\right)=t_5$ is evaluated in polynomial time. Condition 4(i) holds.

The finite set $\mathcal{F}$ consists of four mapping functions $F_h\left(p_k,S\right)$ with ($h=$ 1, 2, 3, 4). It is known that the cardinality of $\mathcal{F}$ is polynomially bounded in $n$. Condition 4(ii) holds.

The initial state space $S_0$ contains only one 5-dimensional state and the initial value for each dimension for this state is zero. Condition 4(iii) holds.

For a coordinate $i$ ($i=1,\dots ,5$), let $V_i$ ($I$) denote the set of the values of the $i$-th components of all vectors in all state spaces $S_k$ ($1\le k\le n$) for any instance $I$ of our scheduling problem. $B_i$ is the upper bound for $V_i$ ($I$), $i=1,2$; $\sum _{j=1}^n{p}_j$ is the upper bound for $V_i$ ($I$), $i=$ 3, 4; and $V_5$ ($I$) is bounded above by UB(SBT) . It results in the length of the binary encoding of every value is polynomially bounded in the input size. Condition 4(iv) is fulfilled.

It can be seen that conditions in Woeginger [42] all hold for the existence of an FPTAS under the structure of our scheduling problem and the dynamic programming. Therefore, our problem $P2,h_{i1}||\sum C_j$ is considered as a CC-benevolent problem in Woeginger [42], and thus an FPTAS exists. This completes the proof.

Additional information

Funding

This work was supported by the Ministry of Science and Technology, Taiwan [106-2410-H-008 −048 and 107-2410-H-008-032].