Refined conditions for V-shaped optimal sequencing on a single machine to minimize total completion time under combined effects

Since the early 1990s, there has been a considerable interest in enhanced scheduling models in which the processing times of jobs are affected by their locations in the schedule. Mathematically, this is formalized in terms of various time-changing effects. In this paper, we clarify the status of a number of single-machine problems with various time-changing effects.

We consider scheduling problems with changing times in which the jobs of set \(N=\left\{ 1,2,\ldots ,n\right\} \) are to be processed on a single machine. Each job \(j\in N\) is associated with its “normal” processing time \(p_{j}\). It is convenient to think of normal processing times as the time required under normal processing conditions of the machine, which might change during the processing, thereby affecting the actual processing times.

In the literature on scheduling with changing processing times, traditionally there is a distinction between so-called deterioration effects and learning effects. Informally, under a deterioration effect, the later a job is placed in a schedule, the longer it takes to process it. This phenomenon is often found in manufacturing: If a machine loses its initial processing quality, it increases the actual processing times of some later scheduled jobs. Under a learning effect, the opposite is observed: The later a job is scheduled, the shorter its actual processing time is. To illustrate a learning effect, a machine may be thought of as a human operator who gains experience during the process, which leads to a certain processing time reduction.

Consideration of time-changing effects should not be limited to monotone effects only, such as deterioration and learning. For example, if a human operator processes jobs on certain equipment, then during the process that equipment might be subject to wear and tear, i.e., it might deteriorate with time, however, the operator simultaneously gains additional skills by learning from experience. This gives rise to a combined effect which has a non-trivial influence on the actual processing times.

Time-changing effects are represented by explicit formulae for how the actual processing time of a job is affected. There are three main types of so-called pure effects studied in the literature, which in accordance with the recent monograph Strusevich and Rustogi (2017) can be informally classified as follows:

• Positional effects the actual processing time of a job is a function of its normal processing time and the position it takes in a schedule; see a focused survey by Rustogi and Strusevich (2012b) and a discussion in Agnetis et al. (2014);

• Start time-dependent effects the actual processing time of a job is a function of its normal processing time and its start time in a schedule; see the book Gawiejnowicz (2008) which gives a detailed exposition of scheduling models with this effect;

• Cumulative effects the actual processing time of a job depends on its normal processing time and a function of the normal processing times of previously scheduled jobs; see Kuo and Yang (2006a, b), where a similar effect is introduced.

In this paper, we mainly focus on job-independent positional effects and cumulative effects, as well as on their combinations.

If job j is sequenced in position \(\pi (r) \) of permutation \( \pi =\left( \pi (1) ,\pi (2) ,\ldots ,\pi \left( n\right) \right) \), its completion time is denoted either by \(C_{j}\left( \pi \right) \) or by \(C_{\pi \left( r\right) }\), whichever is more convenient. Let \(\Phi \left( \pi \right) \) denote an objective function to be minimized. Popular objective functions include the maximum completion time \(C_{\max }\left( \pi \right) \), also known as the makespan; the sum of the completion times \(F\left( \pi \right) =\sum _{j\in N}C_{j}\), also known as the total completion time; and a more general function \(\xi C_{\max }+\eta \) \(\sum C_{j}\), with nonnegative coefficients \(\xi \) and \(\eta \).

Given a permutation \(\pi =\left( \pi (1) ,\ldots ,\pi \left( n\right) \right) \) of jobs, let the actual processing time of a job \(j=\pi (r) \) scheduled in position r, \(1\le r\le n\), be denoted by \( p_{j}(r) \). It follows that

A job-dependent positional effect is given by

where g(r) is called a (job independent) positional factor. The values \(g(r) ,1\le r\le n,\) form an array of positional factors that is common for all jobs. If array \(g(r) ,1\le r\le n\), is monotone non-decreasing (or non-increasing), then we have a situation of positional deterioration (or of positional learning, respectively). For the most general job-independent positional effect, we make no assumption regarding the monotonicity of array \(g(r) ,1\le r\le n\). It is often assumed that \(g(1) =1\), which guarantees that for a job that is sequenced first, i.e., in position \(r=1\), the actual processing time is equal to its normal time. We denote the single-machine problems of minimizing an objective function \(\Phi \) subject to the effect (2) by \(1\vert p_{j}(r)=p_{j}g(r)\vert \Phi \).

One of the most general variants of a pure cumulative effect defines \( p_{j}(r) \) as

where

is the sum of the normal processing times of the earlier sequenced jobs.

In (3), f is a continuous differentiable function, common to all jobs. In the case of learning, \(f:\left[ 0,+~\infty \right) \rightarrow \left( 0,1\right] \) is a non-increasing function, while in the case of deterioration, \(f:\left[ 0,+\,\infty \right) \rightarrow \left[ 1,+\,\infty \right) \) is a non-decreasing function.

The actual processing time of job j under an effect that combines a cumulative effect with a general job-independent positional effect is given by

where array g(r) , \(1\le r\le n\), is a monotone sequence that defines a positional effect. It is assumed that in (3) and (4), the equalities \(f\left( 0\right) =1\) and \(g(1) =1\) hold, which guarantee that for the job which is the first in the processing sequence, the actual processing time is equal to its normal time.

We denote the single-machine problems of minimizing an objective function \( \Phi \) subject to the effects (3) and (4) by \(1\vert p_{j}(r)=p_{j}f(P_{r})\vert \Phi \) and \(1\vert p_{j}(r) =p_{j}f(P_{r}) g(r) \vert \Phi \), respectively.

Quite often a permutation of jobs that defines an optimal schedule is found by applying a priority rule, i.e., by sorting the jobs in accordance with certain priorities. The most popular rules are the LPT and SPT rules. Recall that if the jobs are numbered in accordance with the Shortest Processing Time (SPT) rule then

while if they are numbered in accordance with the Longest Processing Time (LPT) rule, then

A permutation of jobs \(\pi =\left( \pi (1) ,\pi \left( 2\right) ,\ldots ,\pi \left( n\right) \right) \) is called V-shaped with respect to \(p_{j}\) if it is either monotone (non-decreasing or non-increasing) or consists of a non-increasing subsequence followed by a non-decreasing subsequence. Often an optimal permutation belongs to the class of V-shaped sequences, and it is quite common to see the term “V-shaped” in the title of papers; see, e.g., Mosheiov (1991). One of the main reasons for interest in V-shaped sequences is that their number is \(2^{n-1}\), which, while still exponential with respect to the number of jobs, is much less than n!.

