Minimization of flow time and tardiness by swapping of dispatching rules.

Singh, A. ; Mehta, N.K. ; Jain, P.K. 等

Abstract: This paper uses multi criteria algorithm for swapping of dispatching rules for implementing several criteria simultaneously in a shop of dynamic nature. Mean flow time, maximum flow time, mean tardiness and maximum tardiness performance measures are considered for performance evaluation. In order to find the processing sequence, dispatching rules have been applied and the performance of the system has been monitored continuously. Swapping of dispatching rules is allowed only when the performance index deviates from the pre-defined limit. The selection of dispatching rules is made by identifying the worst performing criterion. A rule which can improve system performance for the worst performing criterion is selected to dispatch the part under consideration.

Key words: Swapping, Dispatching rules, multi-criteria scheduling, Priority index, performance improvement.

1. INTRODUCTION

Scheduling is an important function during part manufacturing. Scheduling may be defined as the allocation of limited number of resources (machine, tool, fixture, operator, material handling equipment) to each task of a job over time. Scheduling may be static or dynamic. The nature of job arrivals provides the distinction between static and dynamic scheduling. In static scheduling a certain number of jobs arrive and become available simultaneously in a shop. However, in dynamic scheduling, jobs arrive intermittently, at times that are predictable in a statistical sense, and arrivals continue indefinitely into the future. Hence, entirely different methods are required to solve the problem of scheduling in these two cases. The main objective of the scheduling problem is to optimize various performance measures, singly or jointly. A solution that is optimal for a given criterion may not be optimal for some other criterion. In many practical situations, it would be thus desirable to achieve a solution that is best with respect to a number of different criteria simultaneously. The research on bi-criteria and multi-criteria scheduling can be categorized in four different types of models, viz. single machine-bi-criteria scheduling, single machine-multiple criteria scheduling, multiple machine-bi-criteria scheduling and multiple machine-multi criteria scheduling. Most of the research done so far on multiple criteria scheduling involves only a single machine or two-machine flow shop (Gupta et al. 2000, Lio et al. 1997 and Rajendran, 1992). Multiple machines and multi-criteria scheduling represent the most general class of scheduling problems as most shop floors employ more than one machine. Hence, multiple machine scheduling models have extensive practical applications. Literature review revealed that there is a scarcity of research in this direction, apparently due to the complex nature of scheduling problem. The present work is an attempt in this direction by using a multi criteria algorithm proposed by the authors in their previous work (Singh et al. 2004). Mean flow time, maximum flow time, mean tardiness and maximum tardiness performance measures have been considered simultaneously for performance evaluation. The features of the algorithm are given in the subsequent sections.

2. MULTI-CRITERIA METHODOLOGY (MCM) FOR SWAPPING OF DISPATCHING RULES

Consideration of more than one performance measure during scheduling is an important aspect in the scheduling problems. In dynamic scheduling problems generally dispatching rules are used to find the solution of the problems. In literature it has been found that a rule that is best for a given performance measure may give poor performance for others. Hence, it is necessary to select the dispatching rules in such a way that the system gives better performance with respect to multiple performance measures. This issue is considered in the present work by using an algorithm that is developed by the authors in their previous work to minimize / maximize several performance measures simultaneously. The readers can refer Singh et al. (2004) for the details of the algorithm. The salient features of the algorithm are as follow:

* The algorithm considers several dispatching rules simultaneously.

* It continuously monitors the attained value of the performance measures.

* The selection of dispatching rule is made by identifying the worst performance measure.

* A dispatching rule which improves system performance for the worst performance measure is selected.

* This algorithm improves one performance measure at the cost of others such that the gain from improvement in one measure is more than the deterioration in the performance of the other measure.

* Again, the worst performance measure is identified and the steps are iteratively repeated till the end of the simulation period.

3. SIMULATION MODEL

In the present simulation study three system types have been considered with varying job to machine (J/M) ratio (i. e. J/M > 1, J/M = 1, J/M < 1) for evaluation of the effectiveness of the proposed methodology. The number of operations for each job type is assumed to be uniformly distributed in the range of (1-9) with uniformly distributed processing times in the range of (1-99). Job arrival in the system is assumed to follow exponential distribution with mean inter-arrival time between parts based on shop utilization. As the performance of multi criteria methodology is evaluated in the presence of machine breakdowns, down time of individual machines has been incorporated irrespective of whether it occurs due to tool breakage, tool adjustment, machine breakdown etc. However, breakdowns, such as those due to power failure, that affect the whole system are not considered. Mean time between failure (MTBF) and mean time to repair (MTTR) are assumed to follow Gamma distribution. In the present study, busy time approach has been chosen for generating the breakdown times (i. e. a machine can fail only while performing an operation on a job). Law and Kelton (2000) suggested that in the absence of real time data busy time distribution is most likely to be a Gamma distribution with a shape parameter of 0.7. They also suggested that Gamma distribution with a shape parameter of 1.4 is appropriate for generating the repair time. Thus the busy time between two successive failures (i.e. inter-breakdown time) is assumed to follow a Gamma distribution with [alpha] = 0.7 and [beta] = MTTR x e/ (1-e) x 0.7 and the duration of each breakdown (which is also known as repair time) is also assumed to follow a Gamma distribution with [alpha] = 1.4 and [beta] = MTTR/1.4. Where,

e = MTBF/(MTBF + MTTR) (1)

In the present work, simulation models have been developed in PROMODEL simulation software. Each simulation model has been run for 2000 completed jobs after attaining a steady state.

4. EVALUATION OF MCM

