Theoretical Paper

Introduction

Traditional scheduling research assumes that the job values are independent of their start and finish times. However, there are practical situations where job values depend on the starting time of a job. For example, in a simplified version of scheduling movies in a theatre, the revenue generated from screening a movie depends on its starting time as the customer interest in a movie deteriorates with the passage of time (Swami et al, 1999). Even though the length of time for which a specific movie is shown is determined by the contract between the movie theatre and the distributor of the movie, movie scheduling decisions that determine their starting times can affect the total profits. In order to formulate and solve the movie theatre scheduling problem, therefore, we assume that all other decisions (like those discussed by Swami et al, 1999) have already been made. It is desired to find the order in which these n movies should be screened so as to maximize total profit.

Several other practical situations fit the above description including the remanufacturing environment with high-technology product (Fleischmann et al, 1997) and web object transmission (Xia and Tse, 2000). In such situations, it is advantageous to consider scheduling problems where job values deteriorate with job starting times and the objective is to find a schedule that maximizes the cumulative job values. Since there is only one machine (like the movie theatre), we consider the single machine scheduling problem with deteriorating job values to maximize the aggregate value of all jobs. Following the three field notation of the scheduling problems by Lawler et al (1993), we will designate this problem as 1|V_j(t)|maxV_j where V_j(t) is the value of job j if it starts at time t and 'max' is used to make clear that the objective is the maximization of value rather than minimizing cost.

Ignoring the capacity constraint, Fisher and Krieger (1981, 1984) proposed a heuristic algorithm for the nonincreasing concave job deterioration job value function. Their algorithm is based on the piecewise linear approximation and always obtains at least 2/3rd of the optimal cumulative job value. Voutsinas and Pappis (2002) developed a heuristic algorithm for the 1|V_j(t)=w_j(t+p_j)^_j|maxV_j problem. However, the effectiveness of their algorithm to find an optimal solution decreases as the problem size grows. Heuristics developed for minimizing a general cost function by Alidaee (1991, 1993) can be used for solving the 1|V_j(t)|maxV_j problem considered in this paper. Apart from the above developments, the 1|V_j(t)|maxV_j problem has not received much attention in the literature. For example, existing literature does not address the issue of the capacity constrained environment with deteriorating job value functions.

This paper considers the 1|V_j(t)|maxV_j problem with and without capacity constraints and shows that, except for some special cases, the general problem is unary NP-hard. In view of its NP-hard nature, heuristics for various forms of the 1|V_j(t)|maxV_j problem are developed and empirically evaluated.

The rest of the paper is organized as follows. We first deal with the problem formulation and complexity including the identification of polynomially solvable special cases and a dominance-based optimization algorithm. Heuristics to find optimal or near-optimal schedules for the 1|V_j(t)|maxV_j problem are then described. After this, the results of the computational experiments for empirically evaluating the proposed algorithms are reported and discussed. Finally, we conclude the paper with a summary and some fruitful directions for future research.

Problem formulation and complexity

In this section, we formulate the 1|V_j(t)|maxV_j problem and show that the general problem is unary NP-hard. However, some special cases are polynomially solvable. To start the discussion in this section, we formally define the 1|V_j(t)|maxV_j problem and describe several types of job value functions analyzed in this paper. Then, we show that the problem with equal processing times is polynomially solvable. Problems with unrestricted job value functions are considered next where it is shown that the 1|V_j(t)=w_j-_jt|maxV_j problem is polynomially solvable. Problems with exponential job value functions are shown to be unary NP-hard unless the job value deterioration rate for all jobs is a constant. Utilizing these results, we then show that problems with truncated job value functions and/or capacity constraints are unary NP-hard even for linear job value functions. Finally, we describe a dominance algorithm to find an optimum solution to the 1|V_j(t)|maxV_j problem.

Problem definition and job value functions

Let N={1,2,...,n} be the set of n jobs, available at time zero, that is to be processed on a single machine without interruptions, preemption or inserted idle time. There are no setup times. At any given time, the machine can process only one job. Associated with each job jN is the processing time of p_j and its value V_j(t) which is a non-increasing function of its starting time t. Because of the capacity constraints, the value of any job j may not exceed an upper limit U_j. It is desired to find a schedule that will maximize the total value of all jobs.

To define this problem, consider a schedule =((1),(2),...,(n)) of n jobs. Then, the start time t_j of job (j) is given by

Therefore, the total value of schedule is given by

Then, the problem considered in this paper is one of finding a schedule such that V() calculated using Equations (1) and (2) is maximum.

The value function of each job j, V_j could take various forms. In this paper, we consider cases involving linear and exponential job value functions. Problems involving no capacity constraints are called the unrestricted job values. However, in several situations, the job value may deteriorate up to some time and remain constant after that time. We call this type of job values truncated job values. Further, there may be an upper limit on the value of a job due to certain restrictions, like the maximum number of seats available in a movie theatre. These type of job value functions will be called capacity constrained job values. Based on the above discussion, representative job value functions can be shown in Figure 1.

