Scheduling with tool changes to minimize total completion time under controllable machining conditions

doi:10.1016/j.cor.2005.08.014

Computers & Operations Research

Volume 34, Issue 7, July 2007, Pages 2130-2146

https://doi.org/10.1016/j.cor.2005.08.014 Get rights and content

Abstract

Scheduling under controllable machining conditions has been studied for some time. Scheduling with tool changes, particularly due to tool wear, has just begun to receive attention. Though machining conditions impact tool wear and induce tool change, the two issues have not been considered together. We address for the first time the problem of scheduling a computer numerically controlled (CNC) machine subject to tool changes and controllable machining conditions; our objective is to minimize the total completion time of a given set of jobs. We establish an important result that helps us identify feasible settings of machining parameters such as feed rate and cutting speed. However, the problem at hand remains intractable, even when a single setting is used. In the general case, we are able to solve the problem exactly for up to 30 jobs using a mixed integer linear programming formulation. For larger problems, we turn to approximate solution via heuristics. We examine a number of different schemes. The best of these schemes are used in a problem space genetic algorithm; this produces quality solutions in a time-efficient manner, as is evidenced from an extensive computational study conducted by us.

Introduction

Flexibility is a key to the success of a modern manufacturing system, which is required to deliver diverse products with high quality and short lead times. This flexibility is often achieved through the use of a computer numerically controlled (CNC) machine and is limited only by how effectively resources such as pallets, fixtures and tools are allocated to this machine. Effective tool management, which accounts for a high percentage of the operating costs in an automated manufacturing environment, is of particular importance. Thus, a scheduling model that appropriately incorporates tool management issues can significantly improve the productivity of a flexible manufacturing system.

In this study, we address a single machine scheduling problem under controllable machining conditions and subject to tool changes. Recently, Akturk et al. [1] have focused on a scheduling problem with tool changes caused by wear, but they have assumed that the processing times of the jobs and the tool life are constants. However, by changing the machining conditions, it is possible to control these two values and obtain a better schedule.

The cutting speed and the feed rate are the typical machining parameters that constitute the machine settings. An increase in either one of them decreases the processing time of a job but simultaneously increases the tool usage (which in turn decreases the life of a cutting tool and causes an early tool change). Thus, from a scheduling point of view, there is a tradeoff here. Increased cutting speed or feed rate, while expediting the jobs in process, delays the subsequent jobs due to the more frequent tool changes induced by the increased tool usage. Hence, the machining conditions, cutting speed or feed rate, need to be adjusted properly for each job in order to optimize a scheduling objective that involves the job completion times. Considering the processing times and the tool usage rates of the jobs as consequences of the controllable machining conditions rather than constants, a better integration of tool management and scheduling is achieved.

The tool change time is generally long relative to processing times and the tool life is short relative to the planning horizon. Therefore, it makes sense to schedule the jobs with respect to a completion time-related scheduling objective. We focus here on minimizing the total job completion time, as has been done by Akturk et al. [1].

The literatures on tool management and scheduling are unfortunately disjoint. Machining conditions optimization and tool replacement strategies are studied under tool management, whereas issues related to controllable processing times and machine availability are covered under scheduling. To the best of our knowledge, the interaction between these two streams has not been addressed by researchers thus far.

The optimization of the machining conditions for a single operation is a well-known problem, where the decision variables are usually the cutting speed and the feed rate. Petropoulos [2] has used geometric programming, whereas Khan et al. [3] have proposed local search algorithms for machining conditions optimization. These models consider only the contribution of machining time and tooling cost to the total operating cost and usually ignore the contribution of the nonmachining time components. Tool replacement, which also depends on machining conditions, is a typical example of a nonmachining activity. Note further that the machining conditions optimization models do not address scheduling at all.

A tool replacement strategy specifies a tool change schedule based on the economic service levels of the tools. Tang and Denardo [4] have studied the single machine case with given tool requirements, where the tool changes are required due to part mix. Their objective is to minimize the number of tool switches. Hertz et al. [5] have also considered minimizing tool switches on a flexible machine when scheduling different part types. They have proposed several heuristics for the tool loading problem. Despite the studies on tool loading, tools are usually changed more often because of tool wear than part mix, as reported by Gray et al. [6]. Note also that scheduling is not a concern here either.

