1.Introduction

It is very common that a set of jobs being processed according to a schedule must be rescheduled because of a disruption. Events that might cause a disruption include the arrival of a new job, the breakdown of a machine, or the unavailability of materials. Most deterministic machine scheduling problems deal with constant job processing times. In various real-life systems, however, processing times may be compressed by allocating additional resources, such as money, overtime, energy, fuel, catalysts, or manpower.

This paper deals with rescheduling on unrelated parallel machines with compressible processing times and proposes a heuristic. We assume that the original set of jobs had been optimally scheduled on unrelated parallel machines to minimize the sum of completion times and the costs of compressing processing times and that a disruption occurs when a set of new jobs arrives. In rescheduling, some additional measures may be needed, because any change of the original schedule may lead to additional cost (e.g., transportation) and rescheduling effort (e.g., job reassignment, workforce rescheduling, and/or customer delivery-date changes). Rescheduling parallel machines may result in reassigning some job to a machine other than the one on which it was originally scheduled, a result we call machine reassignment. We consider the disruptions caused by machine reassignments, either as part of the objective function or by imposing a constraint to limit their number. When the cost of reassignment is difficult to estimate, we limit the number of machine reassignments by imposing a constraint, resulting in an assignment problem with a side constraint (APSC) (i.e., an NP-hard problem [13]).

Several papers have contributed to rescheduling on parallelmachines with machine reassignment as an additional measure. For example, Alagoz and Azizoglu [4] and Azizoglu and Alagoz [6] studied the objective of minimizing the sum of completion times and either included penalties for machine reassignment in the objective function or limited the number of reassignments permitted with an additional constraint. Curry and Peters [8] limited machine reassignments by invoking a constraint and used simulation to demonstrate the effect of reassignment in the parallel-machine scheduling environment. Ozen and Azizoglu [15] considered unrelated parallel machines to minimize the total flow time, restricting the total reassignment cost.

Compressible processing times can provide flexibility for rescheduling by managing processing times. Scheduling with compressible processing times has been studied extensively. Shabtay and Steiner [19] gave an extensive survey on this topic. Gurel and Akturk [11] studied a single machine with compressible processing times with different non-linear compressible cost functions. Yin and Wang [22] studied a single machine to minimize a cost function containing makespan, considering compressible processing times and learning effect. Yang [21] studied rescheduling on a single machine configuration with compressible processing times, allowing time compressions only for newly arrived jobs. Akturk et. al. [3] introduced parallel machine match-up scheduling problems to cope with machine disruptions when processing times of the jobs are compressible at a certain manufacturing cost. Gurel and Cincioglu [10] studied a parallel machine rescheduling problem with compressible processing times for number of disrupted jobs. They considered a bicriteria rescheduling problem to deal with a trade-off between the number of on-time jobs and manufacturing cost, admitting machine reassignment.

Several solution approaches have been proposed for APSC. Murty [14] proposed a ranking algorithm, which generates all assignments in order of increasing cost and selects the least-cost assignment that satisfies the side constraint. Gupta and Sharma [9] developed an enumeration scheme using a search tree in which each node represents a complete, feasible solution, so that a node can be fathomed if the solution it represents is infeasible with respect to the side constraint. Aggarwal [2] presented a two-stage algorithm that applies Lagrange relaxation to eliminate the side constraint and then searches for an optimal solution using Murty’s [14] ranking algorithm. Aboudi and Jornsten [1] took a polyhedral approach, presenting several classes of valid inequalities and associated separation problems. Mazzola and Neebe [13] presented a branch-and-bound (B&B) algorithm that incorporates the subgradient method as part of a bounding procedure and a subgradient-based heuristic. Punnen and Aneja [18] observed that the Mazzola-Neebe heuristic is sensitive to the range of the coefficients in the objective function and in the side constraint. Lieshout and Volgenant [12] proposed a B&B algorithm, obtaining lower bounds by utilizing Lagrange relaxation and a heuristic by modifying the B&B algorithm. They mentioned that the B&B algorithm and their heuristic were also affected by the range of coefficients: if the ranges double, their run times also double.