Figure 1.

Representative job value deterioration functions.

Full figure and legend (55K)

In this paper, we focus on these cases of job value functions.

Problems with equal processing times

While the general problem is shown to be unary NP-hard later in this section, the equal processing time problem can be polynomially solved as shown below.

Theorem 1

The 1|V_j(t), p_j=p j|maxV_j problem is optimally solvable in O(n³) computation steps by solving an assignment problem.

Proof

Since the processing times of all jobs are equal, the starting time of the job at sequence position i is (i-1)*p, where i=1,...,n. Introduce assignment variables x_ij (i,j=1,...,n), such that, x_ij=1 if job j is assigned to sequence position i and=0 otherwise. The problem can be formulated as follows:

subject to:

The above optimization problem represented by (3), (4),(5) and (6) can be converted into an equivalent standard linear assignment problem by subtracting each value V_j((i-1)*p) in the objective function in Equation (3) from max_jn(V_j(0)). This assignment problem can be formulated in O(n²) computational steps and solved in O(n³) computational steps (Lawler, 1976).

Unrestricted job value functions

We now resolve the complexity of the 1|V_j(t)|maxV_j problems starting with those involving unrestricted job value functions.

Unrestricted linear job value functions.

We first consider the 1|V_j(t)=w_j-_jt|maxV_j problem with unrestricted linear job value function where the value of job j starting at time t is given by V_j(t)=w_j-_jt. In order to ensure that job values are not negative, it is assumed that for each job j, w_j, _j>0 and w_jj(P-p_j) where P=_s=1ⁿp_s.

Theorem 2

The 1|V_j(t)=w_j-_jt|maxV_j problem is optimally solvable in O(n log n) computation steps by arranging jobs in descending order of the _j/p_j values.

Proof

Let =((1),(2),...,(n)) be a schedule of n jobs where (j) represents job in sequence position j. Further, let C_(j) be the completion time of job (j). Then, using Equations (1) and (2), the value of schedule , V() is given by

From Equation (7) above, it is clear that V() is maximized by minimizing _j=1ⁿ{_(j)C_(j)}, which is the sum of the weighted completion times of all jobs. Therefore, this problem is polynomially solvable in O(n log n) computation steps using Smith's (1956) rule by arranging jobs in descending order of the _j/p_j values.

During the application of above (or heuristics based on similar analysis discussed in a later section), there may be ties that do not cause any problem and can be resolved arbitrarily. However, for its extension to other cases, appropriate tie-breaking rules are required. Therefore, in implementing Theorem 2, we break ties in favour of a job with maximum w_j/p_j value first, maximum w_j value second, and maximum _j value last. However, in case of equal values for all parameters, we select the job randomly.

Unrestricted exponential job value functions.

The value of job j is given by

where V_j(t_j) is interpreted as a job value deteriorating function, t_j is the starting time, and w_j, _j>0. The objective function of the problem is as follows:

Before resolving the complexity of the general 1|V_j(t)=w_je^-_jt_j|maxV_j problem, we note that through a simple job interchange argument, the following special case can be polynomially solved.

Theorem 3

The 1|V_j(t)=w_je^-t|maxV_j problem is optimally solvable in O(n log n) computation steps by arranging jobs in descending order of w_j/(1-e^-p_j) values.

To prove that the 1|V_j(t)=w_je^-_jt|maxV_j problem and the general 1|V_j(t)|maxV_j problem are unary NP-hard, we define the following 3-partition problem instance which is known to be unary NP-hard (Garey and Johnson, 1979).

Problem complexity

3-Partition problem instance (I): Given 3m+1 positive integers a₁,...,a_3m and b such that _j=1^3ma_j=mb, where each a_j>1 is bounded by a polynomial of m and b/4<a_j<b/2 for j=1,...,3m; is there a partition of the set j=1,...,3m into m disjoint three-element subsets {S₁,S₂,...,S_m} such that _jSka_j=b for k=1,...,m?

In case any one of the a_j=1 in the above 3-partition problem, all a_j=1 and b=3. This implies that the special case of the above 3-partition problem with a_j=1 for some j is trivially solvable in constant time. For this reason, this special case is excluded from our above definition of the 3-partition problem.

Now, we define an instance of the 1|V_j(t)=w_je^-_jt|maxV_j scheduling problem with the following parameter values.

Scheduling problem instance (Î) Given n=4m-1 jobs consisting of two subsets N₁={1,2,...,3m} and N₂={3m+1,3m+2,...,4m-1}. For each job jN₁, p_j=a_j, w_j=1-e^-a_j, and _j=1; and p_j=1, _j=1/2, and w_j=(1-e^-2)*e^{-{(j-3m)+(j-3m-1)}/2}, for jN₂ where j=jb-1. It is desired to find a schedule that maximizes V_j=_{[j]=1ⁿw[j]e^-[j]t} where [j] is the job at sequence position j.

