Printer Friendly

Minimization of mean tardiness in a flexible job shop.

1. INTRODUCTION

In today's dynamic market environment flexibility in planning, manufacturing and decision making plays a key role in order to cope up the market uncertainties. Hence, flexible job shops have emerged as the most promising manufacturing system for today's market oriented, low volume, large variety production. In uncertain market environment, the manufacturing systems can achieve their high productivity goals and customer service level requirements by increasing their reactive production capacity and it can be increased by increasing total capacity, number of workers and working hours or by reducing the manufacturing lead time and raw material lead time. Scheduling is one of the important operational functions of a manufacturing system that can improve productivity by reducing the manufacturing lead time.

Reported literature on scheduling can be classified as deterministic and stochastic problems, single machine and multi-machine problems (1), static and dynamic problems and single criterion and multi criterion problems (2), (3). Dynamic scheduling problems are more complex than static scheduling problem and generally dispatching rules are used to solve the dynamic scheduling problems (4). Nowadays, most of the manufacturing systems face uncertainties related to machine breakdowns, demand unpredictability, order cancellations, rush orders etc. In this regard, generation of modified schedules or real time schedules are essential for better utilization of resources while minimizing the impact of market and system uncertainties. Further, these uncertainties cannot be handled by the dispatching rules only. Machine breakdown is one of the most common problems faced by shop management during scheduling (5-8). When a machine breakdown occurs, system needs flexibility in order to cope up the negative impact of these breakdowns and at the same time, a decision has to be needed whether the new incoming jobs and the jobs in the queue of the failed machine should remain in the queue of the failed machine or be transferred to an alternative machine by using routing flexibility. The repositioning of the queue of the failed machine is a typical decision that affects the performance of the system. During repositioning it has to be decided that how many and which one jobs to be rerouted and which one stay in the queue of the failed machine. One more important issue is positions of the rerouted jobs in the queue of the alternative machine. In the present work, these issues are accommodated in selective rerouting approach in which jobs are selectively rerouted to the alternative machine to cope up the impact of breakdowns and this approach is validated by comparing it with the existing rerouting approaches.

Aytug (5) reported the state of the art survey on scheduling with uncertainties and categorized the research into three groups, namely predictive reactive scheduling, completely reactive scheduling and robust scheduling. Rescheduling is a process of updating an existing production schedule in response to disruption or other changes on the shop floor. These unexpected events (disruptions) which can change the system status and affect performance are called rescheduling factors (9). Machine failure, hot job arrival, job cancellation and due date change are the most common rescheduling factors researched in rescheduling / reactive scheduling studies. If any of these events occurs on to the shop floor then their impact can be reduced by taking corrective actions such as provision of overtime, process change or rerouting and machine substitution as a part of the rescheduling / reactive scheduling exercise (10).

Kutanoglu and Sabuncuoglu (11) explain reactive scheduling as "if the point of corrective action coincides with the disruption point then the scheduling is termed as reactive scheduling" (i.e. rescheduling point coincides with the failure time). They compared four reactive scheduling policies under machine breakdowns. These policies (i. e. all rerouting, arrival rerouting, queue rerouting and no rerouting) are tested using a job shop simulation model. A material handling system is also considered in the model. The results of their study indicate that all rerouting is a preferred reactive policy when the material handling system is ignored. They further investigated the performance of four reactive policies under machine breakdown and conclude that if downtime is very short then no rerouting policy performs well. However, if downtime is very large then rerouting of queue as well as the new arrivals gives improved results. Kamrul et al. (12) investigated the reactive scheduling problem in job shop environment in the presence of machine breakdowns. Sabuncuoglu and Kizilisk (13) have studied the reactive scheduling problems in a dynamic and stochastic manufacturing environment. Specifically, they have developed a simulation based scheduling system for FMS and proposed several reactive policies (i. e. when to schedule and how to schedule policies) and test their performances under various experimental conditions. In their investigation they concluded that variable time response is better than

fixed time response, full scheduling scheme is better than partial scheduling and on line scheduling is more robust to uncertainties than the optimum seeking off line scheduling. Dynamic scheduling technique is reactive in the sense that it takes into account the disruption and adjusts the scheduling decision accordingly (11), (13). It is also called priority dispatching, where an on-line schedule is generated over time by choosing the highest priority job when a machine becomes available. Cowling and Johansson (14) have developed a general framework for using real time information's to improve scheduling decisions and they have demonstrated the application of their framework on a single machine system. Zandieh and Adibi (15) proposed a scheduling method to address a dynamic job shop scheduling problem based on variable neighbourhood search in the presence of machine breakdowns. The drawback of their approach was that it could not have utilized the advantage of routing flexibility to improve the performance of the system. Lee et al. (16) addressed a small size flexible job shop problem in static environment by considering AND/OR precedence constraints. Chen and Chen (17) have addressed dynamic scheduling problem of random FMS in the presence of shop floor disruptions. They have proposed an adaptive scheduling approach to make coupled decisions about the part/machine scheduling and operation/tool assignments on rolling time horizon basis. Finally, they reported that the proposed real time scheduler significantly outperforms dispatching heuristics under different shop load levels and machine breakdown levels.