In our study, we consider rescheduling on unrelated parallel machines with compressible processing times and propose a heuristic which is less sensitive to the range of coefficients. The body of this paper is organized in four sections. Section 2 formulates the scheduling and rescheduling problems we study. Section 3 presents our LP(Linear Programming)-based heuristic for APSC. Section 4 describes a computational evaluation of the proposed heuristic. Finally, section 5 relates our conclusions and fertile directions for future research.

2.Problem Definitions

This section is comprised of four subsections: the first introduces the underlying scheduling problem and each of the subsequent three subsections formulates a different version of the rescheduling problem. The first version includes a cost for each machine reassignment; the second incorporates a constraint to limit the number of such reassignments; and the third minimizes compression costs and introduces a constraint to limit the sum of completion times. We assume that rescheduling is triggered by the arrival of a set of new jobs.

2.1.Rm | xij ≤ uij | ΣCj + Σcijxij

We use the standard three-field classification scheme (i.e., α | β | γ) of Pinedo [14] to denote the scheduling problem as Rm | x_ij ≤ u_ij | ΣC_j + Σc_ijx_ij, where the α field uses Rm to denote m unrelated parallel machines; the β field gives x_ij, the actual amount of time compression for job j on machine i(0 ≤ x_ij ≤ p_ij ); and u_ij, the maximum possible time compression for job j on machine i(0 ≤ x_ij ≤ min (u_ij, p_ij)) ; the γ field specifies the objective, which involves the sum of completion times, C_j, and compression costs for which c_ij denotes the cost per unit time of compressing job j on machine i. This subsection formulates this scheduling problem. Throughout this paper, we use the following notation :

Indices

i machines

j jobs

k sequence positions

Index sets

I unrelated parallel machines; I = {1, ⋯, m }

J jobs to be processed; J = {1, ⋯, n}

K sequence positions; K = J

Parameters

C_j completion time of job j

c_ij cost per unit time of compressing job j on machine i

p_ij normal (i.e., uncompressed) processing time of job j on machine i

u_ij maximum possible time compression of job j on machine i

Decision variables

x_ij amount of processing time compression of job j on machine i (i.e., actual processing time is (p_ij - x_ij))

y_ijk 1 if job j is scheduled as the k^th to last job on machine i, 0 otherwise.

For this scheduling problem, Alidaee and Ahmadian [5] proved the following Proposition, which is based on a result of Vickson [20] :

Proposition In the Rm | x_ij ≤ u_ij | ΣC_j + Σc_ijx_ij scheduling problem, there exists an optimal schedule in which x_ij = 0 if c_ij ≥ k and x_ij = u_ij if c_ij < (i.e., its processing time is not changed or fully compressed from the normal processing time (p_ij), depending on the sequence position of the job.) (Proof. see [5]). □

Based on the Proposition, the underlying scheduling problem can be formulated by extending the Rm | ΣC_j scheduling model as follows [17] :

Objective function (1) minimizes the sum of completion times and compression costs. Constraints (2) assure that each job is scheduled exactly once and (3) assure that each position on each machine is taken by at most one job. Constraints (4) require all decision variables to be nonnegative. Problem P (0) is the well-known assignment problem, which is totally unimodular, so that an optimal integer solution can be prescribed by linear programming in polynomial time.

2.2.Rm | xij ≤ uij, ai | ΣCj + Σcijxij + Σj ∈ JR wij Dij

We assume that a disruption occurs when a (index) set J_N of new jobs arrives at time t as a schedule for the (index) set of original jobs, J_o , is ongoing. In particular, jobs in (index) set J_P are in process at time t, each on a scheduled machine, which will become available only after completing the job it is processing.

