Minimization of mean tardiness in a flexible job shop.
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.
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.
(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
Indian Institute of Management, Rohtak, Haryana, India
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.
|Printer friendly Cite/link Email Feedback|
|Publication:||International Journal of Simulation Modelling|
|Date:||Sep 1, 2013|
|Previous Article:||Supply chain analysis using simulation, Gaussian process modelling and optimisation.|
|Next Article:||Calendar of events.|