In practice, a typical scheduling environment is dynamic and requires continuous updating. Hence, discrete event simulation models are used for the reactive scheduling system. Kia et al. (18) investigated the dynamic scheduling of flexible flow line through simulation. They have considered sequence-dependent setup times in their study. Kim and Kim (19) proposed a simulation based scheduling system with two major components, i. e. simulation mechanism and reactive control. The simulation mechanism evaluates various rules and selects the best one for a given job population and performance criteria. Later Jeong and Kim (20) refined the functions and modules of the previous scheduling mechanism and tested several rescheduling policies. Metan et al. (21) proposed a scheduling system by using real time selection of scheduling rules and knowledge extraction through dynamically controlled data mining.

As discussed above, not much work has been done in this category, where the scheduling tool is priority dispatching and the reactive policies involve updating the priorities. It is also observed that the majority of the studies treat reactive scheduling problem as rescheduling of all the jobs. Hence, there is a need to develop efficient reactive policies, which can improve the performance of the priority heuristics due to the impact of shop floor disruptions. Hence, to full fill the gaps of the literature review author developed the selective rerouting algorithm in his previous work (22). In the present work, the simulation study of the selective rerouting algorithm has been carried out in the flexible job shop environment. The results of the simulation study were compared with the existing rerouting algorithm, i.e. no rerouting, all rerouting, queue rerouting and arrival rerouting. In scheduling problem two important performance measures are flow time and tardiness to measure the performance of the system. The flow time of a job is the difference between the exit time to the entry time in the shop whereas tardiness is the difference between due date to the exit time of a job from the shop. In the present work tardiness is considered to measure the performance of the shop.

2. REROUTING METHODOLOGIES

A few scheduling techniques are naturally reactive in the sense that they consider disruptions and adjust the scheduling decisions accordingly. One such technique is dynamic scheduling, also called priority dispatching, where an on-line schedule is generated over time by choosing the highest priority job when a machine become available. Even if the priority dispatching technique is reactive in nature, one can improve these heuristic techniques by using additional policies specifically designed to reduce the effect of disruptions. For example, the performance of priority dispatching based scheduling can be enhanced by using explicit reactive policies (rerouting policies) against machine failure. Some of the rerouting approaches are given below.

2.1 Selective rerouting approach

The authors have reported selective rerouting approach based on lateral entry of critical jobs in queue of the alternative machine in their previous work (22). In this paper this approach has been employed in a flexible job shop and the inferences drawn from the research are discussed in the subsequent sections. In the implementation of selective rerouting approach, dispatching rules has been considered as the scheduling tool. There are random breakdowns on each machine and hence selective rerouting is also considered to reduce the impact of breakdowns and enhance the performance of dispatching rules. The priority index of waiting jobs on each machine is decided by using the (EDD) dispatching rule. In case of any tie in the value of priority index then first in first out (FIFO) rule is used for break the tie. It is assumed that each job in the manufacturing system will follow its current route till the next required machine breaks down. If any machine breaks down during processing then at first, all the jobs waiting behind the failed machine are rearranged on the basis of a priority index calculated by using the earliest due date. Jobs are considered for rerouting on the basis of their above assigned priority index. Rerouting decision is made on the basis of completion time on failed machine and the completion time at each of the alternative machines with appropriate queue discipline. The steps are explained below:

Step 1. Prioritize the queue of the parts at the failed machine (say k) on the basis of earliest due date (EDD) and select the first part for rerouting (say job j). The queue of parts is prioritized only to decide the sequence of the jobs for rerouting. It may be noted that the sequence of parts at the failed machine is not changed due to the above prioritization.

Step 2. Calculate the completion time for the selected job at the failed machine by summing up the processing time of the selected job j, the processing times of the jobs ahead of job j and the remaining down time of failed machine k as given below.

[c.dub.jk] = [i=n.summation over (i=1)][P.sub.ik] = [d.sub.k] (1)

where, n is the position of the selected job in the queue of the failed machine k,

[i=n.summation over (i=1)][P.sub.ik]--Sum of processing times of the jobs from position 1 to n on failed machine k,

[d.sub.k]--Remaining down time of the failed machine.

Step 3. Identify the alternative machines (for job j) by taking routing flexibility into consideration and determine the new position (say m) of the part j in the queues of the alternative machines by using the number of operations remaining criterion. Thus, provision of lateral entry in a suitable position in the queue at the alternative machine is made for all parts. Processing time of the selected job j on the alternative machine may change due to different capability of the alternative machine. Calculate the completion time on each of these machines for the selected job j by using the relationship given below:

[c.sub.ja] = [P.sub.ja] + [i=m-1.summation over (i=1)][P.sub.ia] + [P.sub.ra] (2)

where, [P.sub.ja]--Processing time of job j on the alternative machine (say a),

[P.sub.ra]--Remaining processing time of the job on the machine,

m--Position of the rerouted job in the queue of the alternative machine a,

[i=m-1.summation over (i=1)]--Sum of processing times of all the jobs ahead of job j from position 1 to (m-1).

Step 4. Rerouting of job j will increase the completion time of each job after position m on the alternative machine and decrease the completion time of each job after position n at the failed machine. This net global effect is calculated for each of the alternative machines and summed up as below:

Net global effect = ([P.sub.ja] x q(a)) - ([P.sub.jk] x q(k)) (3)

where, q(a)--Number of jobs after mth position at the alternative machine,

q(k)--Number of jobs after nth position at the failed machine,

[P.sub.jk]--Processing time of job j on the failed machine k,

[P.sub.ja]--Processing time of job j on the alternative machine a due to the different capability of the alternative machine.

Step 5. Calculate the effective completion time ([c.sub.ja(e)]) of the rerouted job on each of the alternative machines and select the alternative machine with minimum ([c.sub.ja(e)]) among all the alternative machines. ([c.sub.ja(e)]) is calculated as follows:

[c.sub.ja(e)] = [c.sub.ja] + Net global effect (4)

If [([c.sub.ja(e)])]min < [c.sub.jk], then reroute the job j to the alternative machine a otherwise let the job j wait in the queue of the failed machine.

Step 6. Repeat steps 1 to 5 for all the jobs in the queue of the failed-machine after every event.

2.2 Other rerouting policies

Selective rerouting approach has been compared with the all-rerouting, queue rerouting and arrival rerouting policies along with the no-rerouting policy that is included here as a benchmark policy. The steps of these rerouting policies are given in the following table (11).

3. SIMULATION MODEL

Modelling of manufacturing systems can be done either through simulation models or analytical models. Analytical modelling tools are based on Markov chains, queuing theory, Stochastic Petri Nets (SPN) (23) and have wide applications in manufacturing. Modern manufacturing is characterized by high levels of automation and integration, complex interactions among system elements, and high capital costs. Integration and automation makes the manufacturing system so complex that models of these systems cannot be solved by using the analytical tools. In these cases, computer based simulation remains one of the most widely used tool of evaluating system performance with the help of the simulation output data. Simulation can be employed to determine the effect of an alternate policy without disturbing the real system. It helps us in deciding the best policy with the prior assurances that its implementation will certainly prove to be beneficial to the organization. Decision makers have for long used the simulation technique in complicated problems of decision-making. Modelling and simulating of manufacturing systems can be achieved using a number of tools and techniques one of which is discrete event simulation.

Simulation models have been developed in ProModel[R] simulation software by considering ten machines and ten part types to compare the performance of selective rerouting algorithm with the rerouting approaches described in section 2.2. The number of operations for each job type is assumed to be uniformly distributed in the range of (2 - 9) with uniformly distributed processing times in the range of (1 - 9). Each operation allows one alternative operation using one machine as alternative machine. The part types are permitted to visit the machines in different operation sequences. The operation sequence along with alternative machine of each part type is given in Table II. The inter-arrival times for jobs are generated by exponential distribution with mean inter-arrival time between parts based on shop utilization as calculated from Eq. (5). [bar.P] If represents the mean processing time of a job, M is the number of machines and [U.sub.s] the shop utilization, the mean inter-arrival time is calculated by the following relation (17):

Table II: Processing sequence data (figures in ( ) are the alternative
machines).

Part
Type

           i           ii           iii           iv

1       [M.sub.3]    [M.sub.8]     [M.sub.9]
      ([M.sub.2])  ([M.sub.5])  ([M.sub.10])

2       [M.sub.3]    [M.sub.6]     [M.sub.7]    [M.sub.8]
      ([M.sub.1])  ([M.sub.4])   ([M.sub.5])  ([M.sub.9])

3       [M.sub.2]    [M.sub.4]     [M.sub.6]   [M.sub.10]
      ([M.sub.3])  ([M.sub.1])   ([M.sub.4])  ([M.sub.7])

4       [M.sub.1]    [M.sub.3]     [M.sub.5]    [M.sub.6]
      ([M.sub.3])  ([M.sub.2])   ([M.sub.6])  ([M.sub.4])

5       [M.sub.4]    [M.sub.1]    [M.sub.10]    [M.sub.3]
      ([M.sub.2])  ([M.sub.5])   ([M.sub.6])  ([M.sub.8])

6       [M.sub.1]    [M.sub.4]     [M.sub.5]    [M.sub.7]
      ([M.sub.3])  ([M.sub.2])   ([M.sub.7])  ([M.sub.5])

7       [M.sub.3]    [M.sub.5]     [M.sub.9]    [M.sub.6]
      ([M.sub.1])  ([M.sub.2])   ([M.sub.3])  ([M.sub.4])

8       [M.sub.4]    [M.sub.3]     [M.sub.1]    [M.sub.2]
      ([M.sub.1])  ([M.sub.2])   ([M.sub.8])  ([M.sub.3])

9       [M.sub.1]    [M.sub.6]     [M.sub.2]    [M.sub.8]
      ([M.sub.3])  ([M.sub.2])   ([M.sub.5])  ([M.sub.7])

10      [M.sub.4]    [M.sub.6]     [M.sub.9]    [M.sub.2]
      ([M.sub.1])  ([M.sub.3])   ([M.sub.5])  ([M.sub.7])

Part   Processing
Type    sequence

            V              vi           vii           viii

1

2

3        [M.sub.5]     [M.sub.9]     [M.sub.8]
       ([M.sub.6])   ([M.sub.3])  ([M.sub.10])

4        [M.sub.9]     [M.sub.8]    [M.sub.10]    [M.sub.7]
       ([M.sub.7])  ([M.sub.10])   ([M.sub.9])  ([M.sub.8])

5        [M.sub.7]
       ([M.sub.9])

6       [M.sub.10]
       ([M.sub.8])

7        [M.sub.7]     [M.sub.1]     [M.sub.2]    [M.sub.4]
       ([M.sub.5])   ([M.sub.7])   ([M.sub.8])  ([M.sub.9])

8        [M.sub.6]     [M.sub.6]     [M.sub.7]
       ([M.sub.3])   ([M.sub.9])  ([M.sub.10])

9        [M.sub.4]    [M.sub.10]
      ([M.sub.10])   ([M.sub.9])

10       [M.sub.8]    [M.sub.10]
      ([M.sub.10])   ([M.sub.8])

Part
Type

           ix