Processing time control and its impact on sequencing decisions and operational performance have received limited attention in the scheduling literature. Trick [7] has focused on assigning single-operation jobs to identical machines while simultaneously controlling the processing speed of each machine. Zdrzalka [8] has dealt with the problem of scheduling jobs on a single machine in which each job has a release date, a delivery time and a controllable processing time. Karabati and Kouvelis [9] have solved the simultaneous scheduling and optimal processing-times selection problem in a flow line operated under a cyclic scheduling policy. Jansen and Mastrolilli [10] have proposed approximation schemes for parallel machine scheduling problems with controllable processing times. Finally, Shabtay and Kaspi [11] have studied a single machine weighted flow time problem subject to resource consumption and limited resource availability. Note that this line of research considers neither tool usage nor tool replacement.

Machine availability models in scheduling come closest to considering the tool replacement issue. Adiri et al. [12] have considered a flow time scheduling problem where a machine faces breakdowns at stochastic time epochs and the repair time is stochastic. The processing times are assumed constant and the jobs are assumed nonresumable. Lee and Liman [13] have studied the deterministic version of this problem considering only a single scheduled maintenance, whereas Liao and Chen [14] have considered the case where there are several maintenance intervals. Schmidt [15] has reviewed results on scheduling under availability constraints and analyzed the complexity of single and multiple machine problems under completion time and due date-related criteria. Note that this area of research does not address processing time control.

The purpose of this paper is to propose a model linking machining conditions control, tool replacement and job scheduling on a CNC machine. As pointed out earlier, this has not been done before. We present solution strategies to a scheduling problem where the job processing times and the tool usage are controlled by setting the cutting speed and/or the feed rate. There is a single production unit (the CNC machine), and the cutting tools are subject to wear and require replacement. Our objective, once again, is to minimize the total job completion time.

We first provide the notation used by us throughout the paper. We then discuss the issue of machining conditions control, proving an important result along the way, and show how one can identify a set of feasible settings for each job. Next, we give a mixed integer program (MIP), which assigns an optimal machine setting to each job and finds the optimal schedule of the jobs as well. We go on to propose single-pass heuristic algorithms and test their performance on a set of randomly generated problems. We also propose a problem space genetic algorithm (PSGA) to improve the solution quality. In PSGA, a base heuristic (which is called many times within the algorithm) needs to be defined. We use as base heuristics some of our single-pass heuristics that result in high performance at low CPU time.

Section snippets

Notation

The notation used throughout the paper is as follows:

$α, β, γ$	speed, feed, depth of cut exponents for the tool
$C_{m}, b, c, e$	specific coefficient and exponents of the machine power constraint
$C_{s}, g, h, l$	specific coefficient and exponents of the surface roughness constraint
C	Taylor's tool life expression parameter
$C_{o}$	operating cost of the CNC machine ($/min)
$C_{t}$	cost of the tool ($)
$d_{i}$	depth of cut for job i (in)
$D_{i}$	diameter of the generated surface for job i (in)
$L_{i}$	length of the generated surface for job i (in)
H	maximum

Problem definition

We are given N jobs with a specified depth of cut, length and diameter of the generated surface along with maximum allowable surface roughness attributes. The problem is scheduling these jobs on a CNC machine in order to minimize the total completion time. When the tool life is over, the tool has to be changed. Since there is a constant tool change time, sometimes significant, and it affects the completion time, it is important to consider it in the schedule. The machining conditions of the CNC

MIP formulation

The following mathematical model can be used to assign a feasible setting to each job and schedule these jobs in order to minimize the total completion time. $\begin{matrix} \min & \sum_{i = 1}^{N} \sum_{j = 1}^{S} \sum_{k = 1}^{N} (N - k + 1) P_{ij} X_{ijk} + T_{c} & \sum_{k = 1}^{N - 1} (N - k) R_{k}, \\ s.t. & \sum_{j = 1}^{S} \sum_{i = 1}^{N} X_{ijk} = 1, & k = 1, \dots, N, \\ \sum_{j = 1}^{S} \sum_{k = 1}^{N} X_{ijk} = 1, & i = 1, \dots, N, \\ \sum_{i = 1}^{N} \sum_{j = 1}^{S} U_{ij} X_{ijk} + Y_{k - 1} - Y_{k} ⩾ 0, & k = 1, \dots, N - 1, \\ Y_{k} - \sum_{i = 1}^{N} \sum_{j = 1}^{S} U_{ij} X_{ijk} - Y_{k - 1} + R_{k} ⩾ 0, & k = 1, \dots, N - 1, \\ \sum_{i = 1}^{N} \sum_{j = 1}^{S} U_{ij} X_{ijk + 1} + Y_{k} ⩽ 1, & k = 1, \dots, N - 1, \\ X_{ijk} \in {0, 1}, & i = 1, \dots, N, j = 1, \dots, S, k = 1, \dots, N, \\ R_{k} \in {0, 1} and Y_{k} ⩾ 0, & k = 1, \dots, N - 1, \end{matrix}$ where $X_{ijk} =$ 1 if job i under setting j is scheduled at