For example, in <Figure 1>, a set of new jobs arrives at time t, machines q and r are processing scheduled jobs, which have remaining processing times a_q and a_r , respectively. In this case, machines q and r will be available at times t + a_q and t + a_r, respectively. Upon arrival of a set of new jobs, delete the sets of completed (J_C) and in-process (J_P) jobs from J_o, and re-index remaining jobs in set J′ ={J_o\ (J_P∪J_C)}∪J_N. Without loss of generality, we assume throughout this paper that a set of new jobs arrives at time 0.

In this and the following subsections, we formulate important variations of the rescheduling problem. First, we introduce some additional notation :

J_R index set of originally scheduled jobs remaining after deleting in-process and completed jobs; J_o\ (J_P∪J_C)

J_N index set of newly arrived jobs

J′ index set of jobs to be rescheduled; J_R∪J_N

i_j machine to which job j ∈ J_R is assigned in the initial schedule

a_i time at which machine i will be available, given that new jobs arrive at time 0

w_ij cost of reassigning job j ∈ J_R onto machine i ∈ I \{i_j}

D_ij 1 if job j ∈ J_Ris reassigned onto machine i ∈ I \ { i_j}, 0 otherwise.

We penalize the amount of inconvenience reassignments cause as a part of the objective function or limit the permissible number of reassignments (i.e., amount of inconvenience) by incorporating a constraint. For example, failure to meet a delivery date may affect customer goodwill to a degree that is hard to estimate and, therefore, the amount of inconvenience can be limited by incorporating a constraint to restrict the number of reassignments permitted. However, if machine reassignment incurs additional costs that can be relatively easily valued, the objective function can reflect the trade-off between the costs associated with rescheduling and inconvenience.

The first version of the rescheduling problem can be designated by Rm | x_ij ≤ u_ij, a_i | ΣC_j +Σc_ijx_ij + Σ_{j ∈ JR} w_ijD_ij, which includes an additional measure, Σ_{j ∈ JR}w_ijD_ij, the total weighted cost of reassigning jobs in set J_R , each of which had been scheduled originally on a different machine. To clarify, the reschedule can assign job j to the same machine (i_j) on which it had been scheduled or reassign it to a different machine (i ∈ I \{i_j}). We assume that a job that is being processed when rescheduling occurs remains on the machine that is processing it and its processing time is not compressed.

Since the symbol a_i in the β field represents the time at which machine i will be available; a_i = 0 if machine i is not processing a job when the set of new jobs arrives at time 0. If a job j ∈ J_R is reassigned, Σ_{i ∈ I\ {ij}}D_ij = Σ_i ∈ I\ {i_j}Σ_k ∈ J y_ijk = 1; otherwise, job j remains assigned to machine i_j according to the original schedule, so that Σ_i ∈ I\ {i_j}D_ij = Σ_i ∈ I\ {i_j}Σ_k ∈ J y_ijk = 0 Rescheduling problem Rm | x_ij ≤ u_ij, a_i | ΣC_j +Σc_ijx_ij + Σ_j ∈ J_Rw_ijD_ij can be formulated as assignment problem P(1).

s.t. (2)-(4).

Constraints are those of the assignment problem, so that P(10) can be solved in polynomial time.

2.3.Rm | xij ≤ uij, ai, Σj ∈ JRDij ≤ U | ΣCj + Σcijxij

When the cost of reassignment, (e.g., w_ij in P(1)), is difficult to estimate, it may be more appropriate to limit the number of jobs reassigned by imposing a constraint. This version of the rescheduling problem incorporates a constraint to impose a limitation, U , to restrict machine reassignments.

P 2 : Min ∑ i ∈ I ∑ j ∈ J ∑ k ∈ K kp ij + a 1 + min 0 , c ij − k u ij y ijk

s.t. (2)-(4).

Constraint (6) invokes the reassignment limitation. This APSC does not possess the unimodularity property; it is NP-hard [16].