This paper is organized as follows. In Sect. 2, we consider the problems \(1\vert p_{j}(r)=p_{j}g(r)\vert \Phi \) with a pure positional effect, where \(\Phi \in \{ C_{\max },\sum C_{j},\xi C_{\max }+\eta \sum C_{j}\} \). Reviewing this well-studied class of problems, we stress that some of the problems \( 1\vert p_{j}(r) =p_{j}g(r)\vert \sum C_{j}\) with a positional deterioration effect cannot be solved by a priority rule. Traditionally, in scheduling with variable processing times, if a solution algorithm is not known, “the second best thing” would be to establish some property of an optimal sequence, e.g., the V-shapeness. We describe the refined procedure that may convert a given permutation to a V-shaped permutation without increasing the value of the function. We give conditions when such a procedure leads to an optimal V-shaped sequence. We show that these conditions hold if g is a concave function of r, a polynomial function \( g(r) =r^{a}\), \(a>0\), and an exponential function \(g(r) =\gamma ^{r-1}\), \(\gamma >1\). On the other hand, the established conditions need not hold for a convex function g(r) .

In Sect. 3, we review the problems \(1\vert p_{j}(r) =p_{j}f(P_{r}) g(r) \vert \Phi \) with a combined effect. While some of these problems accept an optimal sequencing policy based on either the SPT or LPT rule, problem \(1\vert p_{j}(r) =p_{j}f(P_{r}) \vert \sum C_{j}\) with a pure cumulative deterioration effect given by a concave function f, including a polynomial function \(f(P_{r}) =( 1+P_{r})^{A}\), \( 0<A<1\), is not solvable by a priority rule. Refining this result, we show that for this problem, an optimal permutation is not even V-shaped.

In Sect. 4, we look at the problems in which the cumulative effect is normalized, i.e., function f does not just depend on \(P_{r}\), the sum of normal processing times of the jobs sequenced prior to position r, but on the ratio \(P_{r}/P\), where P is the sum of all processing times. By contrast with problem \(1\vert p_{j}(r) =p_{j}f(P_{r})\vert \sum C_{j}\) with a non-normalized deterioration effect given by a concave function f, problem \(1\vert p_{j}(r) =p_{j}f(P_{r}/P) \vert \sum C_{j}\) with a normalized cumulative effect is solvable by the SPT rule under certain conditions which, for example, hold for polynomial functions f. For problem \(1\vert p_{j}(r) =p_{j}f(P_{r}/P) g(r)\vert \sum C_{j}\), we establish conditions for an optimal permutation to be V-shaped. Although the conditions hold for a wide range of problems, they do not hold for the model in which both functions f and g are polynomial. The latter problem has been studied by Lu et al. (2015), where relying on a wrong proof technique, the authors claim that the problem admits an optimal V-shaped sequencing policy.

Section 5 contains concluding remarks. In particular, we emphasis that if our refined technique for proving the V-shapeness of an optimal permutation fails for some problems that does not mean that such problems do not admit an optimal V-shaped sequencing policy. It only implies that more advanced methods have to be used for proving or disproving the V-shapeness of an optimal permutation.

In this section, we consider a range of problems \(1\vert p_{j}(r) =p_{j}g(r) \vert \Phi \) with a pure positional effect (2) to minimize a function \(\Phi \in \{ C_{\max },\sum C_{j},\xi C_{\max }+\eta \sum C_{j}\} .\)

In the general case, array g(r), \(1\le r\le n\), does not have to be monotone. However, we pay special attention to the positional learning effect defined by

and the positional deterioration effect

Informal illustrative examples of positional effects are given, e.g., in Rustogi and Strusevich (2012b). Consider a situation in which in a manufacturing shop, there are several parts that need a hole of the same diameter to be punched through by a pneumatic punching unit. Ideally, the time that is required for such an operation depends on the thickness of the metal to be punched through, and this will determine normal processing times for all parts. In reality, however, an unavoidable gas leakage occurs after each punch, due to which the punching unit loses pressure, so that a positional deterioration effect is observed.

We start with a brief review of the results on problem \(1\vert p_{j}(r) =p_{j}g(r) \vert \Phi \). A systematic exposition of the relevant material is contained in Chapter 7 of the monograph Strusevich and Rustogi (2017). Then, we focus on problem \(1\vert p_{j}(r) =p_{j}g(r)\vert \sum C_{j}\), which under an arbitrary deterioration effect does not admit solution by a priority rule. We derive conditions on the positional factors g(r) , \(1\le r\le n\), which guarantee that an optimal permutation is V-shaped.

2.1 Polynomial-time algorithms: a review

Most of the problems related to \(1\vert p_{j}(r) =p_{j}g(r)\vert \Phi \) can be solved in polynomial time by reducing them to the classical problem of minimizing a linear form over permutations. For completeness, we present the latter problem and an algorithm for its solution below.

Given two arrays \({\mathbf {a}}=\left( a_{1},a_{2},\ldots ,a_{n}\right) \) and \({\mathbf {b}}=\left( b_{1},b_{2},\ldots ,b_{n}\right) \) such that

holds, then for a permutation \(\pi =(\pi (1),\pi (2),\ldots ,\pi (n)),\) a linear form is defined by

In order to minimize the linear form (10), we need to find a permutation \(\varphi =(\varphi (1),\varphi (2),\ldots ,\varphi (n))\) of the components of array \({\mathbf {a}}\) such that the inequality

holds for any permutation \(\pi \). The classical result established in Hardy et al. (1934) asserts that an optimal permutation \(\varphi \) can be found by the following algorithm.

Algorithm Match

Input: Two (unsorted) arrays \({\mathbf {a}}=\left( a_{1},a_{2},\ldots ,a_{n}\right) \) and \({\mathbf {b}}=\left( b_{1},b_{2},\ldots ,b_{n}\right) \)

Output: A permutation \(\varphi =(\varphi (1),\varphi (2),\ldots ,\varphi (n))\) that satisfies (11)

• Step 1. If required, renumber the components of array \({\mathbf {b}}\) so that (9) holds.

• Step 2. Output a permutation \(\varphi \) such that

  $$\begin{aligned} a_{\varphi (1) }\le a_{\varphi (2) }\le \cdots \le a_{\varphi \left( n\right) } \end{aligned}$$

  (12)

  holds.

Algorithm Match requires \(O\left( n\log n\right) \) time. Simple as it is, the algorithm still plays an important role in optimization over permutations, including scheduling applications discussed in this paper. Methodologically, it is also quite important, since one of the proofs of its correctness given in Hardy et al. (1934) is based on the so-called pairwise interchange argument, which has become a popular proof technique, its variants being used in this paper.

For \(\Phi \in \{ C_{\max },\sum C_{j},\xi C_{\max }+\eta \sum C_{j}\} \), problems that we denote by \(1\vert p_{j}(r) =p_{j}g(r) \vert \Phi \) reduce to minimizing a linear form that can be generically written as

where the values W(r) are positional weights that depend only on the position r, \(1\le r\le n\), of a job in sequence \(\pi .\) A permutation that minimizes function \(\Phi (\pi ) \) of the form (13) over all permutations of jobs of set N can be found by Algorithm Match which requires \(O(n\log n) \) time. It follows from the structure of Algorithm Match that:

