Abstract: A model for machining parameter optimization in multi-batch and multi-job is built based on cost analysis. In order to minimize the whole cost, the scheduling rules are employed for the machining parameter optimization during scheduling course with Genetic Algorithm (GA). An example of corporation based on the model and algorithm is developed to validate the rationality of modeling and validity of algorithm. Computational result shows that the new fashion of manufacture model proposed in this paper is advanced for cost control.
INTRODUCTION
Machining parameter optimization and job scheduling are the most important factors for cost control because the machining parameters can determine the processing time which influences the schedule. The research about machining parameter optimization was in-depth for one job to minimize the cost. For example, Budake et al. (1996) educed an approach and Saravanan et al. (2001) thought that genetic algorithm was the right approach for machining parameter optimization. Moreover, the model and algorithm of scheduling for minimum cost also emerged endlessly. Rohleder and Scudder (1993) compared both types of economic objectives and built a dynamic job shop model with computer simulation. Shafaei and Brunn (1999) found that the raw material cost and income of jobs were constant so, the formula for operating costs can be found. At present, the problem that how to make the machining parameter optimization of multi-job is still hard to solve. Vickson (1980) studied the scheduling problem in which the processing time can be controlled. Biskup and Cheng (1999) researched the problem that the cost function related to the control of the processing time was generally a linear function taking the form of addition. Chen and Zheng (2001) discussed the kind of single machine scheduling problem with controllable processing times. However, these researches simplified the relation between processing time and processing cost as linearity. In fact, the machining parameters which determine the processing time and influence the schedule, have very complex relation to the cost.
Moreover, In modern manufacture corporation, the jobs usually arrive the shop in the light of batches. When the arriving times of batches are different, the influence from subsequent batches to anterior batches scheduled also affects the whole cost (Church and Uzsoy, 1992; Jain and Elmaraghy, 1997). Hence, a new model will be proposed in this paper to realize cost control. The model, facing multi-batch and multi-job, can be employed to optimize the machining parameters during the scheduling course and to deal with the relation between rescheduling and cost well.
MODEL CONSTRUCTION
The cost, changed with the variety of processing parameters includes three parts: processing cost, tool cost and logistics cost (Ballfou, 1999). In addition, the penalty cost and the rescheduling cost should be considered on account of the due time and rescheduling.
Coefficient Si can be synthesized to express the metal removal rate from previous operation to next operation and the assistant time toi is a constant for each operation. So the processing cost is stated as follow; (Suffix i expresses job i in each batch, herein after the same):
| (1) |
where, Cm is mobile cost per unit time, Co is assistant cost per unit time. Tool cost is that:
| (2) |
where, ta is tool-exchange time, Ct is the cost of one tool, CT is tool life coefficient and m1, m2, m3 express separately to the influence of v, f, ap.
Minishing the WIP buffers and shortening the circulation time is propitious to cost control (Faria et al., 2006). Then the WIP cost is that (Pinedo, 1995):
| (3) |
where Pi, complete time of the job, expresses the whole time from ready to complete and wi is the WIP cost per unit time.
The penalty cost is described as follow (Suffix j expresses batch j, hereinafter the same):
| (4) |
where Qj is the due time of the batch and lj is the coefficient of tardiness.
A coefficient r is used to express the increase proportion and rescheduling cost is denoted as follow:
| (5) |
In the equation, if the job i need not be rescheduling, r = 0.
The objective function for m batches, in which there are n jobs, processed on one machine is as follow:
| (6) |
When the processing time is known that is to say, the machining parameters are certain and unchangeable, it is a NP-hard question for different batches of jobs arrived at different time (Pinedo, 1995). So a pseudo polynomial algorithm based on the conclusion of Lawler (1977) can be put forward to get the optimal schedule on certain machining parameters. The algorithm is described as follow:
| Step 1: | Observe the processing state of machine if there is new batch arriving. If machine is not working that is to say a job is just complete, transfer to step 2. If machine is working, namely a job is being processing, wait for the completion of the job and transfer to step 2. If all the jobs are complete, transfer to step 8 |
| Step 2: | Arrange all the unprocessing jobs as a schedule with weighted shortest machining time first (WSPT) rule (Pinedo, 1995) and calculate the whole cost. Remember the cost and its corresponding schedule and transfer to step 3 |
| Step 3: | Setup the priority of jobs in the sequence in the light of the due time of the batch that jobs belong to. The priority is from 1 to m. where m denotes the quantity of the batches in the schedule. For example, if the jobs in the schedule belong to 3 batches respectively, m is equal to 3. The less the due time of the batch that jobs belongs to is, the higher priority the job has. The 1 is assigned to variable “flag” and transfer to step 4 |
| Step 4: | Choose the jobs whose priority are equal to the value of variable “flag”. And mark the job which is the last one in these jobs, in the schedule. Transfer to step 5 |
| Step 5: | Pick up the job whose priority is greater than the value of variable “flag” and which is the nearest one from the marked job to the front. Then insert this job behind the marked job and transfer to step 6 |
| Step 6: | Calculate the whole cost on current schedule and remember it. If there is no job whose priority is greater than the value of variable “flag” before the marked job, transfer to step 7. Otherwise, transfer to step 5 |
| Step 7: | Plus 1 to the value of variable “flag” and judge it. If the value of variable “flag” is equal to m, transfer to step 8. Otherwise, transfer to step 4 |
| Step 8: | Select the least whole cost from all the whole cost remembered as the optimal whole cost and regard its corresponding schedule as the optimal schedule |
The algorithm is not only tallying with processing request but easy and feasible.
GENETIC ALGORITHM
Genetic Algorithm is used in this paper to optimize the machining parameters and schedule for minimum cost with different batches.
Usually, ap is decided by cutting allowance, so the variables for optimization are v and f. There are five kinds of restrictions existing in processing course: restriction of rotate velocity of principal axis, restriction of feed rate, restriction of machine power, restriction of surface roughness and restriction of cutting force (Armarego, 1994). The ranges of variables are determined by these five kinds of restrictions.
The length of one chromosome is m+k. where, m and k are determined by precision. In this study, m = k = 3. Random selection is employed to generate the initial population and its dimension is 400. The calculation course of fitness of one chromosome is that: first, translate the chromosome into machining parameters namely fij, vij. Second, calculate the processing time of each job with these machining parameters. Third, utilize the model and the algorithm introduced in 1.8 to calculate the whole cost as the fitness of this chromosome.
The selection operator is used by roulette selection and the probability of selection is 0.2. On account of large scope of individual, uniformity crossover can augment search bound with 0.7 probabilities. In order to advance the search efficiency, 0.1 probabilities are adopted to uniformity mutation 15. The genetic algorithm will stop after 1000.
EXAMPLE
The simulation is for the cylindrical finish machining of roller with HT125 lathe in Shanghai Jingzheng mechanical equipment Ltd. The parameters of machine and tool are mentioned in Table 1.
Example: Two batches arrives at workshop orderly and the alternation is 15000 sec. The dimension, single border cutting allowance, surface roughness and value of S (S = DxLxA/1000) and other parameters are mentioned in Table 2.
| Table 1: | Experimental conditions |
In order to compare each other expediently, the whole cost will be calculated by three approaches:
| • | Approach 1: As the traditional fashion of company, choose the right machining parameters for minimum cost of each operation firstly and then arrange the processing schedule with determinate processing time. The approach introduced by Saravanan et al. (2001) will be employed to choose the right machining parameters for minimum cost of each operation If there is another batch of jobs arriving, the rescheduling will not be executed. That is to say, the subsequent batches must be processed after the completion of anterior batches |
| • | Approach 2: The model built in this paper for machining parameter optimization during the scheduling course are used for minimum cost in one batch of jobs. For different batches, the approach is same as that of approach 1 |
| • | Approach 3: The model and rule for different batch of jobs put forward in this paper are used |
According to these three approaches, the above example are shown in Table 3.
Table 3 shows that the whole cost of approach 3 are minimum. In addition, the fact that approach 2 and approach 3 are both superior to approach 1 shows that the machining parameter optimization during the scheduling course is better for cost control.
When the second batch of jobs arrived after 100 sec, the first batch of jobs was being processed in the light of arranged schedule and parameters. At 15000 sec, the second job of first batch was being processed which caused that the rescheduling occurred at the completion of J2, so J2 and J3 obeyed the former machining parameters and other jobs of first batch obeyed the result of rescheduling.
| Fig. 1: | Relation between the change of whole cost and different arriving time |
| Table 2: | Parameters of jobs |
| In addition, Q = Q’ = 1000, l = l’ = 0.02, r = r’ = 0.05, ’This job belongs to the second batch | |
Influence of different arriving time to whole cost: The curves of Fig. 1 are used to denote the change of whole cost along with different arriving time. In the Fig. 1, the curve of approach 2 is got by 4 times polynomial fitting and each subsection of approach 3 is fit by two time’s polynomial.
Figures 2-4 shows, that the whole costs descend along with the arriving time increasing but the trend becomes moderating. The reason for moderating is that the percentage of WIP cost and penalty cost descends. To approach 3, the arriving time affects the number of jobs participating in the rescheduling and affects the machining parameters and schedule of jobs. Therefore, the curve has the shape of subsection and the time of each subsection point is the time for substitutions of the jobs of first batch.
In addition, along with the arriving time increasing, the difference between the whole costs of the two approaches is less. It shows that the more jobs participating in the rescheduling, the better effect for cost control.
Influence of rescheduling cost coefficient r: The curve to denote the change of whole cost along with rescheduling cost coefficient r is as Fig. 2, 3 and 4 with 4 times polynomial fitting.
Figures 2-4 shows that the whole cost increases along with r increasing linearly and to judge by the value of y-axis, the slope of the line will be minished along with the arriving time increase. The reason is that along with the arriving time increasing, the number of jobs participating in rescheduling descends and the influence of rescheduling to the whole cost is weakened.
| Table 3: | Calculation result |
| Fig. 2: | Relationship between r and whole cost for 5000 sec |
| Fig. 3: | Relationship between r and whole cost for 25000 sec |
| Fig. 4: | Relationship between r and whole cost for 48000 sec |
| Fig. 5: | Change for available range of r along with arriving time |
In addition, when r increases to some value, the whole cost with approach 3 will greater than the cost with approach 2. That is to say, the validity of rescheduling for cost control is limited by the rescheduling cost coefficient. The valid range can be changed with arriving time of jobs and the changing law can be described by the curve with 2 times polynomial fitting in Fig. 5.
Therefore, we can judge the value of rescheduling according to the Fig. 5. If the coordinate locate above the curve, then the rescheduling lost the significance. Contrarily, the farther the coordinate leave the curve below the curve, the more significant the rescheduling is. So how to use rescheduling correctly should be considered cautiously in the light of production status.
CONCLUSION
This study built the model for multi-job and multi-batch single machine scheduling to optimize the machining parameters during scheduling. The validity of model and algorithm are validated by the an example. According to the research, the conclusions as follow can be summarized:
| • | In multi-job and multi-batch single machine scheduling, machining parameters optimization during the scheduling course is more effective for cost control |
| • | The whole costs descend along with the arriving time increasing but the trend is unmonotone and becomes moderating. The value of whole cost is discontinuous at the job-substitution time of last batch |
| • | The whole cost increases along with r increasing linearly and the slope of the line will be minished along with the arriving time increasing |
| • | The valid range of rescheduling can be changed with arriving time of jobs as a parabola |