The improvement in the system performance by using the multicriteria methodology is calculated by using the following relationship.

Percentage improvement = ([PI.sub.i] - [PI.sub.0])/ [PI.sub.0] x 100 (2)

Where [PI.sub.i] is the performance index of the system by swapping of dispatching rules and [PI.sub.0] is the minimum performance index obtained by using the individual dispatching rules.

A manufacturing system is defined by two sets of parameters: system operating parameters and system configuration parameters. The system operating parameters are breakdown level (BL) and mean time to repair (MTTR), while the system configuration parameters are job to machine (J/M) ratio, part complexity (PC) and part mix (PM). In the present work five breakdown levels i.e. 0%, 2.5%, 5%, 7.5% and 10%, five mean time to repair levels i. e. p, 2.5p, 5p, 7.5p and 10p, three part complexity (PC) levels i. e. 4, 5 and 6, three job to machine (J/M) ratio levels i. e. J/M > 1, J/M = 1 and J/M < 1 and three part mix (PM) levels have been considered. In the first part mix(PM1), it is assumed that all part types have equal volume of production. The second (PM2) and third (PM3) part mix have been generated by considering the industrial data given by Muhlema (1982). Here, part complexity is defined by the average number of operations needed to complete the processing of a job.

The system performance has been investigated for two environments viz. by varying system operating parameters with constant system configuration parameters (VOP-CSCP) and varying system configuration parameters with constant system operating parameters (VSCP-COP). The dispatching rules considered while investigating the (VOP-CSCP) and (VSCPCOP) environments are described below.

5. RESULTS AND DISCUSSION

In the present work, seventeen dispatching rules viz. SPT, EDD, FIFO, ODD, AT, AT-RPT, FDD, PT+PW, PT+PW+FDD, PT+PW+ODD, WTIS/TPT-RPT, (WTIS/PT)min, (WTIS/PT)max, PT+WTIS, FDD+WTIS/TPT-RPT, ODD+ WTIS/TPT-RPT and (WTIS)max have been considered and simulation has been carried out by taking one rule at a time. Where, ODD = operational Due Date, AT = arrival time, RPT = remaining processing time, FDD = flow due date, PT = process time, PW = process wait, WTIS =Waiting time in system. After each simulation run the values of mean flow time, maximum flow time, mean tardiness and maximum tardiness have been collected. In the final simulation run all the rules have been considered in the minimization of above performance measures simultaneously and the rules are switched over from one to another on the basis of deterioration in the performance measures. The results are presented in terms of percentage improvement obtained by applying the multi criteria algorithm in comparison with the best performing individual dispatching rule. Table 1 shows the performance improvement at several levels of part complexities, J/M ratio and part mix. Performance improvement of 20.93% and 16.19% has been observed when J/M>1 and J/M<1 respectively. This trend indicates that an increase in J/M ratio increases the percentage improvement in the performance. Results also show that the performance improvement at higher values of part complexities is more in comparison to lower values of part complexities. The results of Table 2 indicate that as the breakdown level increases improvement in the performance decreases. In all the taken cases, the multi-criteria methodology improves the performance in the range of 12.17% to 28.73%.

6. CONCLUSION

The present work uses the multi-criteria methodology and minimizes flow time based and tardiness based performance measures simultaneously. The performance of the multi criteria methodology has been studied by considering several values of job to machine ratio, breakdown parameters, part complexity and part mix. It has been demonstrated that under different conditions the system performance improves between 12.17--28.73% by swapping the dispatching rules when the deterioration in the worst performing measure reaches a predefined limit.

7. REFERENCES

Gupta, JND.; Ho, Jc. & Webster, S. (2000). Bi criteria optimization of the make span and mean flow time on two identical parallel machine, Journal of Operational Research Society, Vol.51, No.11, pp. 1330-1339.

Lio, C. J.; Yu, W. C. & Joe, C. B. (1997). Bi-criteria scheduling in the two machine flow shop, International Journal of Production Research, Vol.53, No.9, pp. 1004- 1015.

Rajendran, C. (1992). Two-stage flow shop scheduling problems with bi-criteria, Journal of Operational Research Society, Vol.43, No.9, pp. 871-884.

Conway Richard, W.; Maxwell William, L. & Miller Louis, W. (1967). Theory of scheduling, Addition-Werley publishing company.

Singh, A.; Mehta N. K. & Jain P. K. " A multicriterion approach for dynamic scheduling" The 15th INTERNATIONAL DAAAM SYMPOSIUM, 3-6 November 2004, Vienna, Austria, pp. 419-420.

Table 1 Percentage improvement in (VSCP-COP) environment
in comparison to the best performing individual dispatching rule

Part mix Part Percentage improvement
 complexity J/M>1 J/M=1 J/M<1

PM1 4 20.93 17.26 19.18
 5 27.54 20.16 25.00
 6 28.73 25.83 25.45
PM2 4 20.17 12.17 16.92
 5 27.30 13.16 17.51
 6 28.53 14.17 19.11
PM3 4 16.19 14.36 14.31
 5 18.54 14.59 14.52
 6 19.26 17.05 14.33

Table 2 Percentage improvement in (VOP-CSCP) environment
in comparison to the best performing individual dispatching rule

 MTTR Breakdown level (BL)
 0% 2.5% 5% 7.5% 10%

 2.5p 28.56 27.85 26.77 26.19 16.11
 5p 28.56 26.19 23.43 18.77 14.52
 7.5p 28.56 21.04 23.71 20.21 16.32
 10p 28.56 20.86 24.59 21.03 16.56