1

2

3

4

5

6

7        [M.sub.8]
      ([M.sub.10])

8

9

10


[gamma] = [bar.P]/M x [U.sub.s] (5)

It is assumed that each machine can fail randomly while performing an operation on a job, a busy time approach has been considered for generating the inter breakdown time. With this approach, a random uptime is generated for each machine from a busy time distribution. The machine is considered as up until its total accumulated busy time reaches the end of the generated uptime. Then it fails for a random time drawn from a down time distribution. In the simulation models, Mean time between failure (MTBF) and mean time to repair (MTTR) are assumed to follow Gamma distribution. Law and Kelton (24) 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 (which is 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) (6)

Machine breakdown level (BLs) is defined by the ratio of MTTR over the sum of MTTR and MTBF.

[BL.sub.s] = MTTR / (MTTR + MTBF) (7)

Each simulation model has been run for 2000 completed jobs after attaining a steady state and data has been collected after 20 replications. The following general assumptions have been made during the undertaken simulation studies:

1. Machines are not continuously available for processing and there are interruptions owing to breakdowns. If a machine breaks down no operation can be performed until the end of the time of repair.

2. When a machine breaks down, its repair starts immediately and the machine starts functioning again after the lapse of a certain period of time known as the time to repair.

3. Repaired machine works as efficiently as new machine.

4. A machine can fail only while performing an operation on a job.

The present simulation models consider the advantage of routing flexibility to cope up with machine breakdowns. The performance of selective rerouting policy has been evaluated with respect to the tardiness based performance measure. In the selected case study the selective rerouting heuristic has been compared with one benchmark rerouting policy (i.e. no rerouting) and three other rerouting policies namely, all rerouting, queue rerouting and arrival rerouting. In this analysis several experimental parameters has been considered such as breakdown level, mean down time, utilization level and rerouting policies. Two utilization levels are considered as low (80 %) and high (95 %). The utilization level has been calculated without considering the downtime of the machine. Four values of breakdown levels have been considered as 2.5, 5, 7.5 and 10 %. The five levels of mean duration of failure (mean down time) have been taken as p, 2.5p, 5p, 7.5p and 10p, where p is the average operation processing time. Hence, a smaller mean down time with same breakdown level represents a higher frequency of short breakdown times. The total work content method has been chosen for setting the three levels of due dates with an allowance factor of 3, 4.5 and 6 as loose, moderate and tight. The due date (Di) for each part type is calculated as:

[D.sub.i] = [A.sub.i] + (C x [k=[n.sub.i].summation over (k=1)][P.sub.ik]) (8)

where, [A.sub.i]--Arrival time of job i on the shop floor,

C--Due date allowance factor,

[k=[n.sub.i].summation over (k=1)][P.sub.ik] Sum of processing time for all the operations of job i.

4. RESULTS AND DISCUSSION

The experiment design for simulation studies considers two types of process plan environments viz., multiple process plans for selective rerouting, all rerouting, queue rerouting, arrival rerouting and single process plans for no rerouting under identical operating conditions. As breakdown level (four values), MTTR (five values), utilization level (two values), due date tightness (three values) and rerouting policies (five) are taken as variables. Hence, following the full factorial design approach 600 (= 4 x 5 x 2 x 3 x 5) simulations runs are performed for the case study. If the values of mean tardiness obtained by using the selective rerouting and all rerouting are [T.sub.2] and [T.sub.1] respectively under similar operating conditions then percentage reduction in the mean tardiness is defined as given below:

% Reduction in mean tardiness = [([T.sub.1] - [T.sub.2]) /[T.sub.1]] x 100 (9)

For example, from Table III, for selective rerouting, mean tardiness performance measure is 210 and for all rerouting the mean tardiness performance measure is 237. Thus, percentage reduction in mean tardiness is +11.39 = [(237 - 210) / 237] x 100. Here + sign indicates that mean tardiness reduces.

Table III: Mean tardiness yielded by taken rerouting approaches
at different breakdowns, MTTR and utilization levels for loose
due dates.

                          Utilization
                            level is
                              low

              Rerouting      Breakdown
              policies       level

                                2.5 %  5 %  7.5  10 %
                                              %

Mean  p     No-rerouting          355  379  397   485
down
time

            Queue                 270  315  372   458
            rerouting

            Arrival               283  378  515   533
            rerouting

            All                   237  262  276   306
            rerouting

            Selective             210  228  237   249
            rerouting

      2.5p  No-rerouting          551  588  616   752

            Queue                 307  358  423   520
            rerouting

            Arrival               321  429  584   605
            rerouting

            All                   281  310  327   362
            rerouting

            Selective             250  272  264   251
            rerouting

      5p    No-rerouting          510  556  750   964

            Queue                 319  433  532   676
            rerouting

            Arrival               399  537  566   669
            rerouting

            All                   299  316  387   530
            rerouting

            Selective             267  299  340   390
            rerouting

      7.5p  No-rerouting          655  714  963  1238

            Queue                 335  424  521   698
            rerouting

            Arrival               419  564  594   703
            rerouting

            All                   356  376  460   631
            rerouting

            Selective             323  362  412   472
            rerouting

      10p   No-rerouting          663  673  968  1247

            Queue                 345  437  537   719
            rerouting

            Arrival               496  667  702   831
            rerouting

            All                   451  476  582   799
            rerouting

            Selective             326  365  415   476
            rerouting

                          Utilization
                            level is
                              high

              Rerouting      Breakdown
              policies       level

                                2.5 %   5 %   7.5  10 %
                                                %