Lemma 1

The current problem instance Î of the 1|V_j(t)=w_je^-_jt|maxV_j problem can be constructed from the 3-partition instance I in pseudo-polynomial time.

Proof

Length (I)=3m+1+_iSlog₂(a_i)>3m+1 and Max(I)=b, where x represents the least integer greater than or equal to x. To construct instance (Î) of the 1|V_j(t)|maxV_j problem, one needs to compute w_j for each job jN₁N₂. For jN₁, w_j can be computed through at most a_j time divisions and one time addition, which needs at most O(b) computational steps, since a_j's are always less than b/2. Similarly, for all jN₂, w_j can be computed in O(2*{(m-1)b+m/2+1}) computational steps. Hence to compute all w_j, at most O(3mb+2m{(m-1)b+m/2+1}) computational steps are needed. Computational complexity of computing parameter is O([log₂(b)]+[log₂(m)]). The other parameters of the current problem instance can be found in constant time. To compute all instances of the current problem will take at most O(4mb+2m{(m-1)b+m/2+1}) computational steps. Hence, the current instance Î of the 1|V_j(t)|maxV_j problem can be constructed in time polynomial in Length (I) and Max (I) of the 3-partition problem instance I. This implies that the current instance Î can be constructed from the 3-partition instance in pseudo-polynomial time (Garey and Johnson, 1979).

Lemma 2

For instance Î of the 1|V_j(t)=w_je^-_jt|maxV_j problem, cumulative job value does not depend upon the ordering of jobs in sets S_i, 1im, where each S_i is the maximal subset of adjoining elements from the set N₁.

Proof

By definition of the scheduling problem instance Î, for each job jS_i, a_j=p_j, w_j=1-e^-a_j, and _j=1. Let S_i=(_i(1),...,_i(r_i)), where r_i is the total number of jobs in S_i. Then, the value of _jSiw_je^-_jt_j in the objective function can be written as

This implies that the objective value does not depend on the order of jobs in sets S_i, 1im.

Lemma 3

In an optimal schedule for instance Î of the 1|V_j(t)=w_je^-_jt|maxV_j problem, job jN₂ starts at time t_j={(j-3m)+(j-3m-1)}+1 irrespective of the ordering of jobs in subset N₁.

Proof

Suppose that in an optimal schedule for instance Î, job iN₁ immediately follows job jN₂. Then,

Substituting the parameter values from the definition of the problem instance Î in Equation (11), we get

where

Since, by definition, p_i>1 for iN₁, it follows that -<A<0. In addition, as each p_i is an integer, the starting times of all jobs will be integers. Further, in order to optimize the cumulative job value, starting time of job j, while satisfying condition (12) should be as small as possible. Therefore, in an optimal schedule, job jN₂ starts at time t_j given by

From Equation (14), it is clear that the starting time of job jN₂ does not influence the order of jobs in subset N₁ nor is influenced by them.

Theorem 4

The 1|V_j(t)=w_je^-_jt|maxV_j and 1|V_j(t)|maxV_j problems are unary NP-hard.

Proof

The processing order and starting times of jobs N₂ are obvious because of their parameters and above. Therefore, filling other jobs in the time gaps created by the schedules of jobs in N₂ will improve the objective function value. With this viewpoint, we consider a complete schedule as shown in Figure 2 where the processing order of jobs will be ({i|iS₁},3m+1,{i|iS₂},3m+2,{i|iS₃},...,4m-1,{i|iS_m}), where S={S₁,S₂,...,S_m}={1,...,3m}.

Figure 2.

A possible solution of the 3-partition problem.

Full figure and legend (6K)

From Figure 2, it follows that the starting time of job 3m+1 is between b and _iS1a_i-b=L₁. The starting time of job 3m+2 is between 2b+1 and _iS1S2a_i+1-2b-1=L₂. Similarly, the starting times of jobs 3m+3,...,4m-1, will deviate from points 3b+2,...,mb+m-1 by L₃,...,L_m-1. From it follows that the value of _jSw_je^-_jt_j is not influenced by the ordering of jobs within the sets S₁,S₂,...,S_m. Further, from Lemma 3, it is clear that the ordering of jobs within sets S₁,S₂,...,S_m is not influenced by the jobs in subset N₂. Using Lemma 2, the objective function for the scheduling problem instance Î defined by Equation (9), Z=_jN1N2w_je^-_jt_j can be written as

which simplifies to

Since p_j and b are integers, L_k must be integer. Therefore, from Equation (16), it is clear that the objective function Z increases as |L_k| decreases. Hence, the objective function Z will be maximum at |L_k|=0 (k=1,2,...,m-1). Therefore, substituting L_k=0 in Equation (16), the optimal value of the objective function Z^* is given by

Now, if the 3-partition instance I has a solution, then _jSka_j=b and |L_k|=0 km. Therefore, the corresponding scheduling problem instance Î has an optimal solution with value Z^* given by Equation (17).

