Information Technology Journal

Year: 2008 | Volume: 7 | Issue: 4 | Page No.: 580-589
DOI: 10.3923/itj.2008.580.589

Minimizing Maximum Tardiness in Single Computer Numerical Control Machine Scheduling with Tool Changes

Ming- Cheng Lo, Jen-Shiang Chen and Yi-Chien Chen

Abstract: This study considers the problem of scheduling a set of jobs on a single Computer Numerical Control (CNC) machine where the cutting tool is subject to wear, aiming to minimize the maximum tardiness. Four mixed binary integer programming models were developed to solve this problem optimally. To solve large-sized problems, two heuristics were also developed. This study presents the computational results to demonstrate the efficiency of the models and the effectiveness of the heuristics.

Keywords: Scheduling, heuristics, availability constraints, tool changes, integer programming and single CNC machine

INTRODUCTION

When scheduling jobs on single machine, engineers have always assumed that the machine is continuously available. In practice, however, the machine may be shut down for various reasons, e.g., for preventive maintenance or tool changes. Preventive maintenance is often discussed in literature, but tool changes are discussed less often. For preventive maintenance activities, related literature includes (Lee, 1996; Schmidt, 1988, 2000; Sanlaville and Schmidt, 1998; Graves and Lee, 1999; Blazewicz et al., 2000; Liao and Chen, 2003; Cassady and Kutanoglu, 2003).

Fluctuations in market demands over recent decades imply that manufacturing strategy has switched from high-volume production of narrow product lines to medium-to low-volume batches of many different products. Computer Numerical Control (CNC) is a programmable automation tool that efficiently accommodates product variations and small batch production. Tool change is essential issue in CNC tool management. Previous literature on tool management has addressed this issue, but assumed that the change is due only to the part mix. In practice, however, most tool changes are caused by tool wear (Akturk et al., 2003). This study considers the problem of scheduling a set of jobs on a single CNC machine where the cutting tool is subject to wear.

Liao and Chen (2003) studied a single machine scheduling problem requiring periodic maintenance in a complete schedule. Their study attempted to minimize the maximum tardiness. However, they assumed that each maintenance activity is fixed and known in advance. That is, they studied scheduling with multiple maintenance intervals and fixed time periods between consecutive maintenance activities.

Qi et al. (1999) studied scheduling with multiple maintenance intervals and variable time between consecutive maintenance activities. Their study attempted to minimize total job completion time. Their model is similar to scheduling with tool changes problem as several tool changes can occur over a given time period and the time between tool changes (while bounded by the tool life) can vary. Qi et al. (1999) showed that their proposed problem was strongly NP-hard and presented three heuristics and a branch and bound algorithm to solve the problem. Akturk et al. (2003) studied the same problem for scheduling with tool changes to minimize total completion time. They provided a mixed Binary Integer Programming (BIP) model for the exact solution of the problem and proposed seven heuristics based on simple dispatch rules and generic search. Akturk et al. (2004) considered the same problem as did and briefly described the problem and discussed its properties, complexity and solution. They provided theoretical worst-case bounds on the performance of the Shortest Processing Time first (SPT) list-scheduling heuristic and also demonstrated its empirical behavior.

This study considers a single CNC machine scheduling problem in which processing is interrupted due to tool wear and tool changes and in doing so, attempts to minimize the maximum tardiness. The scheduling problem has multiple maintenance intervals and varying times between consecutive maintenance activities.

PROBLEM DESCRIPTION AND NOTATION DEFINITION

The notation used throughout the study is defined as:

Assume that n independent jobs J₁, J₂, …, J_n are to be processed on a single CNC machine. All jobs are available at time zero and no pre-emption is allowed. The job processing times are constant and known a priori. Only one tool with a known, constant life and an unlimited availability is required. When an active tool wears out, it is replaced with a new one; the time needed for this tool change is also known and constant. The machine must stop and change tool after continuously working for a period of time. The maximum allowed continuously working time of the machine is T_L and the tool change time is T_C. The relation T_L≥p_i (i = 1, 2, …, n) is assumed since otherwise no feasible schedule is available.