Proposed heuristic algorithms

Akturk et al. [1] proved the NP-hardness of their problem which is a sub-problem of ours. Therefore, noalgorithm is likely to be proposed for solving our problem optimally in polynomial time. Hence, it is justifiable to try heuristic methods to solve our problem.

In order to ease the determination of job sequence, the following structural properties showed by Akturk et al. [1] will be used in the heuristic algorithms.

Let $p_{i}$ be the machining time of job i, $t_{m}$ be the aggregate machining times of

Computational results

The single-pass algorithms and PSGA are coded in C language and compiled with Gnu C compiler. The MIP formulations for the original problem and the knapsack formulation used in the third stage of the single-pass heuristics are solved using the callable library routines of CPLEX MIP solver. There are four experimental factors that can affect the efficiency of the algorithms, which can be seen in Table 1. The experimental design is a $2^{4}$ full factorial design. In addition, we consider two

Conclusion

We have addressed a single machine scheduling problem where job processing times and tool usage can be controlled by selecting the appropriate machining conditions; our objective has been to assign a machine setting to each job and to schedule the jobs such that the total job completion time is minimized. In the process, we have proved an important result that has helped us identify the feasible settings for a job in terms of the cutting speed alone. Given the feasible settings for each job, we

References (17)

M.S. Akturk et al.
Scheduling with tool changes to minimize total completion timea study of heuristics and their performance
Naval Research Logistics
(2003)
P. Petropoulos
Optimal selection of machining variables using geometric programming
International Journal of Production Research
(1973)
Z. Khan et al.
Machining condition optimization by genetic algorithms and simulated annealing
Computers and Operations Research
(1997)
C.S. Tang et al.
Models arising from a flexible manufacturing machine, part Iminimization of the number of tool switches
Operations Research
(1988)
A. Hertz et al.
Heuristics for minimizing tool switches when scheduling part types on a flexible machine
IIE Transactions
(1998)
A.E. Gray et al.
A synthesis of decision models for tool management in automated manufacturing
Management Science
(1993)
M.A. Trick
Scheduling multiple variable-speed machines
Operations Research
(1994)
S. Zdrzalka
Scheduling jobs on a single machine with release dates, delivery times and controllable processing timesworst case analysis
Operations Research Letters
(1991)

There are more references available in the full text version of this article.

Cited by (27)