2.4.Rm | xij ≤ uij, ai, ΣCj ≤ T | Σcijxij

In this subsection, we consider that compressible processing times can provide flexibility for rescheduling by managing processing times. Rescheduling upon the arrival of a set of new jobs may increase the sum of completion times, even of originally scheduled jobs. Furthermore, it may be important to allow processing time compression to satisfy customer demands in a more timely manner; thus, total cost may increase due to time compression.

This problem can be designated by Rm | x_ij ≤ u_ij, a_i,ΣC_j ≤ T | Σc_ijx_ij, which invokes limit, T , on the sum of completion times. To formulate this problem as an integer program, we introduce the following decision variables, assuming that all processing and compression times are integers.

y_ijkl 1 if job j is scheduled as the k^th to last job on machine i and its time compression is the integer value l , 0 otherwise

We also formulate this problem as an APSC as follows :

P (3):

where U_ij denotes the set of possible compression times for job j on machine i(i.e., U_ij = {0, 1, ⋯, u_ij}). Objective function (7) minimizes the total cost of processing time compression. Constraints (8) and (9) assure that each job is scheduled exactly once and each position on each machine is taken by at most one job, respectively. Constraint (10) assures that the sum of completion times does not exceed the limit, T . P(3) has also an additional constraint (10) that makes this problem NP-hard [16].

3.The Linear Relaxation Heuristic

In this section, we propose a heuristic, the Linear Relaxation Heuristic (LRH), which is based on the linear relaxations of p(2) and p(3) . Our LRH can be applied to any model that possesses the totally unimodular property, augmented with a single side constraint. It solves the linear relaxation once and combines the logic of sensitivity analysis applied to the right hand side (RHS) of the side constraint with the fact that all extreme points are 0, 1 integer vectors. Note that sensitivity analysis of the RHS specifies the amount by which the RHS value can change before the current basis changes.

To explain the idea of our heuristic, we present an example with feasible region F = {(x₁, x₂, x₃) | x₁ + x₂ + x₃ ≤ 2.5, x₁ ≤ 1, x₂ ≤ 1, x₃ ≤ 1, x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0} and cost vector c = (- 0.5, - 1, - 1). <Figure 2> shows that the hyperplane represented by the first constraint in the definition of F cuts through the (unit hypercube) polytope described by the other inequalities, forming three fractional extreme points (i.e., (0.5, 1, 1), (1, 0.5, 1), and (1, 1, 0.5)).

In <Figure 2>, as the RHS of inequality x₁ + x₂ + x₃ ≤ 2.5 is gradually decreased, the basis does not change but the objective value slowly increases until the RHS reaches the value 2 and the translated hyperplane (represented by the dotted lines) intersects extreme points (0, 1, 1), (1, 0, 1), and (1, 1, 0). Since sensitivity analysis of the RHS provides lower and upper bounds on the RHS coefficient within which the current basis remains optimal, we can use it to determine how much the RHS must change to translate the hyperplane far enough to intersect an adjacent, extreme point, which must be integer, because the underlying polytope is, by assumption, totally unimodular. Like APSC, all extreme points of feasible region F are composed of 0, 1 integer vectors except any fractional extreme points formed by the additional constraint.

Our heuristic solves the linear relaxation of APSC once, then performs a sensitivity analysis of the RHS to determine the value that changes the basis, equivalently, translates the hyperplane until it intersects at least one feasible, integer extreme point of the assignment polytope. If the solution is fractional, the RHS value of the side constraint is replaced with the lower bound of the range and then the heuristic finds an adjacent extreme-point solution by multiplying the inverse of the current basis by the replaced RHS vector. Since the constrained optimal solution to APSC is not always adjacent to the current fractional solution, the heuristic does not always guarantee the optimal solution.

Let z*_LP, δ*, and l ≤ R ≤ u denote the optimal solution value, the optimal dual variable value corresponding to the side constraint, and the sensitivity range for the RHS value R of the side constraint in the linear relaxation of APSC, respectively.