Minimizing the maximum tardiness a basic objective studied in the scheduling literature (French, 1982). The EDD (Earliest Due Date) dispatching rule is well-known to produce an optimal schedule in the single machine case if the tool life is considered infinitely long (i.e., no tool change occurs). However, the structure of the problem changes dramatically when tool changes are introduced. The performance of the EDD rule depends on the value of T_C. Notably, the EDD rule here assigns jobs to successive tools in non-decreasing order of their due dates and change tools when no current tool can perform a job.

If the jobs are considered as sharing the same tool as a batch, then a schedule can be viewed as a series of batches of jobs separated by tool changes (Fig. 1). Notably, the batch lengths may vary, because tools are changed when the current tool cannot handle the next job in the sequence. The batch length only shows the portion of the tool which has been used.

Theorem 1: The problem of single CNC machine scheduling with tool changes and the maximum tardiness as the criterion is strongly NP-hard.

Proof: Clearly the problem is strongly NP-hard since a problem that minimizes the maximum tardiness subjectto multiple unavailability intervals and fixed start maintenance time is strongly NP-hard (Liao and Chen, 2003).

INTEGER PROGRAMMING MODELS

Mathematical programming formulation is a natural way to solve machine scheduling problems (Rinnooy Kan, 1976). Most mathematical programming formulations of scheduling problems involve mixed Binary Integer Programming (BIP) in which some variables are binary and the others are continuous. The new development of mixed BIP techniques, along with the substantial progress in computer capacity, strongly impacts mixed BIP scheduling models. In this section, four mixed BIP models are provided for solving the proposed problem. These four models include Models 1-4.

Model 1: All n jobs processed in the symbol are assumed to be J₁, J₂, …, J_n. The tool life T_L is assumed to exceed the processing time of any job. Consequently, a maximum of (n-1) tool changes can occur in the planning horizon. Suppose the (n-1) tool changes in the symbol are J_n+1, J_n+2, …, J_2n-1. Models 1 and 2 are based on the concept of (n-1) tool changes can occur.

The binary variable x_ij used by Model 1 is restricted and specifies the order in which the machine processes jobs. Model 1 employs one-job-one-position to describe the single CNC machine scheduling with tool changes.

Constraint (1) describes the objective function, constraint sets (2) to (5) state in which each job is uniquely scheduled in a position for processing. Constraint sets (6) and (7) show that the situation of the tool changes must not be placed in any particular position. Constraints sets (8) and (9) are essentially definitional, while constraints (10) enforce the precedence relationships. Additionally, constraint sets (11) to (13) give the tool change starting and finishing times. Constraint set (14) defines the tardiness of jobs. Finally, the non-negativity and binary restrictions on T_max, h_j, f_j and C_i and x_ij, respectively, are specified in (15).