• if the sequence \(W(r) ,1\le r\le n\), of positional weights is not monotone, then an optimal permutation can be found by matching smaller components of the array of the positional weights to larger components of the other array of processing times;

• if the sequence W(r) , \(1\le r\le n\), of positional weights is monotone non-decreasing, then an optimal permutation can be found by ordering the jobs in accordance with the LPT priority rule applied to the normal processing times \(p_{j}\);

• if the sequence W(r) , \(1\le r\le n\), of positional weights is monotone non-increasing, then an optimal permutation can be found by ordering the jobs in accordance with the SPT priority rule applied to the normal processing times \(p_{j}\).

Surprisingly, the fact that problem \(1\vert p_{j}(r) =p_{j}g(r)\vert \Phi \) for an arbitrary array g(r) ,  \(1\le r\le n\), of positional factors is solvable in \(O(n\log n) \) time was established only in the critical review by Rustogi and Strusevich (2012b). Research on scheduling problems with job-independent positional effects conducted before Rustogi and Strusevich (2012b) had had several limitations. First, authors focused on monotone effects only, such as learning and deterioration; moreover, these two types of effects were considered separately despite their similarities. Second, assumptions on the exact shape of positional factors were made (i.e., polynomial or exponential), despite the fact that many results would hold for an arbitrary array of positional factors. Third, the choice of solution approaches included only simple priority rules, such as the LPT and/or the SPT rules, while the possible use of Algorithm Match was neglected.

For problem \(1\vert p_{j}(r) =p_{j}g(r)\vert C_{\max }\), the makespan can be written as

which satisfies (13) with \(W(r)=g(r),~1\le r\le n\), and \( \Gamma =0\). The following statement from Rustogi and Strusevich (2012b) summarizes the status of problem \(1\vert p_{j}(r) =p_{j}g(r)\vert C_{\max }.\)

Theorem 1

Problem \(1\vert p_{j}(r) =p_{j}g(r)\vert C_{\max }\) under a general positional effect (2) reduces to minimizing a linear form (13) with \(W(r)=g(r),~1\le r\le n\), and \(\Gamma =0\), and is solvable in \( O(n\log n) \) time by Algorithm Match. In the case of a learning effect (7), an optimal permutation is obtained in \(O(n\log n)\) time by renumbering the jobs in the SPT order. In the case of a deterioration effect (8), an optimal permutation is obtained in \(O(n\log n) \) time by renumbering the jobs in the LPT order.

For an effect given by a general array \(g(r),~1\le r\le n\), Theorem 1 is proved in Rustogi and Strusevich (2012b). For special cases of the general position deterioration effect, optimality of the LPT rule has been established for the polynomial deterioration effect defined by the positional factors

in Mosheiov (2005) and for the exponential deterioration effect defined by the factors

in Gordon et al. (2008). Similarly, optimality of the SPT rule has been established for the polynomial learning effect defined by the positional factors

in Mosheiov (2001) and for the exponential learning effect defined by the factors

by Gordon et al. (2008).

For problem \(1\vert p_{j}(r)=p_{j}g(r)\vert \sum C_{j}\), it follows from (1) that the objective function can be written as

which satisfies (13) with \(W(r)=( n-r+1) g(r),~1\le r\le n\). Thus, an optimal schedule can be found by Algorithm Match, and this will take \(O(n\log n)\) time; see Rustogi and Strusevich (2012a, b). Surprisingly, for problem \(1\vert p_{j}(r)=p_{j}g(r)\vert \sum C_{j}\) with a deterioration effect (8), no polynomial algorithm faster than \(O(n^{3}) \) time, via a reduction to a full form linear assignment problem, had been known prior to Rustogi and Strusevich (2012a, b).

For problem \(1\vert p_{j}(r)=p_{j}g(r)\vert \sum C_{j}\), if the factors g(r), \(1\le r\le n\), are non-increasing, i.e., satisfy (7), then we have a learning effect. In this case, for any r, \( 1\le r\le n-1\), we have that \(g(r)\ge g(r+1)\) and \(n-r+1>n-(r+1)+1\), so that

and an optimal solution is achieved by renumbering the jobs in the SPT order.

Factors g(r), \(1\le r\le n\), that satisfy (8) define a deterioration effect. Since for any r, \(1\le r\le n-1\), we have that \( g(r)\le g(r+1)\) but \(n-r+1>n-\left( r+1\right) +1\), we cannot guarantee that the positional weights W(r),  \(1\le r\le n\), form a monotone sequence. Thus, there is no evidence that a solution to problem \(1\vert p_{j}(r)=p_{j}g(r)\vert \sum C_{j}\) with a deterioration effect can be obtained by a priority rule.

It is straightforward to verify that problem \(1\vert p_{j}(r) =p_{j}g(r) \vert \xi C_{\max }+\eta \sum C_{j}\) reduces to minimizing the linear form (13) with the positional weights \(W(r)=(\xi +(n-r+1)\eta ) g(r),~1\le r\le n\). Similarly to the problem of minimizing total completion time, here in the case of a positional learning effect (7), the sequence W(r), \(1\le r\le n\), is non-increasing, so that the solution can be found by the SPT rule. Otherwise, unless \(\eta =0\), the sequence of positional weights need not be monotone, so that an optimal solution can be found by Algorithm Match, but not by a priority rule.

The following statement summarizes the status of problems \(1\vert p_{j}(r) =p_{j}g(r)\vert \sum C_{j}\) and \( 1\vert p_{j}(r) =p_{j}g_{j}(r)\vert \xi C_{\max }+\eta \sum C_{j}\).

Theorem 2

Under a general positional effect (2), problems \(1\vert p_{j}(r) =p_{j}g(r)\vert \sum C_{j}\) and \(1\vert p_{j}(r)=p_{j}g_{j}(r)\vert \xi C_{\max }+\eta \sum C_{j}\) reduce to minimizing a linear form (13) with \(\Gamma =0\) and with \( W(r)=(n-r+1) g(r),~1\le r\le n\), and \(W(r)=(\xi +( n-r+1) \eta ) g(r),~1\le r\le n\), respectively. Both problems are solvable in \(O( n\log n) \) time by Algorithm Match. In the case of a learning effect (7), for each of these problems, an optimal permutation is obtained in \(O(n\log n)\) time by renumbering the jobs in the SPT order. In the case of a deterioration effect (8), both problems do not admit a priority rule solution for an arbitrary non-decreasing array g(r) , \(1\le r\le n\), of job-independent positional factors, unless \(\eta =0\).