Conversely, if the scheduling problem instance Î has an optimal solution with value Z^* given by Equation (17), then _jSka_j=b and |L_k|=0 km. Further, since b/4<a_j<b/2 for j=1,...,3m, it follows that each S_k contains exactly three elements. Therefore, the subsets S₁,S₂,...,S_m is a solution to the 3-partition instance I. Since the 3-partition problem is known to be unary NP-hard, and that the scheduling problem instance Î can be constructed from the 3-partition instance I in pseudo-polynomial time (above), using the results in Garey and Johnson (1979), it follows that the 1|V_j(t)=w_je^-_jt|maxV_j and 1|V_j(t)|maxV_j problems are unary NP-hard.

Theorem 4 above can be used to resolve the complexity of several other forms of exponential deterioration function as shown by the following corollary.

Corollary 1

The 1|V_j(t)=w_ju^-_jt, u>1|maxV_j and 1|V_j(t)=w_ju^-_jt, u_j>1 j|maxV_j are unary NP-hard.

Truncated job value functions

We now consider the problem where the value of job j remains constant after a certain time. In other words, we consider the job value function of the form, V_j(t)=max(v_j,f_j(t)) where f_j(t) is a nonincreasing function of the start time t of job j and v_j=f_j(T_j) for some starting time T_j of job j. In other words, the value of a job j deteriorates only up to time T_j and not after that time.

We now show that 1|V_j(t)=max(v_j,f_j(t))|maxV_j problem is unary NP-hard for any nonincreasing job value function.

Theorem 5

The 1|V_j(t)=max(v_j,f_j(t))|maxV_j problem is unary NP-hard for any non-increasing job value function.

Proof

To prove this theorem, consider the 1|V_j(t)=max(v_j,w_j-_jt)|maxV_j problem where for each job j, v_j=w_j-_jT_j. Suppose that in an optimal schedule, subset of jobs started on or before time T_j is ₁ and those started after time T_j is ₂. Define the deadline of job j, time by which job j must be completed, _j as follows: _j=T_j+p_j if j₁ and _j= if j₂. Then, using the developments similar to those in the proof of Theorem 2, it follows that the problem of finding an optimal schedule for the two subset of jobs ₁ and ₂ is equivalent to the 1|_j|w_jC_j problem (single machine problem to minimize weighted flowtime subject to deadlines) which is known to be unary NP-hard (Lenstra et al, 1977). Since this subset of the special case of the 1|V_j(t)=max(v_j,f_j(t))|maxV_j problem is unary NP-hard, it follows that the general 1|V_j(t)=max(v_j,f_j(t))|maxV_j problem is unary NP-hard for any nonincreasing job value function.

Capacity constrained job value functions

We now consider problems where capacity constraints causes an upper limit U on the value that a particular job can create. Therefore, the capacity constrained job value function may be represented as follows:

where f_j(t) is the unconstrained job value function.

If Umin_jnf_j(P-min_inp_i) where P=_i=1ⁿp_i, then any sequence is optimal. Further, if Umax_jnf_j(0), the problem reduces to the 1|V_j(t)=f_j(t)|maxV_j problem whose complexity has been established above. Therefore, in this section, we consider the non-trivial case of the capacity constrained problem where U does not satisfy the above constraints.

Theorem 6

The 1|V_j(t)=min(U,f_j(t))|maxV_j problem is unary NP-hard for any non-increasing job value function.

Proof

Consider a special case of this problem where V_j(t)=min(U,w_j-_jt) and U=w_j-_jT_j.

Then, the job value function can be written as

Let C_j=t_j+p_j be the completion time of job j and define d_j=T_j+p_j as its due date. Then, the 1|V_j(t)=min(U,w_j-_jt)|maxV_j problem is equivalent to the 1w_jT_j (single machine weighted tardiness) problem which is known to be unary NP-hard (Lawler, 1977; Lenstra et al, 1977). Therefore, the 1|V_j(t)=min(U,f_j(t))|maxV_j problem is unary NP-hard for any non-increasing job value function.

Capacity constrained truncated job value functions

The objective function of the capacity constrained problem with truncated job value function is as follows:

If Umin_jnv_j, then any sequence is optimal. For other values of U, we now state the problem complexity.

Theorem 7

The 1|V_j(t)=min{U,max(v_j,f_j(t))}|maxV_j problem is unary NP-hard.

Proof

Follows from above since the 1|V_j(t)=min{U,f_j(t)}|maxV_j problem is special case of the 1|V_j(t)=min{U,max(v_j,f_j(t))}|maxV_j problem.

Time index formulation

The above problem, regardless of the form of the job value function, can also be formulated as a mixed linear integer program (Sousa and Wolsey, 1992). To do so, for each job j, let x_jt=1, if job j is started at time t; and 0 otherwise. Further, let

The problem then may be represented as the following integer program:

Subject to