Property If l = R or l ≠ R and δ* = 0, the current solution is optimal for the APSC.

Proof. If l = R , the side constraint intersects the underlying polytope at an optimal integer extreme point. Now, suppose l ≠ R and δ* = 0. If the RHS of the side constraint in APSC is decreased by R - l , the new objective value is z*_LP + δ* (L - R) . Since δ* = 0, there is no change in the objective value. This happens when the side constraint is redundant (e.g., if the orientation of the objective function is such that the solution to the linear relaxation is an integer extreme point).

Letting B and 1 R be the optimal basis of the linear relaxation of APSC and RHS vector with R as the RHS value of the side constraint, respectively, we now detail LRH in application to solve APSC.

LRH Solve the linear relaxation of APSC. If infeasible, STOP : APSC is infeasible. Else, Apply sensitivity analysis to determine lower and upper bounds for the RHS coefficient of the side constraint, l ≤ R ≤ u, that allow the current basis to remain optimal,

If the solution is integer, STOP : current solution is optimal.

Else, compute B − 1 1 l to find the new extreme-point solution.

4.Computational Evaluation

In this section, we evaluate the efficacy of LRH using randomly generated instances of problems p(2) and p(3). We program LRH, using the C/C++ language and the CPLEX 12.1.0 callable library, and perform all computations on a Dell PC running Windows 7 with a 2.67 GHz CPU and 2 GB memory. The first subsection describes test instances and the second relates test results.

4.1.Instance Generation

This section reviews instance generation. For problem p(2) , our tests involve three factors, the numbers of machines, old jobs, and new jobs with three levels of each factor : 2, 5, and 10; and 100, 200, and 600; and 10, 50, and 100; respectively. This results in 27 cases as shown in <Table 1> and we generate 20 instances of each randomly.

We generate each independent instance randomly using the discrete uniform distribution (DU); DU [10, 110] for processing times (p_ij), costs of processing time compressions (c_ij), and machine available times (a_i); DU [0, 0.5 × p_ij ], for the maximum possible processing time compressions (u_ij); and, finally, DU [0.2 × |J_R |, 0.8 × |J_R |] for the machine reassignment limit (U) in which |J_R| denotes the number of old jobs to be rescheduled.

For problem p(3) , we consider the first factor with three levels (2, 5 and 10 machines) but limit the second and third factors to one level (100 old and 50 new jobs) because this problem incorporates variables with four indices and, hence, causes memory issues if more jobs are involved. <Table 2> displays those instances.

Again, we generate 20 independent instances for each case as described above, except that we generate the limit on the sum of completion times as follows

T = DU 0.6 × t min , 0.9 × t min

where t_min = Min{Σ_{i ∈ I} Σ_{j ∈ J} Σ_{k ∈ J} Σ_{l ∈ Uij} k p_ij y_ijkl : s.t. (8), (9) and (11)} (i.e., the minimum value of the sum of completion times when processing time compression is disallowed). Depending on the value of t_min, problem (3) can be infeasible. Thus, we repeat instance generations until we get 20 feasible instances.

4.2.Computational Results

All computational results are averages taken over the 20 instances associated with each case. <Table 3> displays test results for cases 1 through 27. Column N_opt gives the number of instances out of 20 that our heuristic solves to optimality. Columns RD_avg , RD_max , and RD_min provide average, maximum, and minimum relative deviations from the optimal value, respectively.

The relative deviation RD is computed as follows : RD = z H − z IP z IP × 100 in which z_H and z_IP denote the objective value of LRH and the optimal solution, respectively. Columns TR_avg , TR_max , and TR_min , give average, maximum, and minimum values of CPLEX run time divided by LRH run time, respectively. The last column gives T_avg , the average run time of LRH in each case.