Problem \(1\vert p_{j}(r) =p_{j}g(r)\vert \sum C_{j}\) can be solved by a priority rule under additional assumptions regarding positional factors g(r) , \(1\le r\le n\), that define a deterioration effect. In particular, it is proved in Gordon et al. (2008) that problem \(1\left| p_{j}(r) =p_{j}g(r) \right| \sum C_{j}\) under an exponential positional deterioration effect (15) is solvable by the LPT rule if \(\gamma \ge 2\), while no priority rule solution exists for this problem if \(1<\gamma <2\). For problem \(1\vert p_{j}(r) =p_{j}g(r)\vert \sum C_{j}\) under a polynomial deterioration effect given by (14), the conditions on A that guarantee that the problem can be solved either by the SPT rule or by the LPT rule are given in Chapter 7.2.2 of the monograph Strusevich and Rustogi (2017).

We summarize the results on the solution algorithms for problems \( 1\vert p_{j}(r) =p_{j}g(r)\vert \Phi \) with \(\Phi \in \{ C_{\max },\sum C_{j},\xi C_{\max }+\eta \sum C_{j}\} \) in Table 1.

2.2 V-shapeness

In this section, we study problem \(1\vert p_{j}(r)=p_{j}g(r)\vert \sum C_{j}\), provided that array g(r) , \(1\le r\le n\), is non-decreasing, i.e., satisfies (8) and defines a deterioration effect. We derive conditions on g(r) which guarantee that for problem \(1\vert p_{j}(r) =p_{j}g(r)\vert \sum C_{j}\), there exists a V-shaped optimal permutation.

Recall that a V-shaped permutation consists of an LPT subsequence of jobs followed by an SPT subsequence of the remaining jobs; one of these subsequences may be empty.

Given a permutation \(\pi =(\pi (1),\pi (2),\ldots ,\pi (n))\), we say that \( \pi \) exhibits a peak in position r if there are three consecutive positions \(r-1\), r and \(r+1\), \(2\le r\le n-1\), for which

holds. It is clear that such a structure is incompatible with the V-shaped property. Below we present a generic procedure for a possible removal of the peak at this position, without increasing the value of the corresponding objective function.

Procedure Peak(r)

Given an instance of the problem of minimizing an objective function \(\Phi \left( \pi \right) \) and a permutation \(\pi \) that exhibits a peak (19) in position r, \(2\le r\le n-1\).

• Step 1. Compute \(G(\pi ) ,\) the joint contribution of the jobs \(\pi (r-1) \), \(\pi (r) \) and \(\pi (r+1) \) to the objective function \(F(\pi ).\)

• Step 2. Create permutations \(\pi ^{\prime }\) and \(\pi ^{\prime \prime }\) obtained from \(\pi \) by interchanging job \(\pi (r) \) with the adjacent jobs, i.e., with \(\pi (r-1) \) and \(\pi (r+1) \), respectively. Compute \(G(\pi ^{\prime }) \) and \( G(\pi ^{\prime \prime })\).

• Step 3. If

  $$\begin{aligned} G(\pi ) \ge \min \{ G(\pi ^{\prime }), G(\pi ^{\prime \prime })\}, \end{aligned}$$

  (20)

  then either \(\pi ^{\prime }\) or \(\pi ^{\prime \prime }\) is a permutation with a value of the objective function that is at most \(\Phi (\pi ) \) and which does not have a peak in position r.

This peak-removing procedure can be reapplied until either a V-shaped permutation is obtained or a peak cannot be removed by applying this procedure.

The following lemma is based on the application of Procedure Peak to problem \(1\vert p_{j}(r) =p_{j}g(r)\vert \sum C_{j}\). It follows from (18) that

Lemma 1