The first set of equations ensures that each job is scheduled exactly once, whereas the second set of inequalities ensures that at each time, at most one job is executed.

Dominance algorithm

We now describe an optimization algorithm to solve the 1|V_j(t)|maxV_j problem. For this purpose, let V() be the total value of a partial (or complete) schedule containing k jobs expressed as follows:

Now consider two partial schedules and ' that are different permutations of the same subset of jobs. Then, we state the following known result.

Theorem 8

For any schedules and ' that are different permutations of the same subset of jobs, V()V(') implies V()V(').

A schedule satisfying the conditions of is said to dominates schedule '. Based on this, a pure dominance theorem to optimally solve the 1|V_j(t)|maxV_j problem can be described as follows.

Pure dominance algorithm

Step 0: Let L=1 and S={1,2,...,n} be the set of n partial schedules each consisting only of one job jN. Compute V() S. Enter Step 1.

Step 1: For each partial schedule S, form n-L partial schedules consisting of L+1 jobs by assigning each of the n-L unassigned jobs at sequence position L+1. Let the set of partial schedules so formed be S. Compute V() S.

Step 2: Group the partial schedules containing the same subset of jobs together, that is, let S={S₁,S₂,...,S_k}, where for each ik, S_i contains all partial schedules containing the same subset of jobs. For each subset S_i, retain the partial schedule _i with maximum V(_i) value, that is, find _iS_i such that V(_i)=max_jSiV(j). Enter Step 3.

Step 3: Let L=L+1. If L<n, return to Step 1. Otherwise STOP; the last schedule retained in Step 2 is optimal.

While the above algorithm will optimally solve the 1|V_j(t)|maxV_j problem, it is, however, not likely to be an efficient algorithm. Its computational burden is exponential as in the best case, it will retain _r=1ⁿ{ⁿC_r} partial schedules.

Proposed heuristics

In view of the NP-hard nature of the problem, we present several heuristics that are based on existing literature. Since several existing algorithms can be used for problems with linear job value functions (by considering their minimum counterparts), we concentrate on developing heuristics for the non-linear job value functions.

Heuristics for unrestricted job value functions

Our first set of heuristics is an adaptation of greedy algorithms. At any sequence position, a greedy selection rule is used to assign a job to that sequence position. The basic steps of this greedy algorithm are as follows:

Algorithm G: basic greedy algorithm

Step 0: Let t=0, U=N={1,2,...,n}, and S=. Enter Step 1.

Step 1: Let j be the job to be assigned to current sequence position using some selection rule. Enter Step 2.

Step 2: Set S=(S,j), U=(Uj), t=t+p_j, and enter Step 3.

Step 3: If U=, find V(S) using Equations (1) and (2) and STOP, otherwise return to Step 1.

Algorithm G has a computational complexity of O(n²).

It remains to specify the selection rule used in Step 1 of the above algorithm. We now describe several rules to select job j to be assigned to a sequence position in Step 1 above.

Our first heuristic selects a job with maximum job value per unit time at a particular time t.

Algorithm H: highest value heuristic

Step 1: Let j=arg[max_iU(V_i(t)/p_i)] using appropriate tie-breaking rules. Enter Step 2.

Our next heuristic follows the work of Fisher and Krieger (1981, 1984). This algorithm creates a dynamic job savings index for scheduling a job at time t rather than at the end of the schedule. To describe this algorithm, let P=_iNp_i.

Algorithm F: Fisher's greedy algorithm

Step 1: Let j=arg[max_iU(V_i(t)-V_i(P-p_i)/p_i)] using appropriate tie-breaking rules.

Enter Step 2.

Alidaee (1993) suggests to approximate V_j(t) by a continuous function over time and hence makes decisions based on the rate of value deterioration rather than the absolute value. To describe this algorithm, let V_j'(t) be the differential of the job value function with respect to t. Step 1 of this algorithm can be described as follows:

Algorithm A: Alidaee's differential algorithm

Step 1: Let j=arg[min_iU(V_i'(t)/p_i)] using appropriate tie-breaking rules. Enter Step 2.

Computational experience with algorithm A showed that it did not yield good results. However, its application in reverse, namely using the job selection rule from the last sequence position to the first produced excellent results. Therefore, we describe this revised algorithm as follows.

Algorithm R: Alidaee's reverse differential algorithm

Step 0: Let t=P, U=N={1,2,...,n}, and S=. Enter Step 1.

Step 1: Let j=arg[min_iU(V_i'(P-t)/p_i)] using appropriate tie-breaking rules. Enter Step 2.

Step 2: Set S=(j,S), U=(Uj), t=t-p_j, and enter Step 3.

Step 3: If U=, find V(S) using Equations (1) and (2) and STOP, otherwise return to Step 1.

For the linear job value function, algorithms A and R described above generate an optimal schedule as they implement stated earlier. Therefore, their computational complexity for the linear case can be reduced to O(n log n).

Our next algorithm is an adaptation of the greedy algorithm due to Voutsinas and Pappis (2002). Because of its use of special function, it is applicable to only those objective functions where some sort of weight w_j for each job j is available (like in the exponential job value functions considered in this paper). They generate four schedules using the following job selection criteria and select the best schedule.

Algorithm V1

Step 1: Let j=arg[min_iU(p_i)] using appropriate tie-breaking rules, similar to the ones described earlier. Enter Step 2.

Algorithm V2

Step 1: Let j=arg[min_iU(p_i/w_i)] using appropriate tie-breaking rules, similar to the ones described earlier. Enter Step 2.

Algorithm V3

Step 1: Let j=arg[max_iU(w_i)] using appropriate tie-breaking rules, similar to the ones described earlier. Enter Step 2.

Algorithm V4

Step 1: Let j=arg[max_iU(V_i(p_i))] using appropriate tie-breaking rules, similar to the ones described earlier. Enter Step 2.

Then, the Voutsinas and Pappis algorithm selects the schedules with maximum cumulative job values. Thus, for this algorithm we add additional step as follows:

Algorithm V: Voutsinas and Pappis algorithm

Step A: Let S₁, S₂, S₃ and S₄ be the schedules found by using Algorithms V1 to V4 above. Select schedule S such that S=arg[max(V(S₁),V(S₂),V(S₃),V(S₄))].

The computational complexity of algorithm V can be reduced to O(n log n) since algorithms V1 through V4 can be implemented in O(n log n) computational steps.

We now describe an adjacent pairwise interchange (API) heuristic which can generate a better schedule, if one exists. To describe this algorithm, let =(₁,₂,...,_n) be the schedule generated by one of the above algorithms with value V(). Then, the steps of the API heuristic are as follows:

Algorithm I: adjacent pairwise interchange algorithm

Step 0: Let =((1),(2),...,(n)) be the initial schedule. Let i=c=1. Enter Step 2.

Step 1: Let '=(₁,...,_i-1,_i+1,_i,...,_n). If V()<V('), set =' and c=2. Enter Step 2.

Step 2: If i<n-1, set i=i+1 and return to Step 1; otherwise enter Step 3.

Step 3: If c=2, set c=i=1 and return to Step 1; otherwise STOP and accept as the solution obtained.

Since any change in a pair of jobs can trigger another iteration of the algorithm, the computational complexity of algorithm I is O(n²).

Since algorithm I can be used for any algorithm, we have a total of eight heuristics for the unrestricted 1|V_j(t)|V_j problem; namely, algorithms, H, F, R, V, HI, FI, RI, and VI. The first four of these eight algorithms have a computational complexity of O(n log n) while the computational complexity of other four heuristics is O(n²+n log n).

Heuristic for truncated job value functions

We now describe adaptation of the heuristics developed above for the truncated job value functions of the form V_j(t)=max(v_j,f_j(t)). To describe this heuristic, for each job j, we find target time T_j such that v_j=f_j(T_j). Then, the heuristic based on those heuristics described above is as follows.

Algorithm T: truncated job value algorithm

Step 1: Let =((1),(2),...,(n)) be the schedule generated by one of the heuristics for the unrestricted job value function. Let t=0, j=1, and A=B=. Enter Step 2.

Step 2: If t<T_((j)), let A=(A,(j)) and proceed to Step 5; otherwise, enter Step 3.

Step 3: From schedule A, find sequence A_q where q is the least sequence position such that t_(q)T_(j). Let . Let . If , enter Step 4; otherwise set B=(B,(j)), t=t-p_(j), and proceed to Step 5.

Step 4: If V_(k)(t_(q)-p_(k)+p_(j))>v_(k), set ; otherwise set , B=(B,(k)), and t=t-p_(k). Enter Step 5.

Step 5: Set t=t+p_(j). If j<n, set j=j+1 and return to Step 2; otherwise STOP.

Heuristic for capacity constrained job value functions

For the 1|V_j(t)=min(U,f_j(t))|V_i problem, we adapt the above algorithm T. To do so, we define the target start time of job jN, T_j such that U=f_i(T_j). The Steps 2 and 3 of the above algorithm are modified as below.

Algorithm C: capacity constrained job value algorithm

Step 1: Let =((1),(2),...,(n)) be the schedule generated by one of the heuristics for the unrestricted job value function. For each job iN, find T_i such that U=f_i(T_i). Let t=0, j=1, and A=. Enter Step 2.

Step 2: If t<T_((j)), let A=(A,(j)) and proceed to Step 4; otherwise, enter Step 3.

Step 3: From schedule A, find sequence A_q where q is the least sequence position such that t_(q)T_(j). Let . Let . If , set ; otherwise set A=(A,(j)). Enter Step 4.

Step 4: Set t=t+p_(j). If j<n, set j=j+1 and return to Step 2; otherwise STOP.

The computational complexity of algorithms T and C is O(n²) in addition to that of getting the schedule in Step 1. Therefore, such improvements of the algorithms for the unconstrained case do not increase the overall complexity of the heuristics.

Heuristic for capacity constrained truncated job value functions

For the 1|V_j(t)=min(U,max(v_j,f_j(t)))|V_i problem, we use a combination of algorithms T and C above. First, we solve the problem using algorithm C and then use algorithm T on the resulting schedule.

For algorithms T, C, and CT, any of the algorithms developed earlier can be used as an input schedules. However, in our implementation, we used algorithms HI, FI, and RI as starting schedules for each of the algorithms T, C, and CT.

Computational results

In this section, we report on the results of the computational experiments designed to evaluate the effectiveness and efficiency of the proposed heuristic algorithms in finding good quality schedules. The time index formulation of the problem could not be used to solve the large-sized problems considered in this paper. No other optimization algorithms exist to solve these large problems. For these reasons, for large sized problems, we compared the performance of these proposed heuristic algorithms relative to the best one.

Test problems

In order to test the effectiveness of the proposed heuristics, we considered two forms of the job value functions: V_j(t)=w_j-_jt and V_j(t)=w_je^-_jt. Limited computational tests were also conducted for the job value function V_j(t)=w_j(t)^-_j used by Voutsinas and Pappis (2002) and found to show that proposed heuristics are superior to those of Voutsinas and Pappis (2002). However, these results are not reported in this paper. For each case, we consider the unrestricted, truncated, capacity constrained, and combined cases.

The parameters for each job were generated on the basis of real-life movie scheduling problem by using uniform random numbers. The processing time and initial job value of each job jN, p_j and w_j were integers from a uniform distribution in the range [5,17] and [80,120], respectively. For each job jN, define

Problem hardness is likely to depend on whether there is a balance between average processing times, capacity constraints, truncation points, and job value deterioration rates. For this reason, three classes of problems for the truncation points, capacity constraints, and job value deterioration rates were generated as shown in Table 1 below.

Table 1 - Levels of the job value functions.

Full table

The number of jobs n=5,10,15,20,50,100,150, and 200. Problems involving 20 or less jobs were classified as small problems while those with more than 20 jobs were considered large problems. For small-sized problems, we solved 30 problems instances for each size while for the large-sized problems, 50 problem instances of each size were solved.

Algorithm effectiveness for small problems

Each problem instance was formulated an integer program and was solved to optimality by CPLEX 7.0 in Solaris 5.8 Environment. The average CPU time for these small sizes of problems on CPLEX 7.0 in Solaris 5.8 Environment was approximately 30 s. Each greedy and adjacent pairwise interchange algorithms were used for each problem instance regardless of the nature of the job value function. In addition, each problem instance was solved using each of the algorithms applicable to the specific job value function being considered. For example, for the truncated and capacity constrained cases, algorithms T and C were used, respectively. Similarly for the combined case, both algorithms T and C were used. However, to keep the tables manageable, algorithms T, C, or TC are represented by T only. However, the designation of specific cases being considered makes the context quite clear.

For each problem instance, the effectiveness of the heuristic algorithm h is determined by optimality gap, OG_h (in terms of percentage), which is defined as

where Z_h and Z_o are solutions obtained by heuristic h and the time-index formulation of the problem, respectively.

Tables 2 and 3 depict the average and maximum values of the optimality gap, OG_h for each algorithm h for the small size problems. The highest value heuristic H did not perform as well as others. However, even for this heuristic, the average optimality gap was rarely more than 10%. Among the greedy algorithms, algorithm F, which is based on the Fisher and Krieger's procedure, produced lower average percentage optimality gap for each problem size. The average optimality gap for heuristic F is less than 1% for all problem sizes. In addition, the maximum optimality gap for heuristic F is rarely more than 15%.

Table 2 - Average optimality gap of the proposed algorithms for small problems.

Full table

Table 3 - Maximum optimality gap of the proposed algorithms for small problems.

Full table

For the problem instances tested, algorithms R and V, which are based on the work of Alidaee and Voutsinas and Pappis, did worse. This result is surprising since for the cost minimization case, Alidaee reports that his proposed algorithms yield better results than Fisher and Krieger algorithms. We conjecture that the problem parameters used by Alidaee may have been rather restrictive in empirically evaluating the two algorithms. Job value dependence on the job starting times in our case and completion times in Alidaee's paper could have also have contributed to these surprising results.

Use of the improvement algorithms I, T, and C significantly improved the results of each greedy algorithm. However, on the average, algorithm FI leads to lower percentage optimality gaps than algorithms HI, RI, and VI. The use of algorithms T and C for the truncated and capacity constrained problems dramatically improves the performance of algorithms HI, FI, RI, and VI. In fact, use of algorithms I, T, and C reduces the average and maximum gaps to less than 1 and 9% for all algorithms.

As the problem size increases, the performance of each heuristic decreases, but not significantly. Further, while not shown in the tables, heuristics performed worse on problems with low or high levels of deterioration rate and high level of truncation.

Algorithm effectiveness for large problems

Each problem instance (n=50,100,150, and 200 jobs) was solved using each of the algorithms applicable to the specific job value function being considered. Further, each greedy and adjacent pairwise interchange algorithms were used for each problem instance regardless of the nature of the job value function.

For large job size problems, the average CPU times on CPLEX 7.0 in Solaris 5.8 Environment were greater than 2 h. Therefore, we used the best value of the objective function obtained by any of the heuristic in the same class (like the H, F, R, and V) as a surrogate of an optimal solution value. Therefore, for each set of 50 large problems instances, we have calculated the optimality gap, OG_h for each heuristic h as follows:

where _c is the best solution among heuristics from class c.

Tables 4 and 5 show the average and maximum values of the optimality gap, OG_h for each algorithm h for the large size problems. The results in Table 4 confirm the conclusions for the small problems. Greedy algorithms based on the Fisher and Krieger's procedure, like algorithm F produced lower average percentage optimality gap for each problem size, the average optimality gap being 4.5% or less. Greedy algorithms based on the work of Alidaee and Voutsinas and Pappis did worse.

Table 4 - Average optimality gap of the proposed algorithms for large problems.

Full table

Table 5 - Maximum optimality gap of the proposed algorithms for large problems.

Full table

Use of the improvement algorithm I significantly improved the results of each greedy algorithm, bringing the average optimality gap to less than 1% for heuristics FI, FIT(C), RI, RIT(C), and VIT(C). However, on the average, algorithm FI leads to lower percentage optimality gaps than algorithms HI, RI, and VI. Further, compared to the results for small problems, the neighbourhood improvement algorithm I produced significantly more improvements for large problems. The use of algorithms T and C for the truncated and capacity constrained problems dramatically improves the performance of algorithms HI, FI, RI, and VI. The maximum optimality gap values in Table 5 show a similar pattern as those for small problems in Table 3. While not shown in Tables 4 and 5, each heuristic performed worse on problems with low or high deterioration rates and low and high capacity restrictions.

From the above computational results, algorithms based on the piecemeal linear approximation of the job value functions suggested by Fisher and Krieger generate the best schedules for the single machine problems with deteriorating job value functions. Algorithm V based on the work of Voutsinas and Pappis consistently performed worse producing optimality gaps greater than heuristic H. However, even for algorithm V, used of proposed improvement heuristics significantly improved its effectiveness.

Conclusions

This paper considered the problem of scheduling a given number of movies in a theatre to maximize total profit. The problem is formulated as one of scheduling jobs on a single machine where the job value deteriorate with its start time and designated by 1|V_j(t)|maxV_j. In view of several practical applications of the problems, different operating configurations, like the limitations on the job values due to the machine capacity constraint were also considered. In addition, this paper analyses cases where the job values may stop deteriorating after a specified starting time.

Except for a some special cases, the 1|V_j(t)|maxV_j problem was shown to be unary NP-hard where the job deterioration function is V_j(t) is a non-increasing function of the starting time of job j. In view of the NP-hard nature of the problem, several heuristic algorithms are developed to find optimal or near optimal schedules for various cases of the 1|V_j(t)|maxV_j problem. Computational results over a large number of problems show that the proposed algorithms generated near-optimal solutions for a large number of problem instances. Among the heuristics tested, heuristic F produced the best results while algorithm V produced the worst results. Further, the use of the adjacent pair-wise interchange algorithm I was found to substantially improve the quality of the solutions obtained by any of the proposed greedy algorithms. Use of algorithms T and C could further improve the results.

While we considered the single machine scheduling problem where the job value deterioration depends on the job starting times, we note that our results and proposed heuristic algorithms can easily be adapted to the problems where the job value deterioration depends on the job completion times. Except for some minor changes in the details of the proofs, all complexity results are valid for the 1|V_j(C_j)|maxV_j problem where C_j is the completion time of job j. Similarly, for the proposed heuristics, equivalent job selection criteria can easily be described for the 1|V_j(C_j)|maxV_j problem.

The development of various heuristic algorithms in this paper also results in some fruitful directions for future research. First, it would be helpful to develop tight bounds and some dominance conditions to develop an effective branch and bound algorithm for the 1|V_j(t)|maxV_j problem. Second, the proposed heuristics can be modified to obtain improved solutions.

One way to do this is to use combinations of the proposed heuristics. For example, algorithms F, H, and R could be used in combination to improve the solution value. Third, it would be interesting to develop heuristics for the 1|V_j(t)|maxV_j problem with specified worse-case performance bounds. Fourth, it would be interesting and useful to develop and evaluate various local search heuristics such as tabu search and genetic algorithms. Finally, extension of the results to schedule movies in a multiplex theatre where several movie screens are available to schedule multiple movies at the same time would enhance the practical utility of scheduling theory. Thus, more research is necessary in the area of scheduling on non-manufacturing sector.