Mean  p     No-rerouting          702   798   873  1050
down
time

            Queue                 675   782   815   915
            rerouting

            Arrival               649   635   687   810
            rerouting

            All                   247   356   498   558
            rerouting

            Selective             225   240   327   447
            rerouting

      2.5p  No-rerouting          714   812  1023  1153

            Queue                 712   825   967  1076
            rerouting

            Arrival               621   608   680   776
            rerouting

            All                   282   406   568   636
            rerouting

            Selective             278   299   407   557
            rerouting

      5p    No-rerouting          761   960  1148  1274

            Queue                 686   837   960  1093
            rerouting

            Arrival               646   718   776   837
            rerouting

            All                   366   498   549   745
            rerouting

            Selective             251   445   482   672
            rerouting

      7.5p  No-rerouting          814  1027  1178  1263

            Queue                 697   851   976  1111
            rerouting

            Arrival               650   723   781   843
            rerouting

            All                   396   539   594   806
            rerouting

            Selective             259   459   497   693
            rerouting

      10p   No-rerouting          940  1186  1260  1359

            Queue                 744   908  1041  1185
            rerouting

            Arrival               682   759   820   885
            rerouting

            All                   407   554   611   828
            rerouting

            Selective             264   467   506   705
            rerouting


This section focuses on finding the effectiveness of selective rerouting over no rerouting, queue rerouting, arrival rerouting and all rerouting approaches for mean tardiness performance measure. Tables III, IV and V present the absolute values of mean tardiness obtained by using the four rerouting approaches as described in section 2.2 and the proposed selective rerouting algorithm at varying utilization levels, MTTR levels and breakdown levels for loose, moderate and tight due date respectively. These Tables show that at several considered operating parameters, selective rerouting approach provides less value of mean tardiness in comparison with other taken rerouting approaches.

Table IV: Mean tardiness yielded by taken rerouting approaches
at different breakdowns, MTTR and utilization levels for moderate
due dates.

                          Utilization
                            level is
                              low

            Rerouting      Breakdown
            policies         level

                                2.5 %  5 %   7.5  10 %
                                               %

Mean  p     No-rerouting          537  596   629   710
down
time

            Queue                 287  337   398   531
            rerouting

            Arrival               313  400   453   547
            rerouting

            All                   247  277   327   377
            rerouting

            Selective             219  241   258   278
            rerouting

      2.5p  No-rerouting          569  454   646   785

            Queue                 326  383   453   554
            rerouting

            Arrival               338  606   594   622
            rerouting

            All                   292  328   349   390
            rerouting

            Selective             255  280   284   275
            rerouting

      5p    No-rerouting          537  561   784  1002

            Queue                 338  460   563   714
            rerouting

            Arrival               422  576   595   695
            rerouting

            All                   316  330   414   561
            rerouting

            Selective             274  319   364   419
            rerouting

      7.5p  No-rerouting          647  746  1043  1132

            Queue                 333  453   554   703
            rerouting

            Arrival               429  585   604   706
            rerouting

            All                   390  394   511   693
            rerouting

            Selective             319  384   424   488
            rerouting

      10p   No-rerouting          669  697  1055  1158

            Queue                 342  465   569   722
            rerouting

            Arrival               507  691   713   834
            rerouting

            All                   496  501   650   881
            rerouting

            Selective             321  386   426   491
            rerouting

                          Utilization
                            level is
                              high

            Rerouting      Breakdown
            policies         level

                                2.5 %   5 %   7.5  10 %
                                                %

Mean  p     No-rerouting          723   828  1038  1166
down
time

            Queue                 694   811   949  1056
            rerouting

            Arrival               670   655   732   836
            rerouting

            All                   274   386   530   591
            rerouting

            Selective             235   267   355   479
            rerouting

      2.5p  No-rerouting          743   844  1058  1189

            Queue                 733   856  1002  1115
            rerouting

            Arrival               637   633   707   808
            rerouting

            All                   311   438   601   671
            rerouting

            Selective             291   330   439   592
            rerouting

      5p    No-rerouting          791   994  1184  1312

            Queue                 718   873   996  1132
            rerouting

            Arrival               667   741   804   869
            rerouting

            All                   396   531   584   781
            rerouting

            Selective             279   478   515   709
            rerouting

      7.5p  No-rerouting          844  1061  1264  1328

            Queue                 727   884  1009  1146
            rerouting

            Arrival               677   752   816   882
            rerouting

            All                   426   571   628   840
            rerouting

            Selective             287   491   529   728
            rerouting

      10p   No-rerouting          970  1220  1353  1427

            Queue                 776   943  1076  1222
            rerouting

            Arrival               704   782   849   917
            rerouting

            All                   438   587   646   864
            rerouting

            Selective             293   502   541   744
            rerouting

Table V: Mean tardiness yielded by taken rerouting approaches at
different breakdowns, MTTR and utilization levels for tight due
dates.

                          Utilization
                           level is
                             low

              Rerouting    Breakdown
              policies       level

                                2.5 %  5 %   7.5  10 %
                                               %