Adaptive neighborhood simulated annealing for sustainability-oriented single machine scheduling with deterioration effect
2021, Applied Soft Computing
This research considers the realistic phenomenon of cutting tool deterioration in the scheduling of jobs and tool replacement activities to ensure sustainable machining operations. Typically, each job has a basic processing time (independent of tool deterioration) and a tool age-dependent prolongation function. Nevertheless, such a strategy may replace the cutting tools before its useful lifespan to avoid longer processing time as it leads to higher energy consumption and likelihood of tardy jobs. Given the reduced tool operating duration, the prospect of exploiting its capability to limit the processing time prolongation is not considered by prior works. In this research, a single-machine scheduling approach that determines the job processing time based on tool age and operating duration (utilization) is studied. The problem is formulated as a mixed-integer linear program (MILP) with the objective of minimizing the weighted costs of energy consumption, tooling, and job tardiness. Due to its computational complexity, a new variant of simulated annealing (SA) algorithm is proposed to solve large instances, where an adaptive strategy is utilized to determine the neighborhood size for enhanced exploration and exploitation. Computational results for an exhaustive set of instances indicate the proposed scheduling strategy to always outperform the existing method, yielding up to a 43% reduction in total cost. Besides, the proposed variant of SA effectively solves the scheduling problem and consistently dominates the traditional SA method.
Cloud manufacturing – Scheduling as a service for sheet metal manufacturing
2019, Computers and Operations Research
Citation Excerpt :
Tool change and setup problem with wearing parts (Giannakakis & Vosniakos, 2008). Flow shop scheduling problem (Akturk et al., 2007). Several quantitative analytical approaches have been presented to solve these problems related to production planning and control.
Cloud manufacturing refers to a new concept of using centralized cloud computing for manufacturing information systems to support distributed and dynamic collaborative manufacturing environment. The core of cloud manufacturing is to provide service to geographically distributed manufacturers centralized services. This paper introduces a cloud based production scheduling system for sheet metal manufacturing and discusses the requirements of scheduling as a service. A genetic algorithm based scheduling application has been developed to serve distributed manufacturing lines in form of cloud manufacturing. The characteristics of the prototype system are described and performance estimates are tested.
Total completion time minimization for machine scheduling problem under time windows constraints with jobs’ linear processing rate function
2018, Computers and Operations Research
In this paper, we consider an identical parallel machine scheduling problem with a single additional resource. The processing rate of a job is defined by a linear resource consumption function. The addressed problem takes into consideration two new constraints. The first is the time-varying total available resource. The second new constraint limits the resource consumption incrementation of each job on two consecutive periods of time. Moreover, jobs have bounded resource consumption, arrival times and deadlines. Many practical applications, such as the electrical charging scheduling, can find interests in our works. Our contributions are two-folds. First, we introduce a Mixed-Integer-Linear-Program (MILP) to formulate the problem. Then, we present a heuristic consisting of two phases: a feasible solution construction phase using geometrical strip packing and a solution improvement phase. The heuristic is proven to be very efficiency for dealing with the problem throughout the numerical experiments.
Scheduling two parallel machines with machine-dependent availabilities
2016, Computers and Operations Research
Citation Excerpt :
For example, the lengths of the available intervals of a machine may be decision variables with a given common upper bound in one scenario while the lengths of the available intervals of a machine may be prefixed with the same value in another. Although these unavailable intervals can be viewed as machine maintenance periods, these two types of machine availabilities are usually called tool changes [12,18–20] and periodic maintenance [1,3–5,9,10,13] respectively in the literature for both historical reasons and technical reasons. The name tool changes originates from the fact that the tool of a machine must be changed within its life due to tool wear and the tool change activity may be conducted immediately at any time.
A two-parallel-machine scheduling problem with machine-dependent availabilities where one machine is subject to tool changes and the other is subject to periodic maintenance is considered. The objective is to determine the start time of each tool change activity and schedule all the jobs to the two machines such that the makespan is minimized. Due to the NP-hardness of the non-approximability of the problem, there does not exist any polynomial time approximation algorithm with a worst-case ratio less than 2 for the problem unless P=NP. To solve small sized and moderate sized instances of the problem, a mixed 0–1 programming model is proposed. To solve large sized instances of the problem, nine heuristic algorithms that employ two classical dispatching rules, two assignment mechanisms and a post-optimization procedure are proposed. To evaluate the performance of the algorithms, some machine setting featured lower bounds are provided. Computational experiment shows that the average-case relative error ratio of the heuristic algorithm that based on the classical LPT rule, two assignment procedures and a post-optimization procedure is less than 8%, which implies that it is promising for problem and suitable for real-world application.
Minimizing the total completion time on a parallel machine system with tool changes
2016, Computers and Industrial Engineering
Citation Excerpt :
Akturk, Ghosh, and Gunes (2004) discussed the computational complexity of such issue, also providing a worst-case lower bound for the SPT heuristic. Three years later, Akturk, Ghosh, and Kayan (2007) analyzed the effect of tool changes and controllable machining conditions on a CNC workstation under the total completion time minimization objective. The authors proposed a mixed integer linear programming (MILP) formulation able to solve up to 30-job problems, and a problem space genetic algorithm to tackle large-sized instances.
In this paper, the identical parallel machine scheduling problem with periodic tool changes due to wear is addressed under the total completion time minimization objective. Due to machine availability restrictions induced by tool replacement operations, the problem is NP-hard in the strong sense. A mixed integer linear programming (MILP) model has been developed with the aim to provide the global optimum for small-sized test cases. Furthermore, a hybrid metaheuristic procedure based on genetic algorithms has been specifically designed to cope with larger instances. A comprehensive experimental analysis supported by a non-parametric statistical test has been fulfilled to select the best metaheuristic configuration in terms of decoding strategy and parameters driving the search mechanism as well. Then, the proposed optimization procedure has been compared with three alternative methods arising from the relevant literature on the basis of a wide benchmark of test cases. The obtained results, also supported by a proper statistical analysis, demonstrate the effectiveness of the proposed approach for solving the tool change scheduling problem at hand.
Batch scheduling of identical jobs with controllable processing times
2014, Computers and Operations Research
Citation Excerpt :
Various versions of this very practical scheduling setting have been studied by many researchers, as reflected in the recent survey of Shabtai and Steiner [3]. Some of the early papers are: Van Wassenhove and Baker [4], Nowicki and Zdrzalka [5], Janiak and Kovalyov [6], Wan et al. [7], Hoogeveen and Woeginger [8], Janiak et al. [9], Shakhlevich and Strusevich [10], Wang [11] Akturk et al. [12] and Wang and Xia [13]. More recently, Tseng et al. [14] studied a single machine setting with controllable processing times and an objective of minimum total tardiness; Turkcan et al. [15] studied a setting of parallel machines and objective functions of minimum manufacturing cost and total weighted earliness and tardiness; Shakhlevich et al. [16] focused on the trade-off between the maximum cost (which is a function of the completion times) and the total compression cost; Shabtay et al. [17] addressed due date assignment problems in a group technology environment; Gurel et al. [18] considered failures of the machine and repair time, and focused on an anticipative scheduling approach; Wan et al. [19] studied the problem of scheduling jobs of two-agents on a single machine with controllable processing times; Choi et al. [20] focused on minimizing weighted completion time subject to an upper bound on the maximum compression cost; Leyvand et al. [21] considered just-in-time scheduling on parallel machines; Yin and Wang [22] studied a model combining controllable processing times and learning; Wang and Wang [23] addressed the single machine problem of minimizing the total resource consumption subject to an upper bound on the total weighted flowtime; Wei et al. [24] focused on a model in which the job processing times are a function of both resource consumption and the job starting times; Uruk et al. [25] studied a two-machine flowshop problem with flexible operations and controllable processing times; and Wang and Wang [26] focused on convex resource dependent processing times and job deterioration.
In scheduling models with controllable processing times, the job processing times can be controlled (i.e. compressed) by allocating additional resources. In batch scheduling a large number of jobs may be grouped and processed as separate batches, where a batch processing time is identical to the total processing times of the jobs contained in the batch, and a setup time is incurred when starting a new batch.
A model combining these two very popular and practical phenomena is studied. We focus on identical jobs and linear compression cost function. Two versions of the problem are considered: in the first we minimize the sum of the total flowtime and the compression cost, and in the second we minimize the total flowtime subject to an upper bound on the maximum compression. We study both problems on a single machine and on parallel identical machines. In all cases we introduce closed form solutions for the relaxed version (allowing non-integer batch sizes). Then, a simple rounding procedure is introduced, tested numerically, and shown to generate extremely close-to-optimal integer solutions. For a given number of machines, the total computational effort required by our proposed solution procedure is $O (\sqrt{n})$ , where $n$ is the number of jobs.

View all citing articles on Scopus

View full text

Scheduling with tool changes to minimize total completion time under controllable machining conditions

Abstract

Introduction

Section snippets

Notation

Problem definition

MIP formulation

Proposed heuristic algorithms

Computational results

Conclusion

Scheduling with tool changes to minimize total completion timea study of heuristics and their performance

Naval Research Logistics

Optimal selection of machining variables using geometric programming

International Journal of Production Research

Machining condition optimization by genetic algorithms and simulated annealing

Computers and Operations Research

Models arising from a flexible manufacturing machine, part Iminimization of the number of tool switches

Operations Research

Heuristics for minimizing tool switches when scheduling part types on a flexible machine

IIE Transactions

A synthesis of decision models for tool management in automated manufacturing

Management Science

Scheduling multiple variable-speed machines

Operations Research

Scheduling jobs on a single machine with release dates, delivery times and controllable processing timesworst case analysis

Operations Research Letters