For problem \(1\vert p_{j}(r) =p_{j}g(r)\vert \sum C_{j}\), let permutation \(\pi =(\pi (1),\ldots ,\pi ( r-1) ,\pi (r) ,\pi (r+1),\ldots ,\pi (n))\) be such that for some r, \(2\le r\le n-1\), (19) holds. Let \(\pi ^{\prime }=((\pi (1),\ldots ,\pi (r) ,\pi ( r-1) ,\pi (r+1),\ldots ,\pi (n))\) and \(\pi ^{\prime \prime }=((\pi (1),\ldots ,\pi (r-1) ,\pi (r+1),\pi (r) ,\ldots ,\pi (n))\) be two permutations obtained from \(\pi \) by interchanging job \(\pi (r) \) with one of its adjacent jobs, respectively. Then, if either

or

holds, then (20) holds.

Proof

For permutation \(\pi ^{\prime }\), the contribution of the three jobs \(\pi (r-1) ,\pi (r) \) and \(\pi (r+1) \) to the objective function can be written as

Compute

Since \(p_{\pi (r) }>p_{\pi ( r-1) }\), it follows that \(\Delta ^{\prime }\le 0\) if condition (22) holds.

Similarly, for permutation \(\pi ^{\prime \prime }\), we have that

so that

Since \(p_{\pi (r) }>p_{\pi \left( r+1\right) }\), it follows that \(\Delta ^{\prime \prime }\le 0\) if condition (23) holds. \(\square \)

Lemma 1 implies that for problem \(1\vert p_{j}(r) =p_{j}g(r)\vert \sum C_{j}\), there exists a V-shaped optimal permutation for fairly general types of deterioration effects.

Theorem 3

For problem \(1\vert p_{j}(r) =p_{j}g(r)\vert \sum C_{j}\) there exists a V-shaped optimal permutation, provided that one of the following holds:

1. (a)

   Function g(r) is concave non-decreasing;

2. (b)

   Function g(r) is exponential non-decreasing, i.e., satisfies (15);

3. (c)

   Function g(r) is polynomial non-decreasing, i.e., satisfies (14).

Proof

To prove the theorem, we show that for each type of positional effect (a)–(c), the conditions of Lemma 1 hold. Notice that \(\left( n-r+1\right) ^{2}-\left( n-r+2\right) \left( n-r\right) =1\), so that

holds for all r, \(2\le r\le n-1\). We have that either (22) holds or, if it does not but

then

i.e., (23) holds. Thus, to prove the theorem, we show that in each case (a)–(c), inequality (25) holds.

Case (a) If function g(r) is concave non-decreasing, then

For positive W and x, suppose that \(g\left( r-1\right) =W\) and \(g(r) =W+x\). Then, due to concavity of function g, we have that \(g\left( r+1\right) \le W+2x\), so that

i.e., (25) holds.

Case (b) In this case, it follows from (15) that

and (25) obviously holds, as equality.

Case (c) In this case, applying (14) with \(A>0\), we have that

and (25) again holds. \(\square \)

Notice that the statement regarding Case (c) of Theorem 3 is given in Mosheiov (2005). The proof there is based on a peak-removing process, similar to Procedure Peak(r); however, for the three jobs \(\pi ( r-1) ,\pi (r) \) and \(\pi ( r+1) \) such that (19) holds, the contributions to the objective function are not defined correctly. Indeed, in Mosheiov (2005), it is assumed that if the jobs \( \pi ( r-1) ,\pi (r) \) and \(\pi \left( r+1\right) \) are processed in this order, then their actual processing times contribute to the objective function three times, two times and one time, respectively. However, the contributions of actual processing times should be computed with respect to the positions of the jobs from the rear of the schedule, as done in the corrected expression (21).

We conclude this section by demonstrating that Theorem 3 does not hold for convex non-decreasing functions g(r) .

Example 1

Consider the following instance of problem \(1\vert p_{j}\) \((r) =p_{j}g(r) \vert \sum C_{j}\) with three jobs

The deterioration positional effect is defined by a convex function \(g(r) =0.6r^{2}-1.4r+1.8\), so that \(g(1) =1,\) \(g(2) =1.4\) and \(g(3) =3\). The results of full enumeration are presented in Table 2. We see that neither of the two optimal permutations (1, 3, 2) and (2, 3, 1) is V-shaped.

In this section, we turn to single-machine problems of minimizing an objective function \(\Phi \) subject to the effects (3) and (4), i.e., to problems \(1\vert p_{j}(r) =p_{j}f( P_{r}) \vert \Phi \) and \(1\vert p_{j}(r) =p_{j}f( P_{r})g(r) \vert \Phi \), respectively. One of the first versions of a pure cumulative effect, a polynomial cumulative effect, given by

was introduced by Kuo and Yang (2006a, b), who studied that effect in the learning form, with \(A<0\). Studies on an effect similar to (4) were initiated in Wu and Lee (2008), also in the learning form. Chapter 10 of the monograph Strusevich and Rustogi (2017) presents a detailed discussion of problems \(1\vert p_{j}(r) =p_{j}f( P_{r}) g(r)\vert \Phi \) and\(\ 1\vert p_{j}(r) =p_{j}f(P_{r})\vert \Phi \). In particular, the following statement gives conditions under which problem \( 1\vert p_{j}(r) =p_{j}f( P_{r}) g(r)\vert \Phi \) is solvable by the SPT rule.

Theorem 4

For problem \(1\vert p_{j}(r) =p_{j}f(P_{r}) g(r) \vert \Phi \) with \(\Phi \in \{ C_{\max },\sum C_{j},\xi C_{\max }+\eta \sum C_{j}\} \) under an effect (4), an optimal permutation can be found in \(O(n\log n) \) time by sorting the jobs in accordance with the SPT rule, provided that f is convex on \([0,+\,\infty ) \) and array g(r) , \(1\le r\le n\), is non-increasing.

The conditions of Theorem 4 imply that array g(r) , \(1\le r\le n\), defines a positional learning effect. If function f is defined by (26), then it is convex if either \( A<0\) (learning) or \(A>1\) (fast deterioration). We exclude from consideration the case that \(A=0\), since no cumulative effect takes place.

The case of a combined effect (4), provided that function f is concave and the array g(r) , \(1\le r\le n\), is non-decreasing, is not fully symmetric to that presented in Theorem 4, and only the makespan \(C_{\max }\) can be minimized by a priority rule, this time LPT.

Theorem 5

For problem \(1\vert p_{j}(r) =p_{j}f(P_{r}) g(r) \vert C_{\max }\) under an effect (4), an optimal permutation can be found in \(O(n\log n) \) time by sorting the jobs in accordance with the LPT rule, provided that function f is concave on \([0,+\,\infty ) \) and the array g(r) , \(1\le r\le n\), is non-decreasing.

The conditions of Theorem 5 imply that array g(r) , \(1\le r\le n\), defines a positional deterioration effect. If function f is defined by (26), then it is concave if \(0<A\le 1\) (slow deterioration).

The results presented in Strusevich and Rustogi (2017) are summarized in Table 3, including their implication for a polynomial cumulative effect (26). Here, in the second column, we use symbols \(\nearrow \) and \(\searrow \) to indicate whether the sequence g(r) ,  \(1\le r\le n,\) is non-decreasing or non-increasing, respectively. Additionally, we write \(g=1\) if \(g(r) =1,\) \(1\le r\le n.\)

It is stressed in Strusevich and Rustogi (2017) that the status of the problem of minimizing total completion time \(\sum C_{j}\) under an effect (4) provided that the conditions of Theorem 5 hold remains open, even if no positional effect is applied, i.e., \(g(r) =1\), \(1\le r\le n\). A counterexample given in Strusevich and Rustogi (2017) shows that for a concave polynomial deterioration effect \(f( P_{r}) =(1+P_{r}) ^{\frac{1}{2}}\), problem \(1\vert p_{j}(r) =p_{j}f( P_{r})\vert \sum C_{j}\) can be solved neither by the SPT nor by the LPT rule. Below, we strengthen that result and show that for the latter problem, an optimal permutation need not be V-shaped.

Example 2

Consider the following instance of problem \(1\vert p_{j}\) \(\left( r\right) =p_{j}f\left( P_{r}\right) \vert \sum C_{j}\)

A polynomial concave cumulative deterioration effect \(f\left( P_{r}\right) =( 1+P_{r})^{\frac{1}{2}}\) applies. The results of full enumeration (accurate to four decimal places) are presented in Table 4. We see that the optimal permutation (2, 3, 1) is not V-shaped.

Define

A cumulative effect given by the function \(f\left( X/P\right) :\left[ 0,P \right] \rightarrow \left[ 0,+\,\infty \right] \) is called normalized. See Wu and Lee (2008); Yin et al. (2009) where the normalized cumulative effects are introduced. The main reason why normalized effects are of interest is due to the fact that a normalized effect provides a slower and smother change in actual processing times. Non-normalized effects often lead to unacceptably high actual processing times (in the case of deterioration) and are seen as unrealistic.

If we set \(y=\frac{X}{P}\), then \(f\left( y\right) :\) \(\left[ 0,1\right] \rightarrow \left[ 0,+\,\infty \right] \) and

4.1 Pure cumulative normalized effect: SPT

We prove that under certain conditions problem \(1\vert p_{j}(r) =p_{j}f( P_{r}/P) \vert \sum C_{j}\) with a pure cumulative deterioration effect defined by a normalized concave function \( f(P_{r}/P) \) can be solved by the SPT rule. The established conditions hold for a popular polynomial normalized concave effect

Our proof is based on several auxiliary statements. One of them is the Lagrange mean value theorem reproduced below.

Theorem 6

If a function f is continuous on a closed interval [a, b] , where \(a<b\), and differentiable on the open interval (a, b), then there exists a point \(\zeta \in \) (a, b) such that

Theorem 6 is used to prove the following lemma.

Lemma 2

For a non-decreasing twice differentiable concave normalized function \(f(X/P) :[ 0,P] \rightarrow [0,+\,\infty ]\) with a non-decreasing second derivative, define the function

where \(B\ge 0\), \(\lambda >1,~0\le t\le P\). Then, the inequality

holds for all \(X\in [ 0,P].\)

Proof

If follows from Theorem 6 that there exists a \(\xi \in \left[ t,\lambda t\right] \) such that

We rewrite

which implies

Applying Theorem 6 again, we deduce that there exists a \(\eta \in \left[ 0,t\right] \) such that

so that we further rewrite

Another application of Theorem 6, this time to the derivative function \(f^{\prime }\), guarantees that there exists a \(\zeta \in \left[ \eta ,\xi \right] \) such that

which leads to

By condition, \(f^{\prime \prime }\) is a non-decreasing function, so that \( 0>f^{\prime \prime }\left( \frac{X+\zeta }{P}\right) \ge f^{\prime \prime }\left( \frac{X}{P}\right) \). Besides, \(\xi -\eta <\lambda t\), so that inequality (29) holds. \(\square \)

Theorem 7

For problem \(1\vert p_{j}(r) =p_{j}f(P_{r}/P) \vert \sum C_{j}\) under a normalized deterioration effect, an optimal permutation can be found in \(O(n\log n) \) time by sorting the jobs in accordance with the SPT rule, provided that function f is concave for \(0\le P_{r}\le P\) with a non-decreasing second-order derivative and for any \(y=\frac{P_{r}}{P}\in [0,1] \), the inequality

holds.

Proof

Suppose that \(\pi =(\pi (1),\ldots ,\pi \left( r-1\right) ,\pi (r),\pi \left( r+1\right) ,\ldots ,\pi (n))\) is an optimal permutation for problem \(1\left| p_{j}(r) =p_{j}f\left( P_{r}/P\right) \right| \sum C_{j}\), and r, \(1\le r\le n-1\), is the latest position (or the first from the rear of \(\pi \)) such that the pair of jobs \(u=\pi (r) \) and \(v=\pi \left( r+1\right) \) breaks the SPT rule, i.e.,

Define

Let \(\pi ^{\prime }\) be the permutation obtained from \(\pi \) by swapping the jobs \(\pi (r)\) and \(\pi (r+1)\). The actual processing times of all other jobs in sequence \(\pi ^{\prime }\) are not affected by the swap of the jobs \(\pi (r)\) and \(\pi (r+1)\).

Denote \(P_{h}=\sum _{i=1}^{h-1}p_{\pi \left( i\right) }\) for \(1\le h\le n\) and define Y as the completion time of the job in the \(\left( r-1\right) \)th position in sequence \(\pi \) (or, equivalently, in \(\pi ^{\prime }\)), i.e., \(Y=\) \(C_{\pi \left( r-1\right) }=C_{\pi ^{\prime }\left( r-1\right) }\) . For \(h=r\), we derive that

Consider the difference \(\Delta \) between the values of the objective functions for these two permutations, i.e.,

Since there are \(n-r\) jobs in each \(\pi \) and \(\pi ^{\prime }\) after the job in the rth position, we have that

To prove the theorem, we show that \(\Delta >0\). Using (31) and the fact that \(\lambda >1\), we write

and

Thus, we may express \(\Delta \) as

For function \(\varphi \) defined by (28), we see that by setting \( B=n-r\) and \(X=P_{r}\), we may write

Applying inequality (29) with \(t=p_{\pi \left( r+1\right) },~\lambda t=p_{\pi (r) },B=n-r,~X=P_{r}\), we obtain

Recall that in permutation \(\pi \) after job \(\pi (r) \), there are \(n-r\) jobs with processing times equal to or larger than \(p_{\pi \left( r+1\right) }.\) Thus, \(P\ge P_{r}+p_{\pi \left( r\right) }+\left( n-r\right) p_{\pi \left( r+1\right) }\), i.e., \(\left( n-r\right) p_{\pi \left( r+1\right) }\le P-p_{\pi \left( r\right) }\). It is clear that the inequality

holds, with the equality achieved for \(p_{\pi (r) }=\frac{P}{2}\) . Since function f is concave, its second-order derivative \(f^{\prime \prime }\) is negative, and we derive

The right-hand side of the above inequality is nonnegative due to property (30), which proves the theorem. \(\square \)

An example of a function that satisfies the conditions of Theorem 7 is a normalized polynomial function (27) with \(0<A<1\). For \(y=P_{r}/P\), we obtain \(f\left( y\right) =\left( 1+y\right) ^{A} \). Notice that \(\frac{\mathrm{d}^{3}}{\mathrm{d}y^{3}}\left( 1+y\right) ^{A}=A\left( A-1\right) \left( A-2\right) \left( y+1\right) ^{A-3}\), i.e., \( f^{\prime \prime }\) is non-decreasing. Moreover, for any \(y\in \left[ 0,1 \right] \), we deduce

since \(4\left( 1+y\right) ^{2}\ge 4\) and \(A\left( A-1\right) \ge -\frac{1}{ 4}\). Thus, the conditions of Theorem 7 are satisfied and this results in the following statement.

Corollary 1

For problem \(1\vert p_{j}(r) =p_{j}f(P_{r}/P)\vert \sum C_{j}\) under a normalized deterioration effect (27) with \(0<A<1\), an optimal permutation can be found in \(O( n\log n) \) time by sorting the jobs in accordance with the SPT rule.

On the other hand, consider a logarithmic function \(f(\frac{x}{P})=\ln \left( e+\frac{10x}{P}\right) \), such that \(f\left( 0\right) =1\). Function f is concave and has a non-decreasing second-order derivative; however, inequality (30) does not hold for all \(y\in (0,0.14623), \) so that Theorem 7 cannot be applied.

Observe a striking impact of the normalized effect: In the case of a polynomial function f, problem \(1\vert p_{j}(r)=p_{j}f( P_{r}/P)\vert \sum C_{j}\) with a normalized deterioration effect is solvable by the SPT rule, while for problem \( 1\vert p_{j}(r) =p_{j}f(P_{r})\vert \sum C_{j}\) with a non-normalized effect, Example 2 demonstrates that an optimal permutation does not have to be V-shaped.

4.2 Combined cumulative normalized effects: V-shapeness

This subsection is aimed at resolving the status of problem \(1\vert p_{j}(r) =p_{j}f( P_{r}/P) g(r)\vert \sum C_{j}\) for a wide range of functions that define the combined effect, including those functions that are considered in Lu et al. (2015). Recall that Lu et al. (2015) address problem \(1\vert p_{j}(r) =p_{j}f(P_{r}/P) g(r)\vert \sum C_{j}\) and claim that for \(f( P_{r}/P) \) given by a normalized polynomial function (27) with \(0<A<1\) and \(g(r) =r^{a}\) for \( a>0\), an optimal permutation is V-shaped. However, the proof technique used in Lu et al. (2015) is based on Mosheiov (2005) and is therefore incorrect. That leaves the status of the problem open.

Notice that it follows from Sect. 2.2 that for problem \( 1\vert p_{j}(r) =p_{j}f(P_{r}/P) g(r)\vert \sum C_{j}\) for an optimal permutation to be V-shaped, the function g(r) that defines the positional effect should satisfy the conditions of Lemma 1. Our proof is split into two parts, depending on which of the two conditions of Lemma 1 holds for position r.

Our proofs are based on applications of Procedure Peak to problem \( 1\vert p_{j}(r) =p_{j}f( P_{r}/P) g(r)\vert \sum C_{j}.\) Also, the proofs are based on the properties of the following function

where \(0\le \frac{X}{P}\le 1.\)

Lemma 3

For function \(\psi (t) \) defined by (32), such that \(\lambda >1\), \(\mu \ge 1\) and function \(f(X/P):[0,P] \rightarrow [0,+\,\infty ]\) is a concave normalized function, the inequality \(\psi (t) \ge 0\) holds for all nonnegative t such that \(X+\lambda t\le P\).

Proof

The proof is similar to the proof of Lemma 9.1 in the book Strusevich and Rustogi (2017). First, notice that

Further, compute

where the last inequality follows from \(\lambda >1\) and the concavity of f, since the derivative of a concave function is non-increasing. Thus, function \(\varphi \left( t\right) \) remains nonnegative for all nonnegative t, and this proves the lemma. \(\square \)

As in Sect. 2.2, assume that a permutation \(\pi =(\pi (1), \pi (2),\ldots ,\pi (n))\) which is optimal for problem \(1\vert p_{j}\) \((r) =p_{j}f\left( P_{r}/P\right) g\left( r\right) \vert \sum C_{j\text { }}\)exhibits a peak in position r, i.e., (19) holds for three consecutive positions \(r-1,r\) and \(r+1\), \(2\le r\le n-1\).

As earlier, for a permutation \(\pi \), let \(P_{h}\) denote the sum of the normal processing times of the jobs that precede job \(\pi \left( h\right) \). Define \(G\left( \pi \right) \) as the total contribution of the three jobs \( \pi \left( r-1\right) ,\pi (r) \) and \(\pi \left( r+1\right) \) to the objective function \(F\left( \pi \right) =\sum _{r=1}^{n}C_{\pi (r) }\), so that

As in Procedure Peak, let \(\pi ^{\prime }\) and \(\pi ^{\prime \prime }\) be two permutations obtained from \(\pi \) by interchanging job \(\pi (r) \) with the adjacent jobs, i.e., with \(\pi \left( r-1\right) \) and \( \pi \left( r+1\right) \), respectively. We demonstrate that under certain conditions, inequality (20) holds, and therefore, the peak in position r of permutation \(\pi \) can be removed.

Lemma 4

For problem \(1\vert p_{j}(r) =p_{j}f(P_{r}/P) g(r) \vert \sum C_{j}\), let a cumulative deterioration effect be defined by a function f that is a concave differentiable non-decreasing normalized function. For a permutation \(\pi =(\pi (1),\ldots ,\pi (r-1)\), \(\pi (r), \pi (r+1) ,\ldots ,\pi (n))\) such that for some r, \(2\le r\le n-1 \), (19) holds, let \(\pi ^{\prime }=((\pi (1), \ldots ,\pi (r)\), \(\pi (r-1), \pi (r+1) ,\ldots ,\pi (n))\) be obtained from \(\pi \) by interchanging jobs \(\pi \left( r-1\right) \) and \(\pi (r). \) Then, inequality (22) implies that \(G(\pi ) \ge G(\pi ^{\prime }) \).

Proof

The total contribution of the three jobs \(\pi \left( r-1\right) ,\pi (r) \) and \(\pi \left( r+1\right) \) to the objective function for permutation \(\pi \) is given by (33), while for permutation \(\pi ^{\prime }\), it can be written as

To prove the lemma, we show that

i.e., permutation \(\pi ^{\prime }\) is no worse than permutation \(\pi \). We have that

Define

Notice that \(\lambda ^{\prime }>1\) due to the definition of position r and \(\mu ^{\prime }\ge 1\) due to (22). Using the introduced notation, we rewrite

It follows from (32) that for \(X=P_{r-1}\), \(\lambda =\lambda ^{\prime }\) and \(\mu =\mu ^{\prime }\), we can express

It follows from Lemma 3 that \(\psi \left( t\right) \ge 0\), which implies that \(\Delta ^{\prime }\ge 0\). \(\square \)

As an illustration, consider problem \(1\vert p_{j}\) \((r) =p_{j}f( P_{r}/P) g(r) \vert \sum C_{j}\) in which function f satisfies the conditions of Lemma 4 and the positional deterioration effect is defined by an exponential function, i.e., \(g\left( r\right) =\gamma ^{r-1}\), where \(\gamma \ge \frac{3 }{2}\). We have that

so that (22) holds due to

Thus, for the problem with the combined effect under consideration, an optimal permutation is V-shaped. The case that \(1<\gamma <\frac{3}{2}\) is left open. We only know that for \(1<\gamma <\frac{3}{2}\), problem \( 1\vert p_{j}(r)=p_{j}\gamma ^{r-1}\vert \sum C_{j}\) with a pure positional deterioration effect is not solvable by a priority rule, but an optimal permutation is V-shaped, as proved in Theorem .

Now, we consider the more intricate case of problem \(1\vert p_{j}(r) =p_{j}f( P_{r}/P) g(r)\vert \sum C_{j} \) assuming function g satisfies condition (23).

The following lemma is an analog of Lemma 2.

Lemma 5

For function \(\psi (t) \) defined by (32), such that \(\lambda <1\), \(\mu \le 1\) and function \(f(X/P) :[0,P] \rightarrow [0,+\,\infty ]\) is a non-decreasing twice differentiable concave normalized function \(f(X/P) :[0,P] \rightarrow [0,+\,\infty ] \) with a non-decreasing second derivative, the inequality

holds for all \(t\ge 0\) such that \(X+t\le P.\)

Proof

The proof is similar to the proof of Lemma 2 and is based on multiple applications of the Lagrange mean value theorem, i.e., Theorem 6.

Substituting

into (32), we obtain

Combining, we rewrite

Applying Theorem 6 to function f, we obtain

where \(\xi \in \left( 0,\lambda t\right) ,\eta \in \left( \lambda t,t\right) \). Applying Theorem 6 to the derivative function \(f^{\prime }\), we further deduce

where \(\xi \in \left( 0,\lambda t\right) ,\eta \in \left( \lambda t,t\right) ,\zeta \in \left( \xi ,\eta \right) \).

Since \(\eta -\xi <\left( 1-\lambda \right) t\) and f is concave, i.e., \( f^{\prime \prime }\) is negative, we have

By condition, \(f^{\prime \prime }\) is non-decreasing, so that \(f^{\prime \prime }\left( \frac{X+\zeta }{P}\right) \ge \) \(f^{\prime \prime }\left( \frac{X}{P}\right) \), and therefore, (34) holds. \(\square \)

Lemma 6

For problem \(1\vert p_{j}(r) =p_{j}f(P_{r}/P) g(r) \vert \sum C_{j}\), let a cumulative deterioration effect be defined by a function f that is a concave twice differentiable non-decreasing normalized function with a non-decreasing second derivative. For a permutation \(\pi =(\pi (1),\ldots ,\pi ( r-1) ,\pi (r) ,\pi ( r+1) ,\ldots ,\pi (n))\) such that for some r, \(2\le r\le n-1\), (19) holds, let \(\pi ^{\prime \prime }=((\pi (1),\ldots ,\pi ( r-1) ,\pi ( r+1) ,\pi (r) ,\ldots ,\pi (n))\) be obtained from \(\pi \) by interchanging jobs \(\pi (r) \) and \(\pi ( r+1) .\) Then, if inequality (23) holds and additionally the inequality

holds for \(y\in [ 0,1] \) and all \(\mu ,\) \(0<\mu \,\le 1\), then \( G(\pi ) \ge G(\pi ^{\prime \prime })\).

Proof

The total contribution of the three jobs \(\pi \left( r-1\right) ,\pi (r) \) and \(\pi \left( r+1\right) \) to the objective function for permutation \(\pi \) is given by (33), while for permutation \(\pi ^{\prime \prime }\), it can be written as

To prove the lemma, we show that

i.e., permutation \(\pi ^{\prime \prime }\) is no worse than permutation \(\pi \) . Since \(P_{r}=P_{r-1}+p_{\pi (r-1)}\) for permutation \(\pi \), we have that

Define

Notice that \(\lambda ^{\prime \prime }<1\) due to the definition of position r and \(\mu ^{\prime \prime }\le 1\) due to (23). Using the introduced notation, we rewrite

In terms of the function \(\psi \left( t\right) ,\) applying (32) with \(X=P_{r},\) \(t=p_{\pi (r)},\) \(\lambda =\lambda ^{\prime \prime }\), \(\mu =\mu ^{\prime \prime }\), we may write

Lemma 5 implies

Notice that \(1-\lambda =\left( p_{\pi (r) }-p_{\pi \left( r+1\right) }\right) /p_{\pi (r) }\) and

Since \(p_{\pi (r) }\le P-p_{\pi \left( r+1\right) }\), we obtain

where the last inequality holds as equality for \(p_{\pi \left( r+1\right) }=P/4\).

Thus, \(\psi \left( p_{\pi (r)}\right) \ge 0\) if

which holds due to (35). This proves the lemma. \(\square \)

We now examine how the derived conditions can be applied to a specific problem.

Consider first problem \(1\vert p_{j}(r)=p_{j}f( P_{r}/P) g(r)\vert \sum C_{j}\), where \(f( P_{r}/P) \) is a normalized polynomial function (27) with \( 0<A<1\) and \(g(r) =r^{a}\) for \(a>0\). As mentioned earlier, Lu et al. (2015) claim that for that problem, an optimal permutation is V-shaped, although no rigorous proof has been given.

Based on Lemmas 4 and 6, we only need to make sure that for \(y=\frac{P_{r}}{P}\), function \(f\left( y\right) =\left( 1+y\right) ^{A}\), \(0<A<1,\) satisfies the conditions of Lemma 6. Notice that \(\frac{\mathrm{d}^{3}}{\mathrm{d}y^{3}}\left( 1+y\right) ^{A}=A\left( A-1\right) \left( A-2\right) \left( y+1\right) ^{A-3}>0\), i.e., \(f^{\prime \prime }\) is non-decreasing. Moreover, for any \( y\in \left[ 0,1\right] \) and any \(\mu \in (0,1]\), we deduce

We know that \(\left( 1+y\right) ^{2}\ge 1\) and \(A\left( A-1\right) \ge - \frac{1}{4}\), i.e., \(\left( 1-\mu \right) f\left( y\right) +\frac{1}{8}\mu f^{\prime \prime }\left( y\right) \ge 0\) if \(\left( 1-\mu \right) \left( 1+y\right) ^{2}-\frac{1}{32}\mu \ge 0\), i.e., \(\mu \le \frac{32}{33}\). This implies that the required inequality (35) holds not for all \(\mu \), \(0\le \mu \le 1\), but only for \(0\le \mu \le \frac{32 }{33}\). In fact, we can produce a counterexample that shows that for an instance of the problem under consideration, a peak in a certain position  r cannot be removed, since neither Lemma 4 nor Lemma  6 can be applied.

Example 3

There are \(n=30\) jobs, such that

The normalized cumulative polynomial deterioration effect is defined by \( f\left( X/P\right) =\sqrt{1+X/P}\), and the positional polynomial deterioration effect is defined by \(g(r) =r^{0.6}\). Consider permutation \(\pi \) in which the longest job 30 is in position 16 and the second longest job 29 is in position 17. Permutations \(\pi ^{\prime }\) and \(\pi ^{\prime \prime }\) are obtained by swapping job 30 either with the preceding job or with the job that follows, i.e., job 29. It can be checked that

i.e., \(G\left( \pi \right) <\min \{ G( \pi ^{\prime }), G( \pi ^{\prime \prime })\} \) and for \(r=16\) Procedure Peak(r) cannot be applied. Notice that for \(r=16\), we have that \(\mu ^{\prime }=0.97451496<1\), i.e., (22) does not hold and Lemma 4 is not applicable. On the other hand,

so that Lemma 6 cannot be applied either.

Notice that this counterexample does not mean that for the described instance, an optimal permutation is not V-shaped. In fact, it can be verified by full enumeration that an optimal solution is delivered by a SPT permutation, e.g., the one that keeps the jobs in the order of their numbering. The example only demonstrates that in general, an optimal permutation cannot be derived by Procedure Peak\(\left( r\right) \) from an arbitrary sequence of jobs, i.e., Procedure Peak(r) may fail for a particular r. We therefore need another technique, different from simple peak removing, to verify whether an optimal permutation is V-shaped or not.

In this paper, we refine the proof technique previously employed for proving the existence of an optimal V-shaped sequencing policy for a range of scheduling problems with various time-changing effects such as positional, cumulative and their combination. The refinement is achieved by presenting a corrected formula for a contribution that an individual job makes to the objective function, typically, the sum of the completion times.

For pure positional effects, we give conditions for an optimal V-shaped policy that hold for the popular polynomial and exponential effects, as well as for non-monotone concave effects. For problems under a combination of a cumulative concave normalized effect and a positional effect, we also derive conditions which hold for a wide range of problems. However, they do not hold for the problem in which both cumulative and positional effects are polynomial, which contradicts the claim made by Lu et al. (2015).

The presented counterexamples show limitations of the discussed proof technique for proving V-shapeness and show the necessity for a more powerful method.