Mean  p     No-rerouting          577  615   666   805
down
time

            Queue                 310  366   431   525
            rerouting

            Arrival               318  428   555   566
            rerouting

            All                   264  300   320   359
            rerouting

            Selective             232  256   268   283
            rerouting

      2.5p  No-rerouting          589  628   680   822

            Queue                 350  413   486   592
            rerouting

            Arrival               360  485   629   641
            rerouting

            All                   310  352   375   421
            rerouting

            Selective             268  296   310   304
            rerouting

      7.5p  No-rerouting          605  600   821  1042

            Queue                 362  490   597   754
            rerouting

            Arrival               447  597   621   721
            rerouting

            All                   338  350   444   596
            rerouting

            Selective             287  344   391   450
            rerouting

            No-rerouting          635  782  1070  1158

            Queue                 388  485   615   778
            rerouting

            Arrival               454  607   631   733
            rerouting

            All                   411  418   540   724
            rerouting

            Selective             336  410   458   527
            rerouting

      10p   No-rerouting          687  731  1093  1182

            Queue                 398  498   631   799
            rerouting

            Arrival               530  708   736   855
            rerouting

            All                   521  530   685   918
            rerouting

            Selective             337  411   459   528
            rerouting

                           Utilization
                            level is
                              high

              Rerouting     Breakdown
              policies        level

                                2.5 %    5%   7.5  10 %
                                                %

Mean  p     No-rerouting          762   861  1074  1204
down
time

            Queue                 721   844   985  1096
            rerouting

            Arrival               641   679   713   821
            rerouting

            All                   305   420   567   630
            rerouting

            Selective             248   298   390   516
            rerouting

      2.5p  No-rerouting          777   878  1095  1228

            Queue                 760   890  1039  1156
            rerouting

            Arrival               659   661   739   843
            rerouting

            All                   343   472   637   708
            rerouting

            Selective             301   364   476   630
            rerouting

      7.5p  No-rerouting          823  1031  1223  1350

            Queue                 752   911  1034  1173
            rerouting

            Arrival               691   769   836   905
            rerouting

            All                   429   565   621   819
            rerouting

            Selective             312   513   552   747
            rerouting

            No-rerouting          876  1098  1302  1438

            Queue                 759   920  1044  1185
            rerouting

            Arrival               704   784   852   923
            rerouting

            All                   459   605   665   877
            rerouting

            Selective             320   526   566   766
            rerouting

      10p   No-rerouting         1002  1256  1389  1475

            Queue                 809   981  1113  1264
            rerouting

            Arrival               726   808   878   951
            rerouting

            All                   473   623   685   903
            rerouting

            Selective             328   539   580   785
            rerouting


Variation in percentage reduction in mean tardiness with selective rerouting in comparison with no rerouting, queue rerouting, all rerouting for varying breakdown levels (i.e. 2.5 %, 5 %, 7.5 % and 10 %) at different utilization (80 %, 90 %), MTTR (p, 10p) and due date tightness (loose due date, tight due date) level is shown from Figs. 2 to 9. Similar figures for other combinations (i.e. 80 %, 90 %, 2.5p, 5p, 7.5p and loose due date, tight due date) can be obtained by using the data given in Tables III and V.

Figs. 1 and 2 show the percentage reduction in the mean tardiness by using selective rerouting heuristic in comparison with no rerouting, queue rerouting, arrival rerouting and all rerouting, when mean time to repair is p, utilization is 80 % and due dates are loose and tight respectively. These figures indicate that as the breakdown level increases while keeping the other parameter unchanged, the percentage reduction in mean tardiness increase in tight as well as loose due dates. Figs. 3 and 4 show the percentage reduction in the mean tardiness by using selective rerouting heuristic in comparison with no rerouting, queue rerouting, arrival rerouting and all rerouting, when mean time to repair is p, utilization is 90 % and due dates are loose and tight respectively. These figures indicate that as the breakdown level increases while keeping the other parameters unchanged, the percentage reduction in mean tardiness decreases in tight as well as loose due dates. During analysis, it has been observed that at low utilization level, percentage reduction in mean tardiness by selective rerouting heuristic with respect to the taken rerouting approaches is less at low breakdown level in comparison to high breakdown level. Similarly at high utilization level, more percentage reduction has been observed at low break down level in comparison to high break down level.

Figs. 5 and 6 show the percentage reduction in the mean tardiness by using selective rerouting heuristic in comparison with no rerouting, queue rerouting, arrival rerouting and all rerouting, when mean time to repair is 10p, utilization is 80 % and due dates are loose and tight respectively. These figures indicate that as the breakdown level increases while keeping the other parameter unchanged, the percentage reduction in mean tardiness increase gradually in tight as well as loose due dates. Figs. 7 and 8 show the percentage reduction in the mean tardiness by using selective rerouting heuristic in comparison with no rerouting, queue rerouting, arrival rerouting and all rerouting, when mean time to repair is 10 p, utilization is 90 % and due dates are loose and tight respectively. These figures indicate that at low utilization level the decreasing trend of percentage reduction in mean tardiness by selective rerouting heuristic with respect to the taken rerouting policies is no-rerouting, arrival rerouting, all rerouting and queue rerouting. At high utilization level, the decreasing trend of percentage reduction in mean tardiness with respect to the taken rerouting policies is no rerouting, queue rerouting, arrival rerouting and all rerouting.