Rows 1~9, 10~18, and 19~27 give results for 2, 5, and 10 machines, respectively. The underlined rows following rows 9, 18 and 27 report the average number of optimal solutions out of 20, RD_avg and TR_avg for all instances involving 2, 5, and 10 machines, respectively.

LRH optimally solves about 78.9% of our test instances. For remaining instances, it provides near-optimal solutions, resulting in an average relative deviation over all test instances of 0.06%. Column TR_avg shows that LRH solves instances about 3.7 times faster than CPLEX, on average. In particular, LRH solves instances that have many jobs relative to the number of machines much faster than CPLEX. For example, LRH solves case 9 about 9.8 times faster than CPLEX, on average.

We also compare cases in which the ratio of the number of old jobs to the number of new jobs is relatively high with cases for which the ratio is small, in particular, equal to 1. For this test, we adapt medium-sized cases 11, 14, and 17, which all have 50 new jobs but 100, 200, and 600 old jobs, giving ratios of 2, 4 and 12, respectively. To specify new cases, 11^d, 14^d, and 17^d, we change the numbers of old and new jobs, keeping the same total number of jobs in each case (150, 250 and 650, respectively), to make each ratio equal to 1, resulting in 75, 125, and 325 old as well as new jobs in these cases, respectively.

<Table 4> assesses the difference that the ratio of the number of old jobs to the number of new jobs makes on run time and solution quality by comparing cases 11, 14, and 17 with cases, 11^d, 14^d, and 17^d, respectively. Columns, T_avg, T_max , and T_min , give average, maximum, and minimum values of LRH run time, respectively. <Table 4> shows that neither the run time nor the solution quality of our heuristic is affected by the ratio of the number of old jobs to the number of new jobs, even though the ratios differ widely.

<Table 6> gives test results obtained for cases 28, 29, and 30. These results show that very few of instances are solved optimally but that average relative deviation barely exceeds 1%. However, LRH solves test instances about 25 times faster than CPLEX, on average.

We use cases of problem P(3) to test the sensitivity of our heuristic relative to the values of the objective function and the RHS coefficients. Run time of the heuristic proposed by Lieshout and Volgenant [12] double if the ranges of coefficients double. Thus, we double the values of the coefficients of the objective function and the RHS to define cases cases, 28^d, 29^d, and 30^d, respectively, then generate 20 independent instances of each case to compare test results with cases 28, 29, and 30, respectively.

<Table 6> compares results associated with cases i and i^d for i = 28, 29, 30. The first six columns and the last three columns correspond to those of <Table 2> and <Table 4>, respectively. <Table 6> shows that solution qualities (i.e., RD_avg, RD_max , and RD_min) and T_avg for classes i and i^d, i = 28, 29, 30 are almost the same, even though coefficients of the objective function and the RHS are doubled in the latter three cases. We have similar results for problem P(2).Table 5

5.Conclusions and Recommendations for Future Research

This paper addresses the problem of rescheduling on unrelated parallel machines with compressible processing times, where the objective is to minimize the sum of completion times, compression costs, and, perhaps, job reassignment costs. We formulate this problem as an APSC, and we introduce a heuristic for problems of this type.

Tests show that our heuristic solves some 78.9% of our randomly generated test instances for cases 1 through 27 to optimality, providing near-optimal solutions for all test instances, and requires much shorter run time than CPLEX, especially on instances of problem P(3) : Rm | x_ij ≤ u_ij, a_i, ΣC_j ≤ T | Σc_ijx_ij. Furthermore, our tests show that our heuristic is not sensitive to the values of objective function coefficients or of the RHS coefficient of the side constraint. Tests show that our heuristic resolves rescheduling problems effectively and that it can be applied to find a good solution quickly for cases in which finding an optimal solution may require prohibitive run time.

Our heuristic can be also applied to any problem with a set of constraints that possesses the unimodular property, augmented with a side constraint. We plan to test such numerical instances. In addition to this, we will try to modify our heuristic to solve APSC with multiple side constraints, perhaps by aggregating them.