1 Introduction
We consider the following scheduling problem with
variable job processing times. Jobs
\(J_{0},J_1,\ldots ,J_{n},\) where
\(n>2\), have to be scheduled on a single machine, starting from time 0. All the jobs are independent, i.e. there are no precedence constraints among the jobs. The processing time of job
\(J_{j}\) linearly deteriorates in time and is equal to
\(p_{j}(t)=1+\alpha _{j}t\), where
t is the starting time of the job,
\(\alpha _{j}>0\) is its deterioration rate and
\(0\le j \le n\). Let
\(a^{\circ }=(a_{0},a_{1},\ldots ,a_{n})\) denote the initial sequence of coefficients
\(a_j=1+\alpha _j>1\), where
\(0\le j\le n\). Let
\({{\mathcal {P}}}(a^{\circ })\) denote the set of all permutations of sequence
\(a^{\circ }\). Notice that any sequence
\(a^{\pi } \in {{\mathcal {P}}}(a^{\circ }),\) in which the elements of sequence
\(a^{\circ }\) are ordered according to a permutation
\(\pi =(\pi _0,\pi _1,\ldots ,\pi _n)\) of indices
\(0,1,\ldots ,n\), corresponds to a schedule in which the job with index
\(\pi _0\) starts at time 0 and all remaining jobs are scheduled one by one without idle times. Therefore, in the paper we use terms ‘sequence’ and ‘schedule’ interchangeably, equating a given sequence
\(a^{\pi } \in {{\mathcal {P}}}(a^{\circ })\) with the schedule corresponding to
\(a^{\pi }\). Hence, for a given
\(a^{\pi }=(a_{\pi _0},a_{\pi _1},\ldots ,a_{\pi _n}) \in {{\mathcal {P}}}(a^{\circ })\), where
\(a_{\pi _j}=1+\alpha _{\pi _j}\) for
\(0 \le j \le n\), the completion time of the
jth job in the schedule corresponding to sequence
\(a^{\pi }\) is equal to
$$\begin{aligned} C_{j}(a^{\pi })= & {} C_{j-1}(a^{\pi })+p_{\pi _j}(C_{j-1}(a^{\pi }))= 1\nonumber \\&+\,a_{\pi _j}C_{j-1}(a^{\pi }), \end{aligned}$$
(1)
with
\(C_{0}(a^{\pi })=0+1+\alpha _{\pi _0}\cdot 0 =1,\) since job
\(J_{\pi _{0}}\) starts at time
\(t=0\). Then, the problem under consideration is to find a sequence corresponding to a schedule with minimal total completion time, i.e. to find
\(a^{\sigma } \in {{\mathcal {P}}}(a^{\circ })\) such that
$$\begin{aligned} \sum _{j=0}^{n}C_{j}(a^{\sigma })= \min _{a^{\pi } \in {{\mathcal {P}}}(a^{\circ })} \left\{ \sum _{j=0}^{n}C_{j}(a^{\pi })\right\} , \end{aligned}$$
where job completion times
\(C_j(a^{\pi })\) are defined by the recurrence equation (
1). Since sequences in which two equal elements have been mutually exchanged are identical, and since the order of jobs with the same deterioration rate has no impact on the value of the
\(\sum C_j\) criterion, we assume that
\(a_i \ne a_j\) whenever
\(i \ne j\) and
\(0\le i,j \le n.\) The problem formulated as above, in three-field notation denoted as
\(1|p_j(t)=1+\alpha _jt|\sum C_j\), in this paper is called
problem (
P).
Problem (
P) is a
time-dependent scheduling problem, where deteriorating job processing times are non-decreasing functions of the starting times of the respective jobs. Scheduling problems of this kind are dynamic in the sense that job processing times are not fixed but change in time. Research on time-dependent scheduling problems was started about 40 years ago, quickly evolving into a self-contained research domain in scheduling theory. We refer the reader to reviews by Cheng et al. (
2004) and Gawiejnowicz (
2020a), and books by Gawiejnowicz (
2008), Agnetis et al. (
2014), Strusevich and Rustogi (
2017) and Gawiejnowicz (
2020b) for more details on the subject.
In this paper, we prove several new results for problem (
P) and show some their consequences. The paper is organized as follows. In Sect.
2, we summarize the previous research on problem (
P). In Sect.
3, we formulate and prove some preliminary results which concern cyclic shifts of V-shaped sequences. In Sect.
4, we introduce a new necessary condition of schedule optimality for problem (
P) which lowers the previous bound on the cardinality of the set containing all possible optimal schedules for (
P) by a multiplicative factor at most proportional to the reciprocal of the square root of the number of jobs. In Sect.
5, we compare the power of the new and the previous necessary condition of schedule optimality for problem (
P), estimating the numbers of schedules which satisfy the respective condition. Finally, in Sect.
6, we present several numerical examples which illustrate the results of Sect.
5. We complete the paper with Sect.
7, including conclusions and remarks on future research.
2 Previous research on problem (P)
Research on problem (
P) has more than a 25-year-old history that was initiated by Mosheiov (
1991), who formulated the problem and proved some its properties.
The first property specifies which job is the first one in an optimal schedule.
In view of Property
1, in sequence
\(a^{\pi } \in {{\mathcal {P}}} (a^{\circ })\) corresponding to an optimal schedule the element
\(a_{\pi _0}\) corresponds to the greatest deterioration rate,
\(a_{\pi _0} = \max \{ 1+ \alpha _j : 0\le j \le n \}\).
The second property shows a symmetry of optimal schedules for problem (P).
By Property
2, for any instance of problem (
P) there exist at least two optimal schedules that are symmetric to each other, starting from the second position.
Before we formulate the third property, we recall a definition.
From Definition
1, it follows that a sequence is V-shaped if elements before and after the minimal element in the sequence are in the non-increasing and non-decreasing order, respectively.
The third property concerns the shape of an optimal schedule for the considered problem. We call the property the first necessary condition of schedule optimality for problem (P).
By Property
3, jobs in an optimal schedule are scheduled in the non-increasing or non-decreasing order with respect to job deterioration rates if the jobs are placed before or after the job with the smallest deterioration rate, respectively.
Mosheiov (
1994) considered a similar to (
P) single machine scheduling problem with proportionally deteriorating job processing times, i.e.
\(p_j(t)=\alpha _jt\), where
\(\alpha _j>0\) for
\(1\le j\le n\) and
\(t>0\), and showed that it is solvable in
\(O(n\log n)\) time by scheduling jobs in the non-decreasing order of job deterioration rates. Gawiejnowicz et al. (
2006a) defined functions of job deterioration rates, called
signatures, proved the basic properties of these functions and proposed two
\(O(n\log n)\) signature-based greedy algorithms for problem (
P). Gawiejnowicz et al. (
2006b) proved several properties of two generalizations of problem (
P), in which the aim is to minimize the weighted sum of the
\(C_{\max }\) and
\(\sum C_j\) criteria or to find a Pareto optimal schedule for them. Kubale and Ocetkiewicz (
2009) proposed an
\(O(n\log n)\) algorithm for (
P), provided that inequality
\(\alpha _i > \alpha _j\) implies inequality
\(\alpha _i \ge \frac{\alpha _{\min }+1}{\alpha _{\min }}\,\alpha _j + \frac{1}{\alpha _{\min }}\) for any
\(i \not = j\), where
\(\alpha _{\min }\) is the smallest deterioration rate. For a special case of (
P) in which all deterioration rates are not smaller than a certain constant
\(u > 0\), Ocetkiewicz (
2010) proposed a fully polynomial-time approximation scheme (FPTAS) running in
\(O(n^{1+6\log _{1+u}2}(\frac{1}{\epsilon })^{2\log _{1+u}2})\) time, where
\(\epsilon >0\) is a given accuracy. For general case of problem (
P), Ocetkiewicz (
2013) proposed a branch-and-bound algorithm. Gawiejnowicz and Kurc (
2015) shown that counterparts of Property
3 also hold for time-dependent scheduling problems with more general criterion functions than the total completion time, considering a generalization of problem (
P) with the objective to minimize the
\(l_p\) norm
\(\Vert C(a^{\pi })\Vert _p=\left( \sum _{j=0}^{n} C_j(a^{\pi })^p\right) ^{\frac{1}{p}}\) of vector
\(C(a^{\pi })=(C_0(a^{\pi }),C_1(a^{\pi },\ldots ,C_n(a^{\pi })),\) where
\(1\le p \le + \infty \). The authors showed that the symmetry of optimal schedules that holds for the total completion time, i.e. for
\(p{=}1\), may hold for the
\(l_p\) norm only for some
\(p>1\), while the V-shapeness of optimal schedules for the
\(l_p\) norm and bounded logarithmic growth of the criterion function values hold both for
\(p=1\) and for all
\(p{>}1\).
Despite so long research history, the time complexity of problem (
P) is still unknown. We only know that Properties
1–
3 allow us to decrease the cardinality of the set containing all possible optimal schedules for (
P) from
O(
n!) to
\(O(2^{n-1})\). Hence, finding a new property for (
P) is a challenging research task. In this paper, we take a step in this direction, proving a new necessary condition for (
P), which implies the decrease in the bound
\(O(2^{n-1})\) by the factor between
\(1 - \frac{1}{\sqrt{n}} \times 2^{O(1)}\) and
\(O(n^{-\frac{1}{2}})\) for sequences
\(a^{\circ }\) in which their minimal and maximal elements are sufficiently close, and by the factor
\(1 - \frac{2^{-n}}{\sqrt{n}} \times 2^{O(1)}\) for arbitrary sequences
\(a^{\circ }\).
3 Preliminary results
Since the results presented further on concern arbitrary but fixed sequences from the set
\({{\mathcal {P}}}(a^{\circ })\), starting from this section we use simplified notation in which we omit superscripts related to permutations, e.g. we write
a instead of
\(a^{\pi }\). Similarly, we denote the full form of considered sequences, taking into account the properties of problem (
P). For example, we write
\(a=(a_{1},\ldots ,a_{n}) \in {{\mathcal {P}}}(a^{\circ })\) instead of
\(a^{\pi }=(a_{\pi _0},a_{\pi _1},\ldots ,a_{\pi _n}) \in {{\mathcal {P}}}(a^{\circ })\), omitting
\(a_{\pi _0}\), since it is fixed by Property
1.
Throughout the paper, we assume that any V-shaped sequence is composed of the left and the right branch. If one of the branches is empty, the V-shaped sequence becomes a non-increasing or non-decreasing sequence. A V-shaped sequence with non-empty branches may be composed of distinct or non-distinct elements. Since any pair of non-distinct elements of a sequence decreases the number of V-shaped sequences which we can generate from this sequence, we assume that V-shaped sequences are composed only of distinct elements. We also distinguish the case when the minimal element of a V-shaped sequence belongs either to the left or to the right branch of the sequence.
Let
\(a(a_r \leftrightarrow a_q)\) denote sequence
\(a=(a_1,a_2,\ldots ,a_n)\) with elements
\(a_r\) and
\(a_q\) mutually exchanged, where
\(1\le r < q \le n\). Observe that for given
a and
\(b=a(a_{r}\leftrightarrow a_{q})\), where
r and
q are indices defined above, and for
\(j=0,1,\ldots ,n\) there holds the equality (Gawiejnowicz et al.
2006b):
$$\begin{aligned}&C_{j}(b)-C_{j}(a)\nonumber \\&\quad =\left\{ \begin{array}{ll} \left( \frac{a_{r}-a_{q}}{a_{q}}\right) \sum \limits _{i=r}^{q-1}\prod \limits _{k=i+1}^{j}a_{k} , &{} \quad 1\le r<q\le j\le n, \\ \left( \frac{a_{q}-a_{r}}{a_{r}}\right) \sum \limits _{i=0}^{r-1}\prod \limits _{k=i+1}^{j}a_{k}, &{}\quad 1\le r\le j<q\le n, \\ 0, &{}\quad 0\le j<r<q\le n. \end{array} \right. \end{aligned}$$
(2)
Summing formula (
2) side by side for
\(j=0,1,\ldots ,n\), we have
$$\begin{aligned}&\Vert C(b)\Vert _{1}-\Vert C(a)\Vert _{1} \nonumber \\&\quad = (a_{q}-a_{r}) \left( \sum \limits _{j=r}^{q-1}\frac{1}{a_{r}}\sum \limits _{i=0}^{r-1}(a_{i+1}\cdots a_{r}\cdots a_{j})\right. \nonumber \\&\qquad \left. -\sum \limits _{j=q}^{n}\frac{1}{a_{q}}\sum \limits _{i=r}^{q-1}(a_{i+1}\cdots a_{q}\cdots a_{j})\right) . \end{aligned}$$
(3)
By simplifying the second difference in Eq. (
3), we obtain equality
$$\begin{aligned}&\Vert C(b)\Vert _{1}-\Vert C(a)\Vert _{1} \nonumber \\&\quad = (a_{q}-a_{r})\left[ \left( \sum \limits _{j=r}^{q-1}\prod \limits _{k=r+1}^{j}a_{k}\right) \left( \sum \limits _{i=0}^{r-1}\prod \limits _{k=i+1}^{r-1}a_{k}\right) \right. \nonumber \\&\qquad \left. -\left( \sum \limits _{i=r}^{q-1} \prod \limits _{k=i+1}^{q-1}a_{k}\right) \left( \sum \limits _{j=q}^{n}\prod \limits _{k=q+1}^{j}a_{k}\right) \right] . \end{aligned}$$
(4)
Mutually exchanging in Eq. (
4) two consecutive elements with indices
r and
\(q=r+1\), where
\(1 \le r \le n-1\), we obtain equality
$$\begin{aligned}&\Vert C(b)\Vert _{1}-\Vert C(a)\Vert _{1}\nonumber \\&\quad =(a_{r+1}-a_{r}) \left( \sum _{j=0}^{r-1}\prod _{k=j+1}^{r-1}a_{k}-\sum _{i=r+1}^{n} \prod _{k=r+2}^{i}a_{k}\right) . \end{aligned}$$
(5)
3.2 Cyclic shifts
Given sequence
\(a=(a_{1},\ldots ,a_{r},\ldots ,a_{q},\ldots ,a_{n}),\) where
\(1\le r<q\le n,\) let
\(a(a_r\leftarrow a_q)\) denote sequence
a in which element
\(a_q\) has been moved immediately before element
\(a_r\). Similarly, let
\(a(a_r\rightarrow a_q)\) denote sequence
a in which element
\(a_r\) has been moved immediately after element
\(a_q\), i.e. let
$$\begin{aligned} a(a_r\leftarrow a_q){=}(a_{1}{,}\ldots {,}a_{r{-}1}{,}a_{q}{,}a_{r}{,}\ldots {,}a_{q{-}1}{,}a_{q{+}1},\ldots ,a_{n})\nonumber \\ \end{aligned}$$
(6)
and
$$\begin{aligned} a(a_r \rightarrow a_q){=}(a_{1}{,}{\ldots }{,}a_{r{-}1}{,}a_{r{+}1}{,}{\ldots }{,}a_{q}{,}a_{r}{,}a_{q{+}1}{,}\ldots {,}a_{n}){.}\nonumber \\ \end{aligned}$$
(7)
We call
\(a(a_r\leftarrow a_q)\) and
\(a(a_r \rightarrow a_q)\) the
cyclic shifts of sequence
a.
Notice that given
a and
\(1\le r<q\le n,\) we can obtain the cyclic shifts
\(a(a_r \leftarrow a_q)\) and
\(a(a_r \rightarrow a_q)\) by consecutive transpositions of suitable pairs of elements in
a. Namely, if we define
\({\overline{a}}^{\,0}=a\), then
$$\begin{aligned} \begin{array}{l c l} {\overline{a}}^{1} &{} = &{} {\overline{a}}^{\,0}({\overline{a}}_{q}^{\,0}\leftrightarrow {\overline{a}}_{q-1}^{\,0}), \\ {\overline{a}}^{2} &{} = &{} {\overline{a}}^{1}({\overline{a}}_{q-1}^{1}\leftrightarrow {\overline{a}}_{q-2}^{1}), \\ \ldots &{} &{} \ldots , \\ {\overline{a}}^{\,q-r} &{} = &{} {\overline{a}}^{\,q-r-1}({\overline{a}}_{r}^{\,q-r-1}\leftrightarrow {\overline{a}}_{r+1}^{\,q-r-1}) \end{array} \end{aligned}$$
(8)
or, in explicit form,
$$\begin{aligned} \begin{array}{l c l} {\overline{a}}^{\,0}&{} {=} &{} (a_{1}{,}{\ldots }{,}a_{r}{,}a_{r+1},a_{r+2},\ldots ,a_{q-1},\boxed {a_{q}},a_{q+1},\ldots ,a_{n}), \\ {\overline{a}}^{1}&{} = &{} (a_{1},\ldots ,a_{r},a_{r+1},a_{r+2},\ldots ,\boxed {a_{q}},a_{q-1},a_{q+1},\ldots ,a_{n}), \\ \ldots &{} \ldots &{} \ldots , \\ {\overline{a}}^{\,q-r-1}&{} = &{} (a_{1},\ldots ,a_{r},\boxed {a_{q}},a_{r+1},\ldots ,a_{q-1},a_{q+1},\ldots ,a_{n}), \\ {\overline{a}}^{\,q-r}&{} = &{} (a_{1},\ldots ,\boxed {a_{q}},a_{r},a_{r+1},\ldots ,a_{q-1},a_{q+1},\ldots ,a_{n}),\\ \end{array}\nonumber \\ \end{aligned}$$
(9)
where box indicates the element
\(a_q\) which is shifted in sequence
a. In other words,
\({\overline{a}}^{1}\) is the result of transposition of the
\({(q-1)}\)th and
qth components of sequence
\({\overline{a}}^{\,0}=a\),
\({\overline{a}}^{2}\) is the result of transposition of the
\({(q-2)}\)th and
\({(q-1)}\)th components of
\({\overline{a}}^{\,0}=a\), etc. Finally,
\({\overline{a}}^{\,q - r}\) is the result of transposition of the
rth and
\({(r+1)}\)th components of
\({\overline{a}}^{\,q-r-1}.\) Therefore, we can identify
\(a(a_r\leftarrow a_q)\) with
\({\overline{a}}^{\,q - r}\).
Similarly, defining
\({\underline{a}}^{0}=a\), applying in
\({\underline{a}}^{0}\) the transposition of elements
\({\underline{a}}^{0}_{\,r}\) and
\({\underline{a}}^{0}_{\,r+1}\) from the left to right and proceeding further as previously, we have
$$\begin{aligned} \begin{array}{l c l} {\underline{a}}^{1} &{} = &{} {\underline{a}}^{0}({\underline{a}}_{\,r+1}^{0}\leftrightarrow {\underline{a}}_{\,r}^{0}), \\ {\underline{a}}^{2} &{} = &{} {\underline{a}}^{1}({\underline{a}}_{\,r+2}^{1}\leftrightarrow {\underline{a}}_{\,r+1}^{1}), \\ \ldots &{} &{} \ldots , \\ {\underline{a}}^{q-r} &{} = &{} {\underline{a}}^{q-r-1}({\underline{a}}_{\,q}^{q-r-1}\leftrightarrow {\underline{a}}_{\,q-1}^{q-r-1}) \end{array}\nonumber \\ \end{aligned}$$
(10)
or, in explicit form,
$$\begin{aligned} \begin{array}{l c l} {\underline{a}}^{\,0} &{} = &{} (a_{1},\ldots ,\boxed {a_{r}},a_{r+1},a_{r+2},\ldots ,a_{q-1},a_{q}, a_{q+1},\ldots ,a_{n}), \\ {\underline{a}}^{1} &{} = &{} (a_{1},\ldots ,a_{r+1},\boxed {a_{r}},a_{r+2},\ldots ,a_{q-1}, a_{q},a_{q+1},\ldots ,a_{n}), \\ \ldots &{} \ldots &{} \ldots , \\ {\underline{a}}^{\,q-r-1} &{} = &{} (a_{1},\ldots ,a_{r+1},a_{r+2},a_{r+3},\ldots ,\boxed {a_{r}},a_{q},a_{q+1},\ldots ,a_{n}), \\ {\underline{a}}^{\,q-r} &{} = &{} (a_{1},\ldots ,a_{r+1},a_{r+2},a_{r+3},\ldots ,a_{q},\boxed {a_{r}},a_{q+1},\ldots ,a_{n}). \end{array}\nonumber \\ \end{aligned}$$
(11)
Therefore,
\(a(a_r \rightarrow a_q)\) can be identified with
\({\underline{a}}^{q-r}.\)
Hence, in view of formulae (
8)–(
11), we use symbols
\(a(a_r\leftarrow a_q)\) and
\(a(a_r \rightarrow a_q)\) interchangeably with symbols
\({\overline{a}}^{\,q - r}\) and
\({\underline{a}}^{q-r}\), respectively.
Since below we consider V-shaped sequences in which the positions of some elements are distinguished, now we introduce two new terms.
From Definition
2, it follows that cyclic shifts of a V-shaped sequence
a lead to sequences
\(a(a_r\leftarrow a_q)\) and
\(a(a_r\rightarrow a_q)\) which are V-shaped as well, whenever
r and
q are
m-conjugated to each other. Notice also that indices
r and
q need not be mutually
m-conjugated.
The behaviour of criterion \(\Vert \cdot \Vert _1\) for such cyclic shifts can be determined by means of some formulae. Before we present the formulae, we introduce two functions of sequence a.
The next result shows that for fixed indices
r and
q the sequences of functions
\(\Delta _{k,q}(a)\) and
\(\nabla _{k,r}(a)\) are monotonic. We omit the proof of the result, since it follows directly from Definition
3.
The last result in this section concerns differences \(\Vert C({\overline{a}}^{q{-}r})\Vert _{1}-\Vert C(a)\Vert _{1}\) and \(\Vert C({\underline{a}}^{q-r})\Vert _{1}-\Vert C(a)\Vert _{1}\).
5 Comparison of necessary conditions
In this section, we estimate the power of the first and the second necessary condition of schedule optimality for problem (P), comparing the cardinalities of the sets of schedules which satisfy the respective conditions.
Given an instance
\(a^{\circ }\) of problem (
P), let
\(V_\mathrm{I}(a^{\circ })\) and
\(V_\mathrm{II}(a^{\circ })\) denote the sets of all
\(a\in {{\mathcal {P}}} (a^{\circ })\) that satisfy the first and the second necessary condition, respectively. Definitions of
\({{\mathcal {P}}}(a^{\circ })\),
\(V_\mathrm{I}(a^{\circ })\) and
\(V_\mathrm{II}(a^{\circ })\) imply that
$$\begin{aligned} V_\mathrm{II}(a^{\circ })\subseteq V_\mathrm{I}(a^{\circ }) \subset {{\mathcal {P}}} (a^{\circ }). \end{aligned}$$
(19)
In view of (
19), we have
$$\begin{aligned} |V_\mathrm{II}(a^{\circ })|\le |V_\mathrm{I}(a^{\circ })|<|{{\mathcal {P}}} (a^{\circ })|, \end{aligned}$$
where
\(|{{\mathcal {P}}}(a^{\circ })|=n!\) and
\(|V_\mathrm{I}(a^{\circ })|=2^{n-1}.\)
Denote
$$\begin{aligned} u=\min \left\{ a_{i}^{\circ }:i=1,2,\ldots ,n\right\} \end{aligned}$$
(20)
and
$$\begin{aligned} v=\max \left\{ a_{i}^{\circ }:i=1,2,\ldots ,n\right\} . \end{aligned}$$
(21)
Notice that
\(1<u<v\). Denote
$$\begin{aligned} d_{n}=n\times \frac{\log u}{\log u+\log v} \end{aligned}$$
(22)
and
$$\begin{aligned} g_{n}=1+n\times \frac{\log v}{\log u+\log v}. \end{aligned}$$
(23)
5.1 Estimations of the position of \(a_m\)
In order to calculate the cardinalities of the sets of schedules that satisfy the necessary conditions discussed earlier, we have to estimate the range of possible positions of the minimal element \(a_m\) in a V-shaped sequence. Before we describe this range, we make two observations.
First, notice that the range of possible values of index m, \(1<m<n\), of the minimal element \(a_{m}\) in \(a=(a_{1},\ldots ,a_{m},\ldots ,a_{n})\in V_\mathrm{II}(a^{\circ })\) depends on a. Second, observe that if the maximal element and the minimal element in a are close to each other, then, roughly speaking, \(a_{m}\) is near the middle of a. On the other hand, if the difference between the maximal element and the minimal element in a is large enough, then the minimal element \(a_{m}\) satisfying the new necessary condition may be located anywhere in a.
5.2 Estimations of \(|V_\mathrm{II}(a^{\circ })|\)
Theorem
3 implies that the set of possible values of
m is contained in the open interval
\((d_n,g_n)\), where
\(d_n < g_n.\) The cardinality of the set
$$\begin{aligned} D=\left\{ k \in {\mathbb {N}}: d_n< k< g_n, 1< k < n\right\} , \end{aligned}$$
where
\({\mathbb {N}}\) denotes the set of natural numbers, is majorized by
\(\left\lceil g_n \right\rceil - \left\lfloor d_n \right\rfloor - 1\) (cf. Graham et al.
1989, p. 74).
Let
\(V_{D}(a^{\circ })\) denote the set of all
\(a=(a_{1},\ldots ,a_{m},\ldots ,a_{n})\in {{\mathcal {P}}} (a^{\circ })\) such that
a is V-shaped and
\(m\in D\). It is clear that
$$\begin{aligned} V_\mathrm{II}(a^{\circ }) \subseteq V_{D}(a^{\circ })\subseteq V_\mathrm{I}(a^{\circ }) \end{aligned}$$
and that
$$\begin{aligned} |V_\mathrm{II}(a^{\circ })|\le |V_{D}(a^{\circ })| \le |V_\mathrm{I}(a^{\circ })|. \end{aligned}$$
Hence, we can estimate the cardinality of the set
\(V_\mathrm{II}(a^{\circ })\) by the cardinality of the set
\(V_{D}(a^{\circ })\) which, in view of Property
3, is estimated by
\(|V_\mathrm{I}(a^{\circ })| = 2^{n-1}\).
In order to find
\(|V_{D}(a^{\circ })|\), we need to know how to generate all V-shaped sequences from a given sequence
\(a^{\circ }\) with minimal element
\(a_m\), where index
\(m \in D.\) These sequences can be generated as follows. First, we order
\(a^{\circ }\) non-increasingly. Next, for each
\(k \in D\), we construct a V-shaped sequence by choosing
k elements of
\(a^{\circ }\) which compose the left branch of the sequence and, in reversed order,
\(n-k\) remaining elements which compose the right branch of this sequence. However, proceeding in this way, we take into account each V-shaped sequence twice, since the minimal element first is assigned to the left and then to the right branch of the sequence. Hence, since we can choose
k elements from
n in
\(\left( {\begin{array}{c}n\\ k\end{array}}\right) \) ways and since each V-shaped sequence is counted twice, the cardinality of the set
\(V_{D}(a^{\circ })\) equals
$$\begin{aligned} |V_{D}(a^{\circ })|=\frac{1}{2} \sum _{k \in D} \left( {\begin{array}{c}n\\ k\end{array}}\right) . \end{aligned}$$
(27)
Now, applying Eq. (
27), we prove the first main result of the section, which gives a lower and an upper bound of
\(|V_{D}(a^{\circ })|\) in terms of
u,
v and
n.
From Theorem
4 follow a few corollaries which are important for practice. First, this theorem gives a good lower estimation of
\(|V_{D}(a^{\circ })|\) and, as a side effect, an upper estimation of
\(|V_{D}(a^{\circ })|\). The latter, in turn, leads to an upper estimation of
\(|V_\mathrm{II}(a^{\circ })|\). However, if for a given sequence
a we have
\(v\le u^{\frac{n+1}{n-1}},\) where
u and
v are defined by (
20) and (
21), respectively, then
$$\begin{aligned} |V_\mathrm{II}(a^{\circ })|\; \le \; 3\;{\sqrt{\frac{2}{\pi n}}} \left( 1+O\left( \frac{1}{n}\right) \right) \times |V_\mathrm{I}(a^{\circ })|. \end{aligned}$$
The latter inequality implies that if
\(u < v\le u^{\frac{n+1}{n-1}},\) then the number of sequences satisfying the second necessary condition of optimality for problem (
P) is reduced by the factor
\(O(n^{-\frac{1}{2}}).\)
Second, if
u and
v are defined by (
20) and (
21), respectively, and
\(v\searrow u\), then
\(d_{n}\nearrow \frac{n}{2}\le m\le 1+ \frac{n}{2}\swarrow g_{n}\) simultaneously. This means that if
v is close to
u, then we can expect that the cardinality of the set
D becomes smaller, so the set
\(V_{D}(a^{\circ })\), and hence the set
\(V_\mathrm{II}(a^{\circ })\), becomes smaller as well. In other words, if elements of a given sequence
\(a^{\circ }\) are close each to other, then the set of all V-shaped sequences satisfying the second necessary condition is smaller, which makes the verification of this condition a more simple task.
Third, if for a given sequence \(a^{\circ }\) we have \(u<< v\), then the set D, and hence the set \(V_{D}(a^{\circ })\), becomes larger and verification of the second necessary condition can be a more expensive task. More formally, if \(1<u<v\) and \(v\rightarrow +\infty ,\) then the set D approaches the set \(\{2,\ldots ,n-1\}\) and, in consequence, \(|V_\mathrm{II}(a^{\circ })|\) may be large, since the set \(V_{D}(a^{\circ })\) can be larger.
Now, applying an asymptotic formula for partial binomial sums (cf. Graham et al.
1989), we prove the second main result of this section, which gives another estimation of
\(|V_\mathrm{II}(a^{\circ })|\) from above.
Let
$$\begin{aligned} H(t) = t \log _2 \frac{1}{t} + \left( 1-t\right) \log _2 \left( \frac{1}{1-t}\right) \end{aligned}$$
denote the
binary entropy function and let
$$\begin{aligned} {\overline{H}}(t) = 1 - H(t), \end{aligned}$$
where
\(t \in \left[ 0,1 \right] \). Notice that
\(0 \le H(t) \le 1\) for
\(0 \le t \le 1\) and that the maximum of the function equals to
\(H(\frac{1}{2})=1.\)
Applying Lemma
3, we can prove the another upper bound of
\(|V_\mathrm{II}(a^{\circ })|\). Let
n be fixed but arbitrary natural number and define
$$\begin{aligned} \alpha = \frac{\log u}{\log u+\log v}&\text{ and }&\beta = \frac{\log v}{\log u+\log v}. \end{aligned}$$
Clearly,
\(\alpha + \beta = 1,\) \(0< \alpha < \frac{1}{2}\) and
\(\frac{1}{2}< \beta < 1.\)
From Theorem
5 follow a few corollaries. Let
\(a^{\circ }\) be a given sequence and let
\(1< u < v\). Then, first,
\(|V_\mathrm{II}(a^{\circ })| < |V_\mathrm{I}(a^{\circ })|\) since
\(0< \Lambda _n(u,v) <1\).
Second, in view of inequality (
30),
\(|V_\mathrm{II}(a^{\circ })|\) is controlled from above by
\(\Lambda _n(u,v)\).
Third, if
v is close to
u, then
\(V_\mathrm{II}(a^{\circ })\) is essentially smaller than
\(V_\mathrm{I}(a^{\circ }).\) Indeed, if
\(v \searrow u\), then
\({\overline{H}}\left( \frac{\log u}{\log u+\log v}\right) \) approaches zero and then
$$\begin{aligned} \Lambda _n(u,v) \nearrow 1 - \frac{1}{\sqrt{n}} \times 2^{O(1)}, \end{aligned}$$
which implies that
\(V_\mathrm{II}(a^{\circ })\) is essentially smaller than
\(V_\mathrm{I}(a^{\circ }).\)
Finally, if
v is large, then it may happen that the set
\(V_\mathrm{II}(a^{\circ })\) approaches the set
\(V_\mathrm{I}(a^{\circ }).\) Indeed, if
\(v \nearrow +\infty \), then
$$\begin{aligned} \Lambda _n(u,v) \searrow 1 - \frac{2^{-n}}{\sqrt{n}} \times 2^{O(1)}, \end{aligned}$$
since
\({\overline{H}}(\frac{\log u}{\log u+\log v}) \nearrow 1.\) Hence,
\(V_\mathrm{II}(a^{\circ })\) can be ‘close’ to
\(V_\mathrm{I}(a^{\circ }).\)
6 Numerical examples
In this section, we illustrate the results of Sect.
5 with a few examples.
The first example shows how large is set
\(V_\mathrm{II}(a^{\circ })\) compared to set
\(V_\mathrm{I}(a^{\circ }),\) when
\(a^{\circ }\) is a regular instance composed of consecutive positive integer numbers. Let
$$\begin{aligned} r_\mathrm{II}(a^{\circ })=100\times \frac{|V_\mathrm{II}(a^{\circ })|}{|V_\mathrm{I}(a^{\circ })|} \end{aligned}$$
denote the ratio of the size of set
\(V_\mathrm{II}(a^{\circ })\) and the size of set
\(V_\mathrm{I}(a^{\circ }).\)
Example
1 shows that set
\(V_\mathrm{II}(a^{\circ })\) for medium size regular instances is a small subset of set
\(V_\mathrm{I}(a^{\circ }).\) The next two examples show that a similar claim may be formulated also for larger regular instances.
The next two examples concern random instances with components from set \(\{1,2,\ldots ,99\}\). Though sets \(V_\mathrm{II}(a^{\circ })\) in the examples are slightly larger compared to those for regular sequences, ratio \(r_\mathrm{II}(a^{\circ })\) is still small.
We complete this section with results of a numerical experiment, in which 220 random instances of size \(n=6,7,\ldots ,16\) were tested. The experiment was conducted using a code implemented in GNU Octave version 4.4.1, running under 64-bit Windows 10 Pro operating system on a computer with Intel Core 1.80 GHz CPU and 16 GB RAM.
Components of all instances were randomly generated from set \(\{1,2,\ldots ,99\}\) without repetition, i.e. in each generated instance no component could be repeated more than once. For a given n, the average ratio \(r_\mathrm{II}(a^{\circ })\) was computed for all instances \(a^{\circ }\) generated in \(k=5\) or \(k=15\) independent runs.
The average computation time for a single instance grown geometrically with a factor about 2, varying between ca. 275 ms for \(n=6\) and ca. 283 s for \(n=16\).
Table
1 presents results for
\(k=5\) and
\(k=15\) runs, symbol
\(r_\mathrm{II}(k)\) denotes the average ratio
\(r_\mathrm{II}(a^{\circ })\) for all instances of a given size generated in
k runs.
Table 1
Average ratios \(r_\mathrm{II}(a^{\circ })\)
6 | 37.50 | 36.67 |
7 | 20.00 | 18.75 |
8 | 31.25 | 30.21 |
9 | 17.19 | 16.56 |
10 | 26.25 | 26.56 |
11 | 14.77 | 15.34 |
12 | 18.44 | 12.51 |
13 | 13.75 | 13.95 |
14 | 20.96 | 18.30 |
15 | 13.64 | 13.10 |
16 | 18.84 | 13.63 |
Examples
1–
5 and Table
1 show that for many instances of problem (
P) the number of schedules satisfying the new condition is significantly smaller compared to the previous necessary condition. Therefore, the claim that the new necessary condition is stronger than the previous one seem to be fully justified.
7 Conclusions
In this paper, we have considered the problem of minimizing the total completion time for a set of independent and linearly deteriorating jobs scheduled on a single machine. First, we proved some results concerning the impact of cyclic shifts of job sequences on the value of the criterion function. Next, based on these results, we proved a new, stronger, necessary condition of schedule optimality for the considered problem, reducing the number of schedules that we must check while looking for an optimal schedule, compared to the previous necessary condition for this problem. Finally, we estimated the size of this reduction, giving new bounds on the cardinality of the set of all possible optimal schedules for the problem.
Our results show that the new necessary condition is stronger than the previous necessary condition, since for many instances of problem (P) the number of schedules satisfying the new condition is significantly smaller compared to the previous one. Therefore, the set of possible optimal solutions of the problem can be narrowed. Hence, the new necessary condition can be used to discard non-promising solutions in exact and sub-optimal algorithms.
Future research may concern the status of time complexity of problem (P) or algorithms that effectively generate schedules satisfying the new necessary condition of optimality for the problem. Another interesting topic for future research is development of sub-optimal algorithms for (P), which start with an initial V-shaped schedule a and applying alternately the cyclic shifts \(a(q \leftarrow r)\) or \(a(q \rightarrow r)\) generate new V-shaped schedules with lower and lower total completion times.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.