From all the cases (i.e. loose, moderate and tight due dates), it has been verified that selective rerouting outperform than no rerouting, arrival rerouting, queue rerouting and all rerouting from the mean tardiness view point. It has been concluded that for a given down time, different breakdown levels give varying percentage reduction in mean tardiness. Thus for a given down time, percentage reduction in mean tardiness is dependent on breakdown level. It is also concluded that for a given breakdown level, percentage reduction in mean tardiness varies as mean down time is increased from 2.5p to 10p in steps of 2.5p. Thus for a given breakdown level, percentage reduction in mean tardiness is dependent on mean down time. The above observations can also be seen from Figs. 2 to 9. Hence, the availability of alternate routing per part type during scheduling reduces mean tardiness performance measure and for a given utilization level, reduction in mean tardiness is dependent on the breakdown level, mean down time and due dates used. The most favourable condition for percentage improvement has been observed in Fig. 3 (breakdowns of short duration with higher frequency). In this case, selective rerouting reduces 69.92 % mean tardiness with respect to the no rerouting.

The proposed selective rerouting algorithm reduces mean tardiness of 67.49 %, 66.14 %, 64.93 %, and 18.95 % (at breakdown level = 2.5 %) and 58.92 %, 54.64 %, 42.71 % and 14.23 % (at breakdown level = 10 %) in comparison with no rerouting, all rerouting, queue rerouting and arrival rerouting respectively. It is seen that irrespective of the breakdown level in the investigated range, reduction of mean tardiness decreases in no rerouting, all rerouting, queue rerouting and arrival rerouting in the above order. Secondly, the reduction of mean tardiness is less at higher breakdown levels, which may be attributed to larger waiting time of part in the system. Thus, it can be concluded that the availability of alternate routes during scheduling reduce mean tardiness performance measure and the amount of reduction depends on the MTTR, frequency of breakdown, shop loading and due date tightness.

5. CONCLUSIONS

This paper presents the simulation study of selective rerouting scheduling approach with the provision of lateral entry of parts at the alternative machine in case of machine breakdown using routing flexibility. The details of the approach are given in section 2.1. The advantage of the selective rerouting is that rerouting is undertaken only when the benefits of rerouting are positive. Furthermore the selective rerouting approach has been compared with all rerouting, queue rerouting, arrival rerouting and one benchmarking no-rerouting approach under identical experimental conditions. It reduces the mean tardiness by a maximum of 71.92 %, 69.31 %, 65.33 % and 44.27 % in comparison with no rerouting, all rerouting, queue rerouting and arrival rerouting respectively. During analysis, more percentage reduction has been observed by selective rerouting approach in a highly loaded system in comparison to a lightly loaded system when due dates are loose and moderate. However, at tight due dates no specific trend has been observed. In a lightly loaded system the performance improvement by selective rerouting heuristic at high breakdown level is more in comparison to low breakdown level under loose, moderate and tight due dates. However, in a highly loaded system the performance improvement by selective rerouting heuristic at high breakdown level is less in comparison to low breakdown level under loose, moderate and tight due dates.

The efficacy of selective rerouting approach has been demonstrated by conducting simulation experiments and by considering several variables and their levels. In all the experiments selective rerouting approach outperforms than others. This is because of the waiting times of parts reduce during the rerouting of the parts from failed machine to alternative machine which implies the reduction in manufacturing lead time. Hence, it can be concluded that the reactive production capacity improves by using selective rerouting in the presence of machine breakdowns.

In the present research work, flexible job shop system with tardiness as the performance measure was considered to investigate the efficacy of selective rerouting algorithm. Further more complex system such as flexible manufacturing system (FMS) may be considered to investigate the efficacy of rerouting algorithm with the scheduling rules. The efficacy can be measure against flow time based performance measures. Further, in this research it is assumed that machines are not continuously available for processing and there are interruptions owing to breakdowns. When a machine breaks down its repair starts immediately it means that plenty of repairman's are available. Hence, in the future research limited availability of repairman may be considered.

DOI:10.2507/IJSIMM12(3)5.242

REFERENCES

(1.) Galzina, V.; Lujic, R.; Saric, T. (2012). Adaptive fuzzy particle swarm optimization for flow-shop scheduling problem, Technical Gazette, Vol. 19, No. 1, 151-157

(2.) Deming, L.; Xiuping, G. (2012). Swarm-based neighbourhood search algorithm for fuzzy flexible job shop scheduling, International Journal of Production Research, Vol. 50, No. 6, 1639-1649, doi:10.1080/00207543.2011.575412

(3.) Slak, A.; Tavcar, J.; Duhovnik, J. (2011). Application of genetic algorithm into multicriteria batch manufacturing scheduling, Strojniski vestnik--Journal of Mechanical Engineering, Vol. 57, No. 2, 110-124, doi:10.5545/sv-jme.2010.122

(4.) Kaban, A. K.; Othman, Z.; Rohmah, D. S. (2012). Comparison of dispatching rules in job-shop scheduling problem using simulation: a case study, International Journal of Simulation Modelling, Vol. 11, No. 3, 129-140, doi:10.2507/IJSIMM11(3)2.201

(5.) Aytug, H.; Lawley, M. A.; McKay, K.; Mohan, S.; Uzsoy, R. (2005). Executing production schedules in the face of uncertainties: A review and some future directions, European Journal of Operational Research, Vol. 161, No. 1, 86-110, doi:10.1016/j.ejor.2003.08.027

(6.) Chiu, Y.; Shih, C.-J. (2012). Rescheduling strategies for integrating rush orders with preventive maintenance in a two-machine flow shop, International Journal of Production Research, Vol. 50, No. 20, 5783-5794, doi:10.1080/00207543.2011.627887

(7.) Dong, Y-H.; Jang, J. (2012). Production rescheduling for machine breakdown at a job shop, International Journal of Production Research, Vol. 50, No. 10, 2681-2691, doi:10.1080/ 00207543.2011.579637