Model 2: This model uses the binary variable z_ij to express the ‘either-or` relationship for the non-interference restrictions. Moreover, Model 2 describes the single machine problems using the concept of non-interference.

Constraint sets (17) and (18) define the completion time of job, while constraint (16) defines the total tardiness. Constraint set (19) defines the tardiness of jobs. Moreover, constraint sets (20) and (21) meet the requirement that only one job can be processed at any time, that is, either C_i≤s_j or C_j≤s_i will hold. Incorporating binary variable z_ij and a very large positive number M, Eq. 20 and 21 together ensure that one of these two constraints holds while the other is eliminated. Furthermore, constraint sets (22) and (23) state the maintenance interval. Finally, constraint set (24) specifies the non-negativity of C_i, s_i and T_max and establishes the binary restrictions for z_ij.

Model 3: A new binary variable k_j is defined to be equal to 1 if the tool is replaced after position j and 0 otherwise. The variable r_j tracks the remaining time between the completion time of the job placed in the sequence position j and the latest starting time of the next tool change. Model 3 uses one-job-one-position with n positions to describe single CNC machine problems.

Constraint (25) describes the objective function, constraint sets (26) and (27) state in which each job is uniquely scheduled in a position for processing. Constraint (28) records the remaining life time of the tool which processes the job in the first position. Additionally, constraint sets (29) and (30) meet the requirement that the range of r_j, that is, either

will hold. Incorporating binary variable k_j-1 and a very large positive number M, Eq. 29 and 30 together ensure that one of these two constraints holds while the other is eliminated. Moreover, constraint sets (31) to (33) define the b_j, f_j and T_max, respectively. Finally, constraint set (34) specifies the non-negativity of T_max, r_j, f_j and b_j and establishes the binary restrictions for x_ij and k_j.

Model 4: Model 4 utilizes the variable e_j instead of r_j as used in Model 3. The variable e_j tracks the time elapsed between the completion time of the last new tool change and the completion time of the job in sequence position j.

Constraint (35) describes the objective function, constraint sets (36) and (37) state in which each job is uniquely scheduled in a position for processing. Constraint (38) records the elapsed time of the tool which processes the job in the first position. Additionally, constraint sets (39) and (40) meet the requirement that the range of e_j, that is, either

will hold. Incorporation binary variable k_j-1 and a very large positive number M, Eq. 39 and 40 together ensure that one of these two constraints holds while the other is eliminated. Furthermore, constraint set (41) states the restriction of the tool life. Constraint sets (42) to (44) define the b_j, f_j and T_max, respectively. Finally, constraint set (45) specifies the non-negativity of T_max, e_j, f_j and b_j and establishes the binary restrictions for x_ij and k_j.

COMPARISONS OF THE PROPOSED MODELS

Size complexity denotes the size of a problem in terms of binary variables, constraints and continuous (real) variables as a function of n, the number of jobs, in the problem. Table 1 shows the size complexity of each of the four integer programming models.

French (1982) stated that the speed with which integer programming problems can be solved depends on the number of variables and constraints in the problem, where the most influential factor is the number of binary variables. If two formulations have the same number of binary variables (Wilson, 1989; Liao and You, 1992) demonstrated that the next most influential element is the number of constraints. As Table 1 shows, Model 4 has the same number of binary and continuous variables as that of Model 3, but has n-1 more constraints. Model 1 has 2n²-2 more number of binary variables than Model 2, the former has (-1/2) n² + (15/2) n +more constraints and n more continuous variables. Models 3 and 4 are superior to Models 1 and 2 in terms of number of binary variables, constraints and continuous variables. Consequently, Model 3 is theoretically the best, followed in order by Model 4, Model 2 and Model 1.

THE PROPOSED HEURISTICS

Although the integer programming approach can solve the problem being considered, large problems are difficult to solve without considerable computational efforts. Therefore, this study proposes two heuristic algorithms. Some properties of the optimal schedule of the proposed problem are first introduced.

Theorem 2: (Optimal sequence in the same batch) For two adjacent jobs in the same batch, an optimal schedule exists for which the job with the smaller due date is placed before the other job.

Proof: The result follows immediately from the EDD order.

Let b denote the number of batches required for processing all jobs. B_q denotes batch number q, where q = 1, 2, …, b. The batch number is also the batch-forming sequence.

Theorem 3: (Feasible interchanging) Assume that T_k is the maximum tardiness of a schedule, where T_k>0 (i.e., C_k>d_k) and J_k is in B_q. B_q is not the first batch in the schedule. Denote by J_j a job in the batch preceding B_q. Let BT_k and BT_j be the total processing time of the batch which contains J_k and J_j, respectively. If BT_j-p_j + p_k≤T_L and BT_k-p_k+p_j≤T_L, then a feasible schedule can be obtained by interchanging J_k with J_j.

Proof: The proof is straightforward.

To reduce the maximum tardiness of a schedule, two jobs placed in two batches can be interchanged.

Theorem 4: (Interchange with preceding job) Suppose that T_k is the maximum tardiness of a schedule, where T_k>0 (i.e., C_k>d_k) and J_k is in B_q. B_q is not the first batch in the schedule. Denote by J_j a job in the batch preceding B_q. Suppose that J_i is not placed in B_q and between J_j and J_k. In a feasible schedule, if the following two conditions can be satisfied simultaneously, then a smaller T_max value can be obtained by interchanging J_k with J_j.

Proof: See Fig. 2, from Theorem 2 both jobs J_k and J_j are assumed to be feasibly interchangeable. Let schedule S = (PS_S, J_j, PS₁, J_i, PS₂, J_k, PS_F), where PS_S, PS₁, PS₂ and PS_F are partial schedules. Let S’ be obtained from S by interchanging J_j with J_k, that is, S’ = (PS_S, J_k, PS₃, J_i, PS₄, J_j, PS_F), where PS₃ and PS₄ are also partial schedules. Denote by T_r (S) and T_r (S’) the tardiness of J_r in schedule S and S’, respectively (Fig. 2). Then the tardiness of T_k (S), T_j (S), T_i (S), T_k (S’), T_j (S’) and T_i (S’) are

To reduce the value of T_max = T_k (S), the following three cases must be satisfied simultaneously: (1) T_k (S’)≤T_k (S); (2) T_j (S’)≤T_k (S) or T_j (S’)≤T_j (S); (3) T_i (S’)≤T_k (S) or T_i (S’)≤T_i (S). These three cases can be further discussed in detail as follows.

Case 1: T_k (S’)≤T_k (S).

Obviously, T_k (S’)≤T_k (S) must hold.

Case 2: T_j (S’)≤T_k (S) or T_j (S’)≤T_j (S).

To satisfy T_j (S’) = max{C_k-d_j, 0}≤T_k (S) = max{C_k-d_k, 0}, the following two conditions must be satisfied.

Then, to satisfy T_j (S’) = max{C_k-d_j, 0}≤T_j (S) = max{C_j-d_j, 0}, the following two conditions must also be satisfied.

Case 3: T_i (S’)≤T_k (S) or T_i (S’)≤T_i (S).

To meet T_i (S’) = max{C_i + p_k-p_j-d_i, 0}≤T_k (S) = max{C_k-d_k, 0}, the following two conditions must be met.

Then, to meet T_i (S’) = max{C_i + p_k-p_j-d_i, 0} ≤T_i (S) = max{C_i-d_i, 0}, the following two conditions must also be met.

In summary the conditions (46-49) and the theorem is proved.

Corollary 1: As described in Theorem 4, if J_i does not exist, that is, J_k is in B_q and J_j placed the last position of the batch B_q-1. If the first condition (i) (that is, C_k≤d_j, or C_k>d_j and d_k≤d_j, or C_j>d_j and C_k≤C_j) can be satisfied, then a smaller T_max value can be obtained by interchanging J_k with J_j.

Proof: The proof is straightforward.

Based on the above properties, two heuristic algorithms are proposed. These two heuristics are Heuristic H1 and Heuristic H2. Both heuristics utilize a two-phase method. Phase I focuses on forming batches and Phase II focuses on improving the maximum tardiness. J_[k] denotes the job placed at the kth position and p_[k], d_[k], C_[k] and T_[k] are defined accordingly.

Heuristic H1: Phase I of Heuristic H1 first employs the EDD rule to sequence all jobs and then follows this sequence to form batches. The steps of Heuristic H1 are outlined as follows:

The steps are now elaborated in detail. Clearly that the smallest number of tool changes is obtained in Phase I. Step 8 of Phase II constructs an initial schedule, where jobs are sequenced in the EDD and the tool changes are included. Steps 9 and 10 check whether to stop the algorithm. Step 11 applies Theorem 3 to determine where the interchange of any two jobs is feasible. Step 12 adopts Theorem 4 and Corollary 1 to determine whether any interchange is advantageous. Step 13 obtains the most advantageous interchange.

To calculate the time complexity of Heuristic H1, carry out the bin-packing technique in Phase I in O (nlogn). The complexity of Steps 9 and 10 are O (n). Steps 11 and 12 require . Step 2.6 needs O (nlogn). Thus, the overall time complexity of the proposed heuristic is

Heuristic H2: Phase I of Heuristic H2 first employs the EDD rule to sequence all jobs and then follows this sequence under the minimum number of batches to form batches. The steps of Heuristic H2 are outlined as follows:

Phase II

Phase II of Heuristic H2 is the same as Phase II of Heuristic H1.

Clearly, Phase I produces the smallest number of tool changes. To calculate the time complexity of Heuristic H2, carry out the modified bin-packing technique in Phase I in O (n²logn). Thus, the time complexity of the Heuristic H2 is

COMPUTATIONAL EXPERIMENT

The test problems were divided into two sets, where one consisting of problems for which optimal solutions were known by solving the four optimization models in a reasonable time and the other containing problems for which optimal solutions were not known.

The numerical values of the problem parameters were generated according to the following scheme. For each test problem, the job processing times were randomly generated from a discrete uniform distribution between 5 and 15. The due dates were generated as a function of due date range, R and the tardiness factor, τ. Let T denote the sum of the processing times of all jobs. The due dates of the jobs were from a uniform distribution of integers between T (1-τ-R/2) and T (1-τ + R/2). In the experiment, τ was set at 0.2 and 0.6; R assumed the values of 0.2 and 0.6; T_L was set at 10 and 18; T_C assumed the values of 2 and 4, respectively.

Problems with known optimal solutions: The first set of problems was solved using the above four optimization models. The models were tested using a computer program coded in the ILOG OPL language. Problem parameters and four total models were generated and solved with ILOG CPLEX on an Intel P4/2.67GHz with 512MB SDRAM. The experiment was conducted using three different problem sizes, namely n = 6, 7 and 12. For each problem size, ten replications were produced for each combination of τ, R, T_L and T_C. Table 2 reports on the average computation time for each model in solving the associated problems.

The effectiveness of the two heuristic algorithms is measured by the percentage error defined as:

where, T_max (heu) is the maximum tardiness obtained by the heuristic algorithm and T_max (opt) is the optimal T_max of the schedule. Table 2 also summaries the performance of the two heuristic algorithms on the average percentage error. Table 2 yields the following observations.

For the four models, the computation time increases with increasing number of jobs. Additionally, the relationship between the efficiency of the proposed models and τ is not significant. The average CPU time of Models 3 and 4 decreases with increasing T_L and decreasing T_C. The efficiency of Models 3 and 4 increases with increasing R, while the efficiency of Models 1 and 2 decreases with increasing R. For the proposed problem, Model 1 is the best optimization model in average CPU time, followed by Models 2, 3 and 4. The real data testing results for the models differ from the results of the theoretical analysis.

For the two heuristics, Table 2 shows that problems with smaller τ values generate smaller average percentage errors and spend less computation time. Also, problems with larger T_L value and smaller T_C value were found to produce smaller average percentage error. Moreover, the average percentage error increases as the number of jobs increases. Heuristic H1 spends less computation time than Heuristic H2. Heuristic H2 is better than Heuristic H1 in terms of average percentage error.

Problems with unknown optimal solutions: Since optimal solutions were unknown for these problems, the relative performance is denoted by T_max (H2) /T_max (H1), where T_max (H2) and T_max (H1) are the maximum tardiness values found by Heuristics H2 and H1, respectively. If Heuristic H2 produces a better solution than that Heuristic H1, then its relative performance is less than 1. Table 3 shows the average relative performance values and average percentage error.

Heuristic H2 outperforms Heuristic H1 in terms of average relative performance. The average relative performance T_max (H2)/T_max (H1) is 0.8495 with a maximum of 0.9215. Heuristic H1 spends less computation time than Heuristic H2. Additionally, computation time increases with increasing τ.

CONCLUSIONS

This investigation studied the single CNC machine scheduling problem of minimizing the maximum tardiness with taking account of tool changes. Four mixed BIP models to obtain the optimal solution. These four mixed BIP models are Models 1, 2, 3 and 4. Model 1 is the best optimization model in average CPU time, followed by Models 2, 3 and 4. Two efficient heuristics, Heuristics H1 and H2, were proposed to provide the near-optimal solution for the problem. Performance of the heuristics was evaluated by comparing its solution with the optimal solution derived by the developed mixed BIP models. Several properties associated with the problem have also been investigated and implemented in the algorithm. Heuristic H1 spends less computation time than Heuristic H2. Heuristic H2 is better than Heuristic H1 in terms of average percentage error. The computational results show that the mixed BIP models are inefficient, especially Models 3 and 4. The two heuristic algorithms can improve the maximum tardiness of jobs in terms of percentage error. The heuristics were shown to spend much less computation time than the mixed BIP models. Therefore, the heuristic is applicable for large-sized problems, while the mixed BIP models can only be used for small-sized problems.

Future research should address problems with different shop environments, including flow-shop and job-shop. Problems with other performance measures, including mean tardiness and multi-criteria measures, should also be studied.

ACKNOWLEDGMENT

The author would like to thank the National Science Council of the Republic of China, Taiwan for financially supporting this research under Contract No. NSC93-2213-E-269-003.

REFERENCES