Considering manufacturing cost and scheduling
performance on a CNC turning machine
Sinan Gurel,M.Selim Akturk *
Department of Industrial Engineering,Bilkent University,06800Bilkent,Ankara,Turkey
Received 20March 2005;accepted 21November 2005
Available online 23February 2006
Abstract
A well known industry application that allows controllable processing times is the manufacturing operations on CNC machines.For each turning operation as an example,there is a nonlinear relationship between the manufacturing cost and its required processing time on a CNC turning machine.If we consider total manufacturing cost (F 1)and total weighted completion time (F 2)objectives simultaneously on a single CNC machine,making appropriate processing time decisions is as critical as making job sequencing decisions.We first give an effective model for the problem of minimizing F 1subject to a given F 2level.We deduce some optimality properties for this problem.Based on these properties,we propose a heuristic algorithm to generate an approximate set of efficient solutions.Our computational results indicate that the proposed algo-rithm performs better than the GAMS/MINOS commercial solver both in terms of solution quality and computational requirements such that the average CPU time is only 8%of the time required by the GAMS/MINOS.
Ó2006Elsevier B.V.All rights reserved.
Keywords:Scheduling;Bicriteria optimization;Controllable processing times;CNC machines;Manufacturing cost;Total weighted completion time
1.Introduction
Most of the scheduling literature assume fixed processing times.However,there are many industry appli-cations where we can control the processing times.The best known example is the turning operation on a CNC machine.On a CNC turning machine,we can control the processing time of an operation by controlling the machining parameters.Since the scheduling problems are sensitive to the processing time data,we need appropriate processing time decisions to improve the scheduling objectives.When we consider a regular sched-uling objective,we set processing time of each job as small as possible and then solve the scheduling problem.However,to achieve shorter processing times we have to use more resource.In a turning operation this resource is the cutting tool.As we decrease the processing time of an operation we incur more tooling cost.0377-2217/$-see front matter Ó2006Elsevier B.V.All rights reserved.doi:10.1016/j.ejor.2005.11.029
*Corresponding author.Tel.:+903122901360;fax:+9031226054.
E-mail address:akturk@bilkent.edu.tr (M.S.
Akturk).
European Journal of Operational Research 177(2007)
325–343
This study considers the situation where both total weighted completion time and cost performance are under consideration for a CNC turning machine.In order tofind a set of efficient solutions for this bicriteria prob-lem,wefirst present a mathematical model and derive optimality properties.Then,by utilizing these proper-ties,we propose a new heuristic method to generate a set of approximate efficient solutions.Our results show that by integrating the machine scheduling and process planning decisions,we can generate a set of alternative solutions for the decision maker so that significant time/cost gains can be achieved.
On a CNC turning machine,increasing the cutting speed and/or feed rate decreases the processing time of an operation whereas it increases the tooling cost.Machining parameters selection problem dealing with this tradeoffis a well known problem in the literature.There are many studies in the literature that consider dif-ferent objectives and solution methods.Malakooti and Deviprasad(19)formulated machine parameter selection problem as a multiple objective decision making problem.They considered minimizing cost per part, minimizing production time and minimizing surface roughness objectives.Gopalakrishnan and Al-Khayyal (1991)provided a geometric programming based method to minimize machining and tooling costs.Choi and Bricker(1996)discussed the effectiveness of a geometric programming model in machining optimization problems.Lamond and Sodhi(1997)considered the cutting speed selection and tool loading decisions on a single cutting machine so as to minimize total processing time.Akturk and Avci(1996)propose a solution procedure to make tool allocation and machining conditions selection decisions simultaneously.Kayan and Akturk(2005)provide a mechanism to determine upper and lower bounds for the processing time of a turning operation.
In the scheduling literature,controllable processing time issue has been receiving increasing attention in recent studies.They deal with minimizing the processing cost and a scheduling objective simultaneously. The processing cost of a job is usually defined to be the cost of compressing the processing time of it.The survey of Nowicki and Zdrzalka(1990)lists results for sequencing problems with controllable processing times up to1990.A review on controllable processing times in multi-objective scheduling is included in the recent review by Hoogeveen(2005).Thefirst study in the area is by Vickson(1980a)which considers the objective of minimizing the sum of total processing cost and total completion time on a single machine,and also shows that the problem is polynomially solvable.Chen et al.(1997)show that the discrete controllable case for the same problem is also polynomially solvable.Daniel Ng et al.(2003)additionally consider batching and controllable setup times for the same objective.Vickson(1980b)considers total weighted completion time case which is recently shown to be NP-hard by Wan et al.(2001).Janiak et al.(2005)provide an alternative NP-hardness proof for the same problem and propose a polynomial time approximation algorithm.Karabati and Kouvelis(1997)discuss simultaneous scheduling and optimal processing time decision problem to maximize the throughput for a multi-product,deterministicflow line operated under a cyclic scheduling approach.These studies assumed linear job compression costs.A nonlinear relationship is considered between processing times and production resource by Shabtay and Kaspi(2004).They study a single machine scheduling problem to minimize total weightedflow time subject to a limited resource.Kayan and Akturk(2005)consider the bicri-teria problem of minimizing the makespan and total manufacturing cost simultaneously on a CNC turning machine and provide methods to determine an approximate efficient frontier for the problem.
In the literature,most of the research on scheduling has focused on problems with a single objective.How-ever,in the real world,we usually face a number of objectives.Process planning decisions focus on how to minimize manufacturing cost,whereas in the scheduling decisions the main aim is to optimize a scheduling criterion.Usually these two decisions are made independently.Since there is a significant interaction between the schedule performance and cost,it would be more beneficial to propose a model that combines these deci-sions to minimize total manufacturing cost and total weighted completion time,simultaneously.We also give an alternative model for the total completion time case,and present optimality properties for both problems. In practise,the weights of cost and time objectives for the decision maker may vary over time.If the workload is heavy,scheduling related objectives become more important.If it is relatively light,the manufacturing cost is very important.Therefore,we proposed a new method to generate an approximate efficient solution set for this bicriteria problem.
In multi-objective optimization problems,approximation quality of the generated efficient set is important to the decision maker.In the literature,there are different approximation quality evaluation metrics devel-oped.These metrics are useful for comparing different algorithms.Tuyttens et al.(2000)consider the classicallinear assignment problem with two objectives for which they employ a multi-objective simulated annealing method,and provide two metrics to compare the results with an exact efficient set.Wu and Azarm(2001)pro-pose some quality evaluation measures to compare efficient sets generated by different multi-objective optimi-zation methods.A review and discussion on existing metrics is available in Zitzler et al.(2003).In this paper, we will employ three different metrics to compare the approximation quality of our proposed methods.
In this study,we basically focus on CNC turning machines,so we have a well defined and realistic manu-facturing cost function for each job.This manufacturing cost function is nonlinear and convex.In our anal-ysis,we assume the case where the manufacturing cost function might be different for each job due to different operational and surface quality requirements,and its required cutting tool.However,all our results are appli-cable for the cases where there exists sublot of jobs which are identical.Although we specifically consider man-ufacturing cost function for the turning operation,our results apply to any problem with nonlinear convex processing cost functions.Furthermore,all the properties and methods that we derive below apply to the lin-ear cost function case as well.In the literature,to the best of our knowledge,the linear cost function case was not considered either.
In the next section,the problem definition is given and a mathematical model tofind an efficient solution for a given total weighted completion time level is provided.We give optimality properties for the model. Based on these properties,an efficient frontier approximation method is presented in Section3.Then,in Sec-tion4,an alternative model for the total completion time problem is discussed.In Section5,a numerical example is presented.Finally,in Section6the computational results and the performances of the proposed methods are discussed.
The notation used throughout the paper is as follows:
Decision variables
p i processing time of job i
X ij binary variable to state if job i precedes job j in the sequence
v i cutting speed for operation i(fpm)
f i feed rate for operation i(ipr)
U i usage rate of the required cutting tool to process operation i
Parameters
p l i processing time lower bound for job i
p u i processing time level that gives minimum manufacturing cost for job i
w i weight of job i
f i(p i)manufacturin
g cost function of processing time for job i
a,b,c speed,feed,depth of cut exponents for the required cutting tool of job i C TL i Taylor’s tool life constant for the required cutting tool of job i
C o operating cost of the CNC turning machine($/min)
C s,g,h,l specific coefficients of the surface roughness constraint of job i
C m,b,c,e specific coefficients and exponents of the machine power constraint
C t
i cost of cutting tool required to process job i($/tool)
D i diameter of the generated surface for job i(in)
d i depth of cut for job i(in)
H maximum available machine power(hp)
L i length of the generated surface for job i(in)
S i maximum allowable surface roughness for job i(l in.)
2.Problem definition
We have N jobs to be processed,and each job corresponds to a metal cutting operation that will be per-formed by a given cutting tool on a single CNC turning machine.Each job differs in terms of its manufactur-ing properties such as diameter,length,depth of cut and maximum allowable surface roughness and its cutting S.Gurel,M.S.Akturk/European Journal of Operational Research177(2007)325–343327tool,and a positive weight which shows its importance relative to the other jobs.The CNC turning machine can process one job at a time.We have two objectives,minimizing the total manufacturing cost of jobs on a CNC turning machine and minimizing their total weighted completion time.Therefore,we have to determine a job sequence and the corresponding processing times simultaneously.In order to solve this bicriteria problem,we have to consider process planning and scheduling problems simultaneously.One way to inte-grate these two decision making problems is through the proper selection of job processing times.Assuming a single pass operation,the processing time of job i on a CNC turning machine can be calculated as follows:
p i ¼
p D i L i 12v i f i
.
On the other hand,the tool usage rate of a job,U i,is simply the ratio of its processing time to the tool life.If we use extended Taylor’s tool life equation,T i,to describe the tool life then
U i¼p
i
T i
¼
ðp D i L iÞ=ð12v i f iÞ
C TL
i
=ðv a f b d cÞ
.
The optimum machining parameters of the cutting speed(v i)and the feed rate(f i)for each job can be found by solving machining conditions optimization problem subject to the tool life,surface roughness and machine power constraints as discussed in Appendix A.The most commonly used objective function for the manufac-turing cost of job i is the sum of the operating and tooling costs.Operating cost of job i is the cost of running the machine for p i.We assume that C o is constant and independent of selected machining parameters.Tooling cost for job i is the cost of its tool usage U i.We also assume that setup time and the tool change times are negligible.In Appendix A,we give the geometric programming model for the problem and the optimality properties proved by Akturk and Avci(1996)and Kayan and Akturk(2005).They showed that the surface roughness constraint must be tight at the optimal solution.Using this property,the manufacturing cost of job i is given below as a function of p i:
f iðp iÞ¼C o p iþC t
i U i¼C o p iþC t
i
d c
i
C
i
p D i L i
12
a hÀ
b g hÀg
ðÞC
s
d l
i
S i
aÀb hÀgðÞ
p
ð1ÀaÞhÀð1ÀbÞg
hÀg
ðÞ
i
.
Furthermore,Kayan and Akturk(2005)showed that the nonlinear manufacturing constraints that limit the
allowable ranges of the processing times can be replaced by a linear bound of p l
i 6p
i
6p u
i
for each job i when
there is a regular scheduling performance measure,such as makespan or total completion time.For the deter-
mination of p l
i and p u
i
values,we refer to Kayan and Akturk(2005).A typical manufacturing cost function
behavior for a job is given in Fig.1.Since jobs have different manufacturing properties,they will have different nonlinear convex manufacturing cost functions and different bounds on their processing times.
328S.Gurel,M.S.Akturk/European Journal of Operational Research177(2007)325–343The mathematical model for the problem is as below:
min F1:
X N
i¼1f iðp iÞ¼
X N
i¼1
C o p
i
þC t
i
U i
min F2:
X N
j¼1X N
i¼1
w j p
i
X ijþ
X N
j¼1
w j p
j
subject to X ijþX ji¼1;i¼1;...;N and j¼iþ1;...;N;ð1ÞX ijþX jkþX ki P1;j;k;l¼1;...;N;and j¼k¼l;ð2Þ
p l i 6p
i
6p u
i
8i;ð3Þ
X ij2f0;1g8i;j and i¼j.ð4ÞIn the mixed integer nonlinear programming(MINLP)model above,thefirst objective function(F1)is the total manufacturing cost.The second objective function(F2)is the total weighted completion time.Constraint set(1)is the precedence constraints to ensure that two jobs cannot precede each other at the same time.Con-straint set(2)satisfies the triangular inequality among the jobs such that if job i precedes job j and job j pre-cedes job k then job i precedes job k.We have constraint set(3)that sets the upper and lower bounds on the processing time of each job.
For the weighted completion time problem,the minimum value is attained when we set the processing times
to their lower bounds,p l
i .On the other hand,the manufacturing cost decreases when we increase the process-
ing times,and the minimum manufacturing cost is attained at p u
i for each job i.That means if we increase the
processing time of a job,the manufacturing cost decreases but completion time of the job itself and all the following jobs increase.Therefore,we cannot minimize both objectives F1and F2at the same time,and hence the overall problem is to generate an efficient solution set for the decision maker.A solution x(F1(x),F2(x))is said to be efficient with respect to the given bicriteria if there does not exist another solution y(F1(y),F2(y)) such that F1(y)6F1(x)and F2(y)6F2(x)with at least one holding as a strict inequality.The following lemma states that there are infinitely many efficient solutions for the problem.
Lemma1.1.The efficient solution set for the problem includes infinitely many points.
Proof.This is due to the fact that the processing times of jobs are continuous and can take any value satisfying
p l i 6p
i
6p u
i
.If we slightly decrease the processing time of any job i that will increase the total manufacturing
cost(as shown in Fig.1),but at the same time it will decrease the total weighted completion time.Hence,there are infinitely many possible F2(or F1)levels for the problem and we canfind infinitely many efficient solutions. Furthermore,efficient frontier can be represented as a continuous function on a(F1,F2)plot.h In Fig.2,an example for a set of efficient solutions is given.Solution Z1is the ideal solution for F2where
F2(Z1)=K l where the superscript l implies that K l is achieved by setting p
i ¼p l
i
for each job i and applying the
S.Gurel,M.S.Akturk/European Journal of Operational Research177(2007)325–343329
weighted shortest processing time first (WSPT)rule by Smith (1956).According to the WSPT rule the jobs are ordered in the decreasing order of w i /p i to minimize total weighted completion time.At Z 1,total manufactur-ing cost is F 1ðZ 1Þ¼P N i ¼1f i ðp l i Þ.On the other hand,solution Z 2is the ideal solution for F 1where F 1ðZ 2Þ¼P N i ¼1f i ðp u i Þand it is achieved by setting p i ¼p u i for each job i and jobs are ordered by the WSPT rule.At Z 2,total weighted completion time is F 2(Z 2)=K u ,where the superscript u implies that the solution is achieved where all jobs are machined at processing time upper bounds.
In order to find a set of efficient solutions other than Z 1and Z 2,we can consider F 2as a constraint as in the formulation below and solve the resulting Single Criterion Problem (SCP)for different values of K .
min F 1:
X N i ¼1f i ðp i Þsubject to X
N j ¼1X N i ¼1w j p i X ij þX N j ¼1w j p j 6K ;ð5Þ
and (1)–(4).
Constraint (5)guarantees that the total weighted completion time (F 2)of the schedule is less than or equal to a predefined value K .We can solve this model by the MINLP solvers like GAMS/BARON (Brooke et al.,2004).To generate an efficient solution set of n points between Z 1and Z 2we can employ the following algo-rithm denoted as the SCP-based method:
Step 1.Calculate K u and K l by using the WSPT rule for p u and p l values,respectively.
Step 2.Set =(K u ÀK l )/(n +1).
Step 3.For k =1to n ,solve the SCP model for K =K l +k .
The SCP-based method finds a set of efficient points by solving the SCP model iteratively,so we investi-gated the SCP model and found some useful properties for the problem.
Lemma 1.2.When K 6K u ,the constraint (5)on F 2must be tight at the optimal solution.This implies that the optimal schedule must satisfy the WSPT rule.
Proof.When K >K u ,total manufacturing cost can be minimized by setting all jobs to their minimum cost processing times (p u )and ordering them by the WSPT rule.In this case,the constraint (5)can be loose at opti-mality.When K 6K u ,if constraint (5)is loose,then by increasing the processing time of a job,we can decrease the total manufacturing cost of the schedule.Therefore,a solution cannot be optimal if constraint (5)is loose.As a consequence of this result we can also state that the WSPT rule must be satisfied by an optimal schedule.Otherwise,we can reorder the jobs and find a better solution which violates the optimality.h
We proved that an optimal solution for the SCP must satisfy the constraint (5)as an equality and it must also satisfy the WSPT rule.The next property for the problem is about the non-cycling constraint set (2).Lemma 1.3.The non-cycling constraints,constraint set (2),are redundant for the SCP.
Proof.Consider the SCP model without constraint set (2).We can easily see that Lemma 1.2still holds for the new problem,otherwise we can improve the solution by resequencing the jobs and increasing the processing times.Lemma 1.2states that the optimal solution must satisfy the WSPT rule which implies that the optimal solution cannot have cycles and always satisfies the constraint set (2).h
By using this result we can eliminate constraint set (2)when solving the SCP model in SCP-based method.Since constraint set (2)is defined for each job triple,removing it reduces most of the constraints in the model so that MINLP solvers can solve the problem more efficiently.From this point on,SCP will denote the single criterion problem without constraint set (2).Further,we consider the relaxation of the problem where the inte-grality assumption of X ij ’s is relaxed.Relaxation results a nonlinear programming (NLP)model for which we can state the following two properties.330S.Gurel,M.S.Akturk /European Journal of Operational Research 177(2007)325–343
Lemma 1.4.For the relaxed SCP,in a local optimal solution,if w i /p i >w j /p j for any job pair (i,j),then job i must precede job j,i.e.the solution must have X ij =1.This implies that a local optimal solution to the relaxed SCP must have binary X ij ’s.
Proof.Suppose that there is a local optimal solution S which has non-integer X ij values.We will show that by modifying S in a way to achieve an integer solution,we can improve F 2.
Consider a job pair (i ,j )in S for which w i /p i >w j /p j holds.Suppose that the precedence variables for the job pair (i ,j )are as follows:X ij =k ,X ji =1Àk ,where 06k <1.Then,P w i C i for S is as below:
F 2ðS Þ¼U þw i Âp j Âð1Àk Þþw j Âp i Âk ;
where U is a constant value.
If we form a new solution S 0from S by setting X ij =1and X ji =0,we get
F 2ðS 0Þ¼U þw j Âp i .
Obviously,F 2(S 0) P w i C i calculated by the mathematical model remains the same.In practice,it is highly unlikely to face this situation since in our case p i ’s are controllable variables that take real values. Lemma 1.4is an extremely important result to reduce the computational burden since we do not need MINLP solvers to solve the SCP.The problem can be solved by an NLP solver.However,NLP solvers can only guarantee to achieve local optimal solutions.From nonlinear programming theory we know that if the objective function of a problem is convex and the feasible region for the problem is a convex set,then a local optimum is a global optimum.Therefore,we investigated if the feasible region for the relaxed SCP is a convex set or not to see if NLP solvers could give us the global optimum. Lemma 1.5.The feasible region for the relaxed SCP is not a convex set,i.e.NLP solvers cannot guarantee global optimality for the problem. Proof.Consider two jobs i 1and i 2such that i 1immediately precedes i 2,X i 1i 2¼1,in a solution called A 1.Let us suppose that p i 1¼s 1and p i 2¼s 2with weights w 1and w 2,respectively.We also have w 11>w 22.F 2(A 1)=Q +w 2s 1+w 1s 1+w 2s 2=K ,where Q is a constant.Next,consider another solution A 2which is identical to A 1except that i 1and i 2were pairwise interchanged and processing times were set to q 1and q 2, respectively,and w 22>w 11holds.F 2(A 2)=Q +w 1q 2+w 1q 1+w 2q 2=K .Now consider a convex combination of A 1and A 2as the solution A =k A 1+(1Àk )A 2.At A ,X i 1i 2¼k ,X i 2i 1¼1Àk ,p i 1¼k s 1þð1Àk Þq 1and p i 2¼k s 2þð1Àk Þq 2.Then, F 2ðA Þ¼Q þw 1X i 2i 1p i 2þw 2X i 1i 2p i 1þw 1p i 1þw 2p i 2 ¼Q þðw 1ð1Àk Þþw 2Þðk s 2þð1Àk Þq 2Þþðw 2k þw 1Þðk s 1þð1Àk Þq 1Þ ¼Q þk ðs 1ðw 1þk w 2Þþs 2ðw 2þð1Àk Þw 1ÞÞþð1Àk Þðq 1ðw 1þk w 2Þþq 2ðw 2þð1Àk Þw 1Þ ¼Q þk ðs 1w 1þs 2w 2þk s 1w 2þð1Àk Þs 2w 1Þþð1Àk Þðq 1w 1þq 2w 2þk q 1w 2þð1Àk Þq 2w 1Þ >Q þk ðK ÀQ Þþð1Àk ÞðK ÀQ Þ>K since s 2w 1>s 1w 2and q 1w 2>q 2w 1.This shows that the feasible region for the relaxed SCP is not a convex set.h Lemma 1.5implies the potential existence of multiple local optimal solutions for the relaxed SCP.Although it does not prove NP-hardness of the SCP,we know that in general,computing a global minimum in a non-convex NLP is an NP-hard problem due to Murty and Kabadi (1987). min F1: X N i¼1 f iðp iÞ subject to X N j¼1X N i¼1 w j Y ijþ X N j¼1 w j p j 6K;ð6Þ Y ij P p i þðX ijÀ1ÞM8i;j and i¼j;ð7Þ Y ij6p i þð1ÀX ijÞM8i;j and i¼j;ð8ÞY ij6MX ij8i;j and i¼j;ð9Þ Y ij P08i;j and i¼j;ð10Þ and(1),(3)and(4). In this model,constraint(6)is the constraint on F2.Constraint sets(7)–(10)assure that if X ij=0then Y ij=0and if X ij=1then Y ij=p i,so that Y ij=p i X ij always holds.Unfortunately,the computational perfor-mance of this linearization is very poor because Lemma1.4no longer holds so we cannot relax the integrality constraint of X ij.Therefore,we have to use computationally less efficient GAMS/BARON solver instead of GAMS/MINOS. In this section,we defined the problem and proposed the SCP-based method that can utilize commercial NLP solvers to solve the SCP and generate an approximation for the efficient frontier for the problem. We also gave the LSCP model which can be solved to global optimum by the MINLP solvers.However, since the MINLP and NLP solvers are not yet widely used and they are not as much computationally efficient as LP solvers,we also aimed to develop an effective approximation method tofind a set of effi-cient points.In the next section,we define a heuristic method to approximate the efficient frontier for the problem. 3.Cost index based approximation(CIBA)method In Section2,we showed some optimality properties and simplifying characteristics for the SCP.In this sec-tion,we further present another very important optimality property in Lemma1.6.This property will be help-ful to design a heuristic method.This property basically tells us that if a solution is locally optimal then we cannot improve the total manufacturing cost by only changing the processing times of the jobs.It can also be explained as follows:for a given job sequence there is a unique processing time vector p H¼ðp H 1;p H 2 ;...;p H N Þthat minimizes the total manufacturing cost for a given total weighted completion time (K).This property is as follows: Lemma1.6.For any job pair i,j,a local optimal solution must satisfy the following conditions: (i)If p i >p l i and p j >p l j then o f iðp iÞ o p i 1 W i ¼o f jðp jÞ o p j 1 W j ,where W i¼w iþ P N k¼1 X ik w k(i.e.the sum of the weights of job i and jobs that job i precedes). (ii)If p i ¼p l i and p j >p l j then o f iðp iÞ i 1 i P o f jðp jÞ j 1 j .Proof.Suppose that o f iðp iÞ i 1 i 1 j for some i,j.Then, lim D p!0 f iðp iþD pÞÀf iðp iÞ W i D p À f jðp jÞÀf j p jÀW i j D p W j W i W j D p @ 1 A<0; lim D p!0 f iðp iþD pÞÀf iðp iÞþf jðp jÞÀf j p jÀW i W j D p D p @ 1 A<0. Then,$D p>0s.t.f iðp iþD pÞÀf iðp iÞþf jðp jÞÀf j p jÀW i j D p <0,which means the current solution can be improved without violating the total weighted completion time constraint.This proves that if there exists a job pair that does not satisfy the given conditions,then the solution is not locally optimal.h The heuristic approach(CIBA)starts with the solution Z1(Fig.2)and generates new approximate efficient points by using the information in Lemma1.6.After taking the solution Z1,by slightly increasing the process-ing times of the jobs one at a time at each iteration,we decrease F1while increasing F2.The critical issue is which job to choose to perturb at each iteration so that the achieved decrease in F1over the increase in F2 is at the maximum(i.e.the‘biggest bang for the buck’).To make the most appropriate choice,we propose a new cost index r i for each job i,such that r i¼o f iðp iÞ o p i 1 W i . It is the estimated manufacturing cost change per unit total weighted completion time loss to be achieved by increasing the processing time of job i.Note that this index definition comes from Lemma1.6.Next,we choose the job with the minimum r i value.It is important to note that f i(p i)is decreasing and r i<0when p l i 6p i i for all i.Then,the processing time of the selected job is increased by a predefined D amount.Increasing processing time of a job may result in a schedule that violates Lemma1.2.We check if the WSPT rule is violated or not and if so we reorder the jobs according to the WSPT rule.After reordering,F new 2and F new 1 are calculated.For the updated and re-sequenced jobs,their r i’s are updated.This job selection and update process is applied until F new 2reaches to K u.Each schedule achieved at the end of an iteration is kept as an approximate efficient solution.By keeping D as small as possible we can achieve solutions which are more close to the optimality property defined by Lemma1.6. Having discussed the basic approach,the proposed cost index based approximation(CIBA)method is given below: Step1.Find the non-dominated solutions Z1and Z2. Step2.Start with the solution Z1,set F new 1¼F1ðZ1Þand F new 2 ¼F2ðZ1Þ.While F new 2 Step2.2.Set p m=p m+D. Step2.3.If the WSPT rule is violated,re-sequence the jobs by the WSPT rule. Step2.4.Update r i indices for job m and for all other jobs whose position in sequence is changed in Step2.3. Step2.5.Update F new 1¼F new 1 À½f mðp mÞÀf mðp mþDÞ and recalculate F new 2 . Step2.6.Report the current schedule with F new 1and F new 2 as an approximate efficient solution. In each iteration of the CIBA method,we want to improve total manufacturing cost by slightly losing from the total weighted completion time.Since we want to minimize both criteria at the same time,we always prefer to update the job with the maximum manufacturing cost gain per unit increase in the total weighted comple-tion time(Step2.1).This is due to Lemma1.6which states the optimality conditions on p i’s.By choosing the job with minimum r i each time we try to keep the achieved solutions to be close as possible to hold the con-ditions given in Lemma1.6.After increasing the processing time of the selected job,the sequence of jobs is updated(Step2.4),if necessary,by the WSPT rule.This is due to Lemma1.2which states that in an optimal schedule the job sequence must satisfy the WSPT rule.Then,for the perturbed job and for all re-sequenced jobs,r i values are updated.At each iteration,the schedule achieved is reported as an approximate efficient solution.An important property that holds for the solution set generated by the CIBA is the following:Lemma1.7.Each iteration of the CIBA method generates a new approximate efficient solution. Proof.As discussed earlier,we have a nonlinear convex manufacturing cost function and the processing times can take any real value between p l i 6p i 6p u i .At each iteration of the CIBA method,the processing time of a selected job is increased by a D amount,that means the total manufacturing cost is strictly decreasing in each iteration as shown in Fig.1.Moreover,the total completion time strictly increases even if the job sequence changes.Therefore,in each iteration we generate a new approximate efficient solution that cannot dominate previously generated solutions.h The solution quality of the CIBA method depends on the selected D value.Since we are making decisions based on o f iðp iÞ o p i ’s,if we choose a small D value,we get a better approximation to an efficient solution.Further-more,a smaller D leads to more solution points to be generated which implies a better approximation of the efficient frontier. 4.Total completion time problem All the models,properties and algorithms that we have given above also apply for the total completion time problem,which is a special case where the weights of jobs are equal.Instead,we present a new model for the total completion time problem.In this section,we proved that this new model holds the same properties as the previous one.Moreover,we performed a set of trial runs and showed that the new model is computationally more efficient in terms of the CPU times in solving the total completion time problem.In this model,we intro-duce a new binary decision variable X ij to control if job i is assigned to position j in the sequence.The new formulation for the SCP is as below: min F1: X N i¼1 f iðp iÞð11Þ subject to X N i¼1X N j¼1 ðNÀjþ1ÞX ij p i6K;ð12Þ X N j¼1 X ij¼18i;ð13ÞX N i¼1 X ij¼18j;ð14Þ p l i 6p i 6p u i 8i;ð15Þ X ij2f0;1g8i;j.ð16ÞIn the above model,the objective function corresponds to the total manufacturing cost.The constraint(12) gives the total completion time.Constraints(13)and(14)are the assignment constraints which guarantee that each job is assigned to a position in the schedule and each position has a job assigned.Constraints(15)and (16)are same as in the previous model. We could have used a similar model with the assignment variables X ij to solve the weighted total completion time problem.In that case,we will not be able to use the property stated in Lemma1.4,and hence the relaxed SCP model cannot be solved by the NLP solvers.It turns out that the way we model the problem affects the solver to be used and the computational requirements.We now check the characteristics of this new formu-lation as we did for the previous model before. Lemma2.1.When K6K u,the total completion time constraint(12)must be tight at the optimal solution.This implies that the optimal schedule must satisfy the shortest processing timefirst(SPT)rule. The proof for Lemma2.1is similar to the proof of Lemma1.2,so we skip it due to the space limitations. We next consider the NLP relaxation of the new SCP formulation and look for the optimality conditions for the relaxed problem.Lemma2.2.For the relaxed SCP,in a local optimal solution,if p i 1 2 for any job pair(i1,i2),then job i1must be assigned to an earlier position than i2.This implies that a local optimal solution to the relaxed SCP must have binary X ij’s. Proof.Suppose that we have a solution S for the relaxed problem where we consider two jobs i1and i2with processing times p i1 .Further consider two positions j1and j2in the schedule such that j1 X i 1j1¼q1and X i 2j1 ¼q2; X i 1j2¼n1and X i 2j2 ¼n2;where q1;q2;n1and n2are positive. Since we relaxed the integrality constraint,a solution to the relaxed problem may contain non-binary X ij val-ues.This means,the same job could be allocated to multiple positions in the schedule,which is infeasible for our original problem. Total completion time value calculated for S is as below: F2ðSÞ¼ X N i¼1X N j¼1 ðNÀjþ1ÞX ij p i¼UþðNÀj1þ1Þ½q1p i 1 þq2p i 2 þðNÀj2þ1Þ½n1p i 1 þn2p i 2 ¼Uþ½ðNÀj1þ1Þq1þðNÀj2þ1Þn1 p i 1þ½ðNÀj1þ1Þq2þðNÀj2þ1Þn2 p i 2 ; where U is a constant value.Suppose that without changing the processing times,we change the assignment variables to get a new solution S0.Setting d=min(n1,q2),new values for the assignment variables are as follows: X i 1j1¼q1þd;X i 2j1 ¼q2Àd; X i 1j2¼n1Àd and X i 2j2 ¼n2þd. By this arrangement we reallocate these two jobs to positions j1and j2such that we increase job i1’s ratio in the preceding position j1without disturbing the assignment constraints. Total completion time of the solution after this arrangement is F2ðS0Þ¼Uþ½ðNÀj1þ1Þðq1þdÞþðNÀj2þ1Þðn1ÀdÞ p i 1 þ½ðNÀj1þ1Þðq2ÀdÞþðNÀj2þ1Þðn2þdÞ p i 2 . Then,F2ðS0ÞÀF2ðSÞ¼dðj2Àj1Þðp i 1Àp i 2 Þ<0,because j2>j1and p i 1 . This proves that there is always an integer optimal solution for the relaxed problem.h According to Lemma2.2,a local optimal solution must have integer X ij’s.Although for the case where p i1¼p i 2 ,we could have alternative non-integer local optimal solutions.As in the previous formulation for the weighted case we do not need a MINLP solver to solve the relaxed problem,and an NLP solver would be sufficient. Lemma2.3.The feasible region for the relaxed SCP is not a convex set. Proof.Consider two jobs i1and i2in a schedule called A1.They are assigned at positions k and k+1,respec- tively.Their processing times are p i1¼s1and p i 2 ¼s2where s1 Consider another schedule A2which is identical to A1except that job i1is at position k+1and i2is at position k with processing times p i 1¼q1and p i 2 ¼q2where q2 Next,define a point A which is a convex combination of A1and A2as follows: A=k A1+(1Àk)A2where0 2 ¼k s2þð1ÀkÞq2.Also, X i 1k ¼k,X i 1 ðkþ1Þ ¼ð1ÀkÞ,X i 2 k ¼ð1ÀkÞand X i 2 ðkþ1Þ ¼k.F2ðAÞ¼Qþ½ðNÀkþ1ÞkþðNÀkÞð1ÀkÞ p i 1þ½ðNÀkþ1Þð1ÀkÞþðNÀkÞk p i 2 ¼Qþk2½ðNÀkþ1Þs1þðNÀkÞs2 þð1ÀkÞ2½ðNÀkþ1Þq2þðNÀkÞq1 þkð1ÀkÞ½ðNÀkþ1Þq1þðNÀkÞq2 þkð1ÀkÞ½ðNÀkþ1Þs2þðNÀkÞs1 >K since s1 The SCP model for the total completion time case also includes nonlinear terms in constraint(12).We can linearize constraint(12)in the model by replacing the nonlinear term p i X ij in constraint(12)with a variable Y ij and adding constraints(7)–(10)to the model as we did in Section2.By this way we can achieve the LSCP model for the unweighted case and solve it to global optimum by using the MINLP solver GAMS/BARON. Next,we give another property analogous to Lemma1.6. Lemma2.4.For any job pair i,j a local optimal solution must satisfy the following conditions: (i)If p i >p l i and p j >p l j then o f iðp iÞ i 1 i ¼o f jðp jÞ j 1 j ,where n i¼ P N j¼1 X ijðNÀjþ1Þ. (ii)If p i ¼p l i and p j >p l j then o f iðp iÞ o p i 1 n i P o f jðp jÞ o p j 1 n j . Proof.Suppose that in a solution o f iðp iÞ o p i 1 n i 1 n j for jobs i,j.Then lim D p!0 f iðp iþD pÞÀf iðp iÞ n i D p À f jðp jÞÀf j p jÀn i j D p n j n i n j D p @ 1 A<0; lim D p!0 f iðp iþD pÞÀf iðp iÞþf jðp jÞÀf j p jÀn i j D p n i D p @ 1 A<0. Then,$D p>0s.t.f iðp iþD pÞÀf iðp iÞþf jðp jÞÀf j p jÀn i j D p <0,which means the current solution can be improved by increasing p i by D p and decreasing p j by n i n j D.This proves that if a solution does not satisfy the conditions above,then it is not locally optimal.h As we have shown that similar properties as the weighted case apply to the alternative formulation for the total completion time case we can employ similar approaches tofind an approximation for the efficient fron-tier.We can generate approximate efficient solution set by solving the new model in the SCP-based method as described in Section2.We can also employ our CIBA method by just modifying the cost index r i as r i¼o f iðp iÞ i 1 i where n i is the number of jobs that job i precedes including itself. 5.Numerical example In this section,we give a numerical example for the total weighted completion time problem and apply the SCP-based method and the CIBA method to generate an approximate efficient frontier.In this problem we havefive jobs and the design attributes(D i,L i,d i and S i)of each job along with the required cutting tool type are given in Table1.Wefirst calculated p l i and p u i values for each job as given in the same table.They are used to define a manufacturing cost function for each job.For example,the manufacturing cost function for job1is f1¼0:25Âp1þ0:35ÂpÀ1:32 1 Tofind the solution Z1and the corresponding schedule,wefirst set all jobs’processing times to their lower bounds and apply the WSPT rule as shown in Table2.Total manufacturing cost,F1,for this initial schedule is 5.105and the corresponding optimal total weighted completion time,F2,is4.820.The initial schedule gives us the ideal total weighted completion time and the nadir manufacturing cost.We also have the schedule (Z 2)cor-responding to the minimum manufacturing cost in Table 2.For the minimum cost settings,F 1=1.952and F 2=15.6.This schedule gives us the ideal manufacturing cost and the nadir total weighted completion time.As stated in the proposed CIBA method,we start with the solution Z 1,and perturb the job with the min-imum r i in each iteration,such as job 2at the first iteration.In this example,we set the step size D =0.1.In Table 3,we present the perturbed job (j ),and after each perturbation the new p j ,w j /p j ,sequence and r i ’s along with the F 1and F 2values.As an example,after we perturb job 1in iteration 2,we need to re-sequence the jobs to satisfy the WSPT rule.The algorithm progresses in this way by perturbing one job at a time until we reach to solution Z 2.As can be seen in Table 3,at each iteration we improve the total manufacturing cost (F 1)while losing from the total weighted completion time (F 2)(i.e.generate a new efficient solution)as discussed in Lemma 1.7. Using the CIBA method,we generated 34approximate efficient solutions for the example problem.As dis-cussed before,we could also use a commercial NLP solver to find the minimum manufacturing cost for a given total weighted completion time level.In this study,we model the problem in GAMS and use the MINOS sol-ver as the SCP-based method.In Table 4,there are two schedules generated for the total weighted completion time of 7.660.The first schedule is found by the CIBA method at iteration 10given in Table 3.We also solved the same problem by MINOS.It can be seen from Table 4that two schedules are different in terms of job sequences and job processing times.When we consider the schedule found by the SCP-based method using Specifications of the jobs in the numerical example Job D i L i d i S i Tool w i p l i p u i 1 1.9 4.60.2111685 1.20.295 1.3022 2.0 4.90.1511561 1.30.447 1.1383 1.6 4.30.2041809 1.10.2970.5944 1.9 4.60.1381565 1.90.203 1.0295 1.6 4.2 0.170 175 9 1.0 0.251 0.530 Table 2 Schedules at Z 1and Z 2Position Z 1Z 2Job p w /p r i f i (p i )Job p w /p r i f i (p i )140.2039.38À1.63 1.71350.530 1.0.00.210210.295 4.06À1. 1.82230.594 1.850.00.235350.251 3.99À0.490.3414 1.029 1.850.00.452430.297 3.71À0.580.3592 1.138 1.140.00.4835 2 0.447 2.91 À1.68 0.870 1 1.302 0.92 0.0 0.572 Table 3 Results of the first 10iterations by the CIBA method Iter.Pert.job (j )p j w j /p j Sequence r i F 2 F 1 12345120.547 2.371532À1.À0.95À0.58À1.63À0.49 4.950 4.939210.395 3.03745312À1.49À0.95À0.39À1.63À0.36 5.238 4.406340.303 6.27945312À1.49À0.95À0.39À0.62À0.36 5.888 3.748410.495 2.42345312À0.84À0.95À0.39À0.62À0.36 6.138 3.467520.7 2.00945312À0.84À0.57À0.39À0.62À0.36 6.268 3.370610.595 2.015312À0.51À0.57À0.39À0.62À0.36 6.518 3.205740.403 4.72045312À0.51À0.57À0.39À0.30À0.367.168 2.923820.747 1.74045312À0.51À0.34À0.39À0.30À0.367.298 2.865910.695 1.725321À0.68À0.18À0.39À0.30À0.367.540 2.76110 1 0.795 1.509 45321 À0.45 À0.18 À0.39 À0.30 À0.36 7.660 2.694 Position Schedule by CIBA method Schedule by SCP-based method Job(i)p i w i/p i r i f i(p i)Job(i)p i w i/p i r i f i(p i) 140.403 4.720À0.300.77340.395 4.81À0.320.788 250.251 3.987À0.360.34150.261 3.83À0.320.325 330.297 3.708À0.390.35930.316 3.48À0.320.335 420.747 1.740À0.180.54910.704 1.70À0.320.731 510.795 1.509À0.450.67220.763 1.70À0.320.542 MINOS,we see that it satisfies Lemma1.2,which states that total weighted completion time must be tight at optimality and it also satisfies the WSPT rule.The MINOS solution has integer X ij’s,so that it gives a feasible schedule(Lemma 1.4).For this particular solution,the CIBA method gives a slightly better solution (F1=2.694)than the GAMS/MINOS solver(F1=2.721),which is an example for the case that a solution found by MINOS may not be a global optimal(Lemma1.5).Finally,when we check the r i values of the MINOS solution,we see that they satisfy Lemma1.6which states that a local optimal solution cannot be improved by just changing the processing times of jobs.In order tofind the global optimum of F1for a given F2=7.660,we solve the LSCP model by GAMS/BARON,which gives F1=2.6with the job sequence of4–5–3–2–1(the same sequence with the CIBA),and the processing times(0.402,0.265,0.321,0.3,0.886), respectively. 6.Computational results In this study,we considered two bicriteria production optimization problems with a scheduling objective and manufacturing cost objective.The scheduling objectives we considered were total completion time and total weighted completion time.For each case,we provided two different efficient frontier approximation algo-rithms:namely the SCP-based method and the CIBA method.The SCP-based method is modeled in GAMS 2.5using solver MINOS5.51.The CIBA method is coded in C and compiled with Gnu C compiler.All codes were run on a computer with1294MB memory and Pentium III1133MHz CPU.In this section,we discuss the results of the computational study. There are three experimental factors that can affect the efficiency of the proposed methods as listed in Table 5.The number of jobs is an important factor that affects the solution quality and computational requirements. The machine type is considered since different machines have different cutting power levels and different oper-ating costs.Machines with higher maximum cutting power,H,are more expensive to buy so operating cost of them,C o,is higher.C o and H affect the p l and p u levels as well as the shape of the manufacturing cost function. C t,the tooling cost level,affects the p u and the shape of the manufacturing cost function too.We also consider 10different cutting tool types with the specific coefficients given in Table6.Each job can be manufactured by one of these cutting tools.For each experimental setting(3*3*2),we tookfive replications resulting in90 different problem settings.Furthermore,we generated jobs’technical specifications as follows: D i are selected from U[1,4],L i from U[4,6],d i from U[0.05,0.3],S i from U[150,250],where U[a,b]is a uniform distribution in interval[a,b].For the weighted case we generated a weight for each job from U[1,10].Finally,we used two different levels of step size D,such as0.01and0.03. Wefirst present the results for the total weighted completion time problem.The number of approximate efficient points generated by the CIBA method depends on the experimental factors,job specifications and Table5 Experimental design factors Factor Definition Level1Level2Level3 N Number of jobs50100150 m/c Machine type C o=1,H=5C o=2,H=10C o=4,H=20 C t Tooling cost level U[6,10]U[15,19]Technical coefficients of the cutting tools Tool a b c K b c e C m g h l C s 1 4.0 1.40 1.10,960,0000.910.780.75 2.394À1.5 2 1.0040.25204,620,000 2 4. 3 1.60 1.2037,015,0560.960.700.71 1.637À1.60 1.0050.30259,500,000 3 3.7 1.30 1.1013,767,3400.900.750.72 2.315À1.45 1.0150.25202,010,000 4 3.7 1.28 1.0511,001,0200.800.750.70 2.415À1.63 1.0520.30205,740,000 5 4.1 1.2 6 1.0548,724,9250.800.770.69 2.545À1.69 1.0050.40204,500,000 6 4.1 1.30 1.1057,225,2730.870.770.69 2.213À1.55 1.0050.25202,220,000 7 3.7 1.30 1.0513,767,3400.830.750.73 2.321À1.63 1.0150.30203,500,000 8 3.8 1.20 1.0523,451,6370.880.830.72 2.321À1.55 1.0160.18213,570,000 9 4.2 1.65 1.2056,158,0180.900.780.65 1.706À1.54 1.1040.32211,825,000 10 3.8 1.20 1.0523,451,6370.810.750.72 2.298À1.55 1.0160.18203,500,000 D.We cannot determine the number of points to be generated by the CIBA method in advance.Therefore,to compare these two approaches wefirst run the CIBA method and generate a set of approximate efficient points.Then,we choose a subset of this solution set and run the SCP-based model for this subset.As discussed earlier,we generate points with total weighted completion time values in[K l,K u].Out of these points,we chose 50points other than Z1and Z2such that each successive point pair has equal(or almost equal)separation. This is because we want to test the algorithms at different total weighted completion time levels along the effi-cient frontier. We measured the relative difference between the F1values for a given F2value,R=(F1(CIBA)ÀF1(SCP))/ F1(SCP).Another critical issue to consider is the computational requirements of both methods.In Table7,we summarize the R level and the required CPUs.The given CPUs in this table are measured for the entire solu-tion sets.The data shows that the relative difference between two methods on the average is very small in favor of the CIBA.We can say that on the average the CIBA performs slightly better than the commercial NLP solver MINOS in terms of the solution quality.The maximum R values show that there are cases where the SCP-based method performs better.Moreover,we conclude that the CIBA method canfind significantly higher number of efficient points than the SCP-based method in a much shorter computational time.For D=0.01,the SCP-based method used352.91CPU seconds on the average to solve for50solution points, but the CIBA method just spent29.56CPU seconds on the average to generate354,597points.In an eighth of MINOS’CPU requirement,the CIBA method can generate7000times more alternatives.It is important to note that we originally had a nonlinear mixed-integer programming formulation.Due to Lemmas1.4and2.2, we were able to solve these problems by using the MINOS solver by relaxing the integrality requirements.Still, the CPU needed to solve the SCP-model is quite high.As expected,when we increase the step size,D,we loose from the solution quality at each point but gain from the CPU time.Moreover,for a higher D value,the size of the approximate efficient solution set decreases.When we check the results for different levels of N,we observe that increase in the number of jobs increases the SCP-based method’s CPU much more than the CIBA method,but the relative difference between two methods,R,slightly improves in favor of the CIBA method. Table7 Performance measures for the weighted case D Min Max Mean Std.dev. 0.01RÀ0.0039700.001559À0.0001080.000665 SCP-based CPU16.86961.59352.91356.88 CIBA CPU0.78125.5929.5635.17 CIBA set size32,0841,066,094354,597296,026 0.03RÀ0.0009360.000216À0.0000410.000177 SCP-based CPU17.30955.57354.19355.70 CIBA CPU0.21.249.7611.56 CIBA set size10,693355,344118,188,674Next,we discuss the computational results for the total completion time case.In Table8,we present the results for the unweighted case for different D values.We see that the overall performance of CIBA is very close to the SCP-based method but the SCP-based method performs slightly better than the CIBA in terms of solution quality.The minimum R values indicate that there are cases where the CIBA performs better. Results show that both methods require less computation time for the unweighted case compared to the weighted case as expected.Moreover,the CIBA method generated less number of efficient points for the unweighted case.This is because when the weights of completion times are selected from the interval[1,10] we achieve a larger[K l,K u]interval so that the CIBA can generate more points for the weighted case if the same D value is used as in the total completion time case. Another important question is the absolute performance of the SCP-based method from the global mini-mum due to Lemmas1.5and2.3.We could solve the LCSP model only for5and8job problems within the reasonable CPU times by using the GAMS/BARON solver version7.2.3.We applied the same experimental setting as above.We tookfive replications for each setting.For each replication,we applied the SCP-based approach forfive efficient points that the CIBA generated.So,we solved a total of300MINLP problems by BARON and MINOS.Table9shows the relative difference values for the SCP-based methods using MINOS versus BARON and the CIBA versus the SCP-based method using BARON.Results show that both MINOS and CIBAfind solutions very close to global optimal.There are some cases where MINOSfinds the global optimal.The computational requirements of MINOS and CIBA are negligible for the considered num-ber of jobs levels.We observe that when we increase the number of jobs from5to8,the CPU time required by BARON increases by300times. Up to this point we have compared the pointwise quality of individual solutions generated by different methods.However,since this is a multi-objective optimization problem,we also check the approximation quality of solution sets generated by the CIBA and SCP-based methods.In the literature,there are different metrics used to compare the approximation quality of solution sets generated by different methods.In this paper,we will use three of them.Thefirst one is the area method proposed by Zitzler and Thiele(1998),which measures the size of the objective value space covered by a solution set.The second metric is the coverage dif-ference of two sets,CD(A,B),by Zitzler(1999),such that CD(A,B)=Area(A[B)ÀArea(B).This measure shows the contribution of solution set A to the area covered by solution set B.These two metrics use the ideal and nadir values of the objective functions in order to normalize the objective values of solutions and calculate Table8 Performance measures for the unweighted case D Min Max Mean Std.dev. 0.01RÀ0.0000760.0012320.0003130.000309 SCP-based CPU12.70509.43201.60194.72 CIBA CPU0.010.140.060.03 CIBA set size132497314471.72286.3 0.03RÀ0.0195990.0102210.0026100.0032 SCP-based CPU11.42522.29202.65195.51 CIBA CPU0.010.050.0210.01 CIBA set size44432471494.6763.2 Table9 Comparison with the global optimal solutions N Min Max Mean Std.dev. 5R(CIBA-BARON)0.0000140.00550.0010070.001433 R(MINOS-BARON)0.00.0066730.0012580.002132 BARON CPU 5.5113.3210.07 1.79 8R(CIBA-BARON)0.0000100.0041250.0001050.000109 R(MINOS-BARON)0.00.0045520.0000920.001348 BARON CPU993.904627.833010.53943.08 the corresponding areas.In our problem,ideal and nadir values are achieved at solutions Z 1and Z 2.The last metric we use is the probability,P (A ,B ),that an algorithm,A ,gives a better solution than another algorithm,B .This metric is proposed by Hansen and Jaszkiewicz (1998).It is calculated as P ðA ;B Þ¼ R u 2½0;1 C ðA ðu Þ;B ðu ÞÞd u ,where C ðA ðu Þ;B ðu ÞÞ¼1; f ðA ðu ÞÞ 8 ><>:and f ðA ðu ÞÞ¼min x 2A f max ðuF 01ðx Þ;ð1Àu ÞF 02ðx ÞÞg where F 01ðx Þ¼F 1ðx ÞÀF 1ðZ 2Þ F 1ðZ 1ÞÀF 1ðZ 2Þ which is a normalization of F 1.Here u is the weight of the normalized objective function F 1for the decision maker.The method basically tries a number of u values between 0and 1and estimates the decision maker’s probability to choose a solution gen-erated by method A .The results in Table 10show that on the average area covered by the CIBA algorithm is larger than the area covered by the SCP-based method.Although there is a small difference,paired t -test re-sults show that CIBA is significantly better than SCP-based method in terms of the area measure.When we check the coverage difference results,we see that the contribution of CIBA to the area covered by the SCP-based method is much more than the opposite measure.Finally,we check the probability measure,which shows that for the 99.5%of the cases on the average,the decision maker would prefer to implement a solution achieved by the CIBA method. Computational results show that the CIBA method has almost same pointwise cost quality with the SCP-based approach despite the much less computational time requirement.More than that,the CIBA method can generate significantly higher number of efficient solutions than the SCP-based methods in a short computation time.As a result,the approximation quality measures that we calculated for both methods show that CIBA achieves significantly better approximations of the efficient frontiers than the SCP-based method.7.Conclusion In this study,we dealt with controllable processing times where processing time decisions affect the man-ufacturing cost as well as the scheduling performance.We considered the bicriteria problem with the objectives of minimizing the manufacturing cost and the total weighted completion time.We proposed a very effective single criterion model to find efficient solutions for different levels of total weighted completion time.This model can be solved to integer local optimality by just using a commercial NLP solver.Additionally,we have derived important optimality properties for the model which led us to design a very quick and effective algo-rithm which generates an approximate efficient solution set.Although we focus on the CNC turning machines for practical purposes,our results are valid for any nonlinear convex processing cost function.This study is an important step to integrate the process planning and scheduling decisions since it copes with job sequencing and processing time decisions simultaneously.For the future research,we consider the minimizing manufac-turing cost objective with different scheduling objectives and different machine environments.Acknowledgements The authors thank the anonymous referees for suggestions on improving the paper.This work was sup-ported in part by the Scientific and Technical Research Council of Turkey under grant #2211. Table 10 Comparison of the approximation algorithms for D =0.01Metric Mean Min Max Area(CIBA)0.8430.8160.867Area(SCP) 0.8330.8050.856CD(CIBA,SCP)0.0110.0100.012CD(SCP,CIBA)0.0000020.00.000029P (CIBA,SCP) 0.995 0.975 1.000 SMOP is the manufacturing cost minimization problem for the turning operation.Decision variables for the problem are the cutting speed(v i)and the feed rate(f i).The job to be machined has certain specifications like job diameter,length,depth of cut and maximum allowable surface roughness and a selected cutting tool. A cutting tool has certain technical coefficients. There are three constraints in the problem.Thefirst one is the tool life constraint which comes from the limitation that each job can use at most one tool.The second constraint is the machine power constraint that comes from the maximum applicable cutting power by the machine.The last one,the surface roughness con-straint,satisfies the surface quality requirement for the operation.The geometric programming model for the problem to minimize manufacturing cost(i.e.the sum of the operating and the tooling costs)for job i is as follows: Minimize Cost¼C oÁp iþC tÁU i¼C1vÀ1 i fÀ1 i þC2vðaÀ1Þ i fðbÀ1Þ i Subject to C0 t v aÀ1 i f bÀ1 i 61ðTool life constraintÞ; C0 m v b i f c i 61ðMachine power constraintÞ; C0 s v g i f h i 61ðSurface roughness constraintÞ; v i;f i>0; where C1¼p D i L i C o,C2¼p D i L i d c i C t i 12C TL i ,C0 t ¼p D i L i d c i 12C TL i ,C0 m ¼C m d e i and C0 s ¼C s d l i i . Theorem1(Akturk and Avci,1996).At least one of the surface roughness and machine power constraints is binding at optimality for SMOP. Theorem2(Kayan and Akturk,2005).The surface roughness constraint must be tight at the optimal solution. References Akturk,M.S.,Avci,S.,1996.Tool allocation and machining conditions optimization for CNC machines.European Journal of Operational Research94,335–348. Brooke,A.,Kendrick,D.,Meeraus,A.,Raman,R.,2004.GAMS:A User’s Guide.GAMS Development Corporation. Chen,Z.L.,Lu,Q.,Tang,G.,1997.Single machine scheduling with discretely controllable processing times.Operations Research Letters 21,69–76. Choi,J.C.,Bricker,D.L.,1996.Effectiveness of a geometric programming algorithm for optimization of machining economics models. Computers and Operations Research23,957–961. Daniel Ng,C.T.,Cheng,C.T.E.,Kovalyov,M.Y.,2003.Batch scheduling with controllable setup and processing times to minimize total completion time.Journal of the Operational Research Society54,499–506. Gopalakrishnan,B.,Al-Khayyal,F.,1991.Machine parameter selection for turning with constraints:An analytical approach based on geometric programming.International Journal of Production Research29(9),17–1908. Hansen,M.P.,Jaszkiewicz,A.,1998.Evaluating the quality of approximations to the non-dominated set.IMM Technical Report, Technical University of Denmark,IMM-REP-1998-7. Hoogeveen,H.,2005.Multicriteria scheduling.European Journal of Operational Research167,592–623. Janiak,A.,Kovalyov,M.Y.,Kubiak,W.,Werner,F.,2005.Positive half-products and scheduling with controllable processing times. European Journal of Operational Research165,416–422. Karabati,S.,Kouvelis,P.,1997.Flow-line scheduling problems with controllable processing times.IIE Transactions29,1–14. Kayan,R.K.,Akturk,M.S.,2005.A new bounding mechanism for the CNC machine scheduling problems with controllable processing times.European Journal of Operational Research167,624–3. Lamond,B.F.,Sodhi,M.S.,1997.Using tool life models to minimize processing time on aflexible machine.IIE Transactions29,611–621. Malakooti,B.,Deviprasad,J.,19.An interactive multiple criteria approach for parameter selection in metal cutting.Operations Research37(5),805–818. Murty,K.G.,Kabadi,S.N.,1987.Some NP-complete problems in quadratic and nonlinear programming.Mathematical Programming39, 117–129. Nowicki,E.,Zdrzalka,S.,1990.A survey of results for sequencing problems with controllable processing times.Discrete Applied Mathematics26,271–287. Shabtay,D.,Kaspi,M.,2004.Minimizing the total weightedflow time in a single machine with controllable processing times.Computers and Operations Research31,2279–22. S.Gurel,M.S.Akturk/European Journal of Operational Research177(2007)325–343343 Smith,W.E.,1956.Various optimizers for single stage production.Naval Research Logistics Quarterly3,59–66. Tuyttens,D.,Teghem,J.,Fortemps,P.H.,Van Nieuwenhuyze,K.,2000.Performance of the MOSA method for the bicriteria assignment problem.Journal of Heuristics6,295–310. Vickson,R.G.,1980a.Choosing the job sequence and processing times to minimize processing plusflow cost on a single machine. Operations Research28,1155–1167. Vickson,R.G.,1980b.Two single-machine sequencing problems involving controllable job processing times.AIEE Transactions12,258–262. Wan,G.,Yen,B.P.-C.,Li,C.-L.,2001.Single machine scheduling to minimize total compression plus weightedflow cost is NP-hard. Information Processing Letters79,273–280. Wu,J.,Azarm,S.,2001.Metrics for quality assessment of a multi-objective design optimization solution set.Journal of Mechanical Design123(1),18–25. Zitzler,E.,1999.Evolutionary algorithms for multi-objective optimization:Methods and applications.Ph.D.dissertation,Shaker Verlag, Aachen,Germany. Zitzler,E.,Thiele,L.,1998.Multiobjective optimization using evolutionary algorithms—A comparative case study.In:Eiben,A.E.et al. (Eds.),Parallel Problem Solving from Nature(PPSN V).Springer,Berlin,Germany,pp.292–301. Zitzler,E.,Thiele,L.,Laumans,M.,Fonseca,C.,Fonseca,V.G.,2003.Performance assessment of multi-objective optimizers:An analysis and review.IEEE Transactions on Evolutionary Computation7(2),117–132.
Copyright © 2019-2026 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