(8.) Ham, M.; Lee, Y. H.; Kim, S. H. (2011). Real-time scheduling of multi-stage flexible job shop floor, International Journal of Production Research, Vol. 49, No. 12, 3715-3730, doi:10.1080/00207543.2010.492797

(9.) Hozak, K.; Hill, J. A. (2009). Issues and opportunities regarding replanning and rescheduling frequencies, International Journal of Production Research, Vol. 47, No. 18, 4955-4970, doi:10.1080/00207540802047106

(10.) Abumaizar, R. J.; Svestka, J. A. (1997). Rescheduling job shops under random disruptions, International Journal of Production Research, Vol. 35, No. 7, 2065-2082, doi:10.1080/ 002075497195074

(11.) Kutanoglu, E.; Sabuncuoglu, I. (2001). Routing-based reactive scheduling policies for machine failures in dynamic job shops, International Journal of Production Research, Vol. 39, No. 14, 3141-3158, doi:10.1080/00207540110057909

(12.) Kamrul Hasan, S. M., Sarker, R.; Essam, D. (2011). Genetic algorithm for job-shop scheduling with machine unavailability and breakdowns, International Journal of Production Research, Vol. 49, No. 16, 4999-5015, doi:10.1080/00207543.2010.495088

(13.) Sabuncuoglu, I.; Kizilisik, O. B. (2003). Reactive scheduling in a dynamic and stochastic FMS environment, International Journal of Production Research, Vol. 41, No. 17, 4211-4231, doi:10.1080/0020754031000149202

(14.) Cowling, P.; Johansson, M. (2002). Using real time information for effective dynamic scheduling, European Journal of Operational Research, Vol. 139, No. 2, 230-244, doi:10.1016/S0377-2217(01)00355-1

(15.) Zandieh, M.; Adibi, M. A. (2010). Dynamic job shop scheduling using variable neighbourhood search, International Journal of Production Research, Vol. 48, No. 8, 2449-2458, doi:10.1080/ 00207540802662896

(16.) Lee, S.; Moon, I.; Bae, H.; Kim, J. (2012). Flexible job-shop scheduling problems with 'AND'/'OR' precedence constraints, International Journal of Production Research, Vol. 50, No. 7, 1979-2001, doi:10.1080/00207543.2011.561375

(17.) Chen, J.; Chen, F. F. (2003). Adaptive scheduling in random flexible manufacturing systems subject to machine breakdowns, International Journal of Production Research, Vol. 41, No. 9, 1927-1951, doi:10.1080/0020754031000119016

(18.) Kia, H. R.; Davoudpour, H.; Zandieh, M. (2010). Scheduling a dynamic flexible flow line with sequence-dependent setup times: a simulation analysis, International Journal of Production Research, Vol. 48, No. 14, 4019-4042, doi:10.1080/00207540902922869

(19.) Kim, M. H.; Kim, Y.-D. (1994). Simulation-based real-time scheduling in a flexible manufacturing system, Journal of Manufacturing Systems, Vol. 13, No. 2, 85-93, doi:10.1016/0278-6125(94)90024-8

(20.) Jeong, K.-C.; Kim, Y.-D. (1998). A real time scheduling mechanism for a flexible manufacturing system: using simulation and dispatching rules, International Journal of Production Research, Vol. 36, No. 9, 2609-2626, doi:10.1080/002075498192733

(21.) Metan, G.; Sabuncuoglu, I.; Pierreval, H. (2010). Real time selection of scheduling rules and knowledge extraction via dynamically controlled data mining, International Journal of Production Research, Vol. 48, No. 23, 6909-6938, doi:10.1080/00207540903307581

(22.) Singh, A. (2010). Aspects of selective rerouting in multicriteria scheduling of flexible manufacturing, International Journal of Simulation Modelling, Vol. 9, No. 3, 131-142, doi:10.2507/IJSIMM09(3)2.158

(23.) Viswanadhamn, N.; Narahari, Y. (2010). Performance Modeling of Automated Manufacturing Systems, Prentice-Hall, New Delhi

(24.) Law, A. M.; Kelton, W. D. (2000). Simulation Modeling and Analysis, 3rd Edition, McGraw-Hill, New York

Singh, A.

Indian Institute of Management, Rohtak, Haryana, India

E-Mail: amol.singh@iimrohtak.ac.in

Table I: Steps of existing rerouting policies.

Rerouting                    Steps
policies

Arrival    * The jobs in the queue of the failed
Rerouting  machine wait there.
           * The newly arriving jobs are rerouted to
           the alternative machine until the machine
           is repaired.

Queue      * All the newly arriving jobs on the
Rerouting  failed machine wait in the queue of the
           failed machine.
           * The jobs already in the queue at the
           time of machine breakdown are rerouted to
           the alternate machine.

All        * All rerouting is a combination of queue
rerouting  rerouting and arrival rerouting.
           * All the jobs in the queue of the failed
           machine and all the new arrivals (during
           the repair time) are rerouted to the
           alternative machine in case of machine
           failure.

No         * All the new arrival and the jobs in the
Rerouting  queue of the failed machine wait in the
           queue of the failed machine until the
           machine has been repaired.
COPYRIGHT 2013 DAAAM International Vienna
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Singh, A.
Publication:International Journal of Simulation Modelling
Article Type:Report
Geographic Code:9INDI
Date:Sep 1, 2013
Words:7352
Previous Article:Supply chain analysis using simulation, Gaussian process modelling and optimisation.
Next Article:Calendar of events.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |