Abstract
In this paper, we address a scheduling problem for minimizing total weighted flowtime, observed in automobile gear manufacturing. Specifically, the bottleneck operation of the pre-heat treatment stage of gear manufacturing process has been dealt with in scheduling. Many real-life scenarios like unequal release times, sequence dependent setup times, and machine eligibility restrictions have been considered. A mathematical model taking into account dynamic starting conditions has been proposed. The problem is derived to be NP-hard. To approach the problem, a few heuristic algorithms have been proposed. Based on planned computational experiments, the performance of the proposed heuristic algorithms is evaluated: (a) in comparison with optimal solution for small-size problem instances and (b) in comparison with the estimated optimal solution for large-size problem instances. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently yielding near-statistically estimated optimal solutions in a reasonable computational time.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Allahverdi A, Gupta JND, Aldowaisan T (1999) A review of scheduling research involving setup considerations. Omega 27(2):219–239
Allahverdi A, Ng CT, Cheng TCE, Kovalyov MY (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187(3):985–1032
Anghinolfi D, Paolucci M (2007) Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach. Comput Oper Res 34(11):3471–3490
Armentano VA, Filho MFF (2007) Minimizing total tardiness in parallel machine scheduling with setup times: an adaptive memory-based GRASP approach. Eur J Oper Res 183(1):100–114
Balakrishnan N, Kanet JJ, Sridhiran SV (1999) Early/tardy scheduling with sequence dependent setups on uniform parallel machines. Comput Oper Res 26(2):127–141
Bilge Ü, Kiraç F, Kurtulan M, Pekgün P (2004) A tabu search algorithm for parallel machine total tardiness problem. Comput Oper Res 31(3):397–414
Bouzakis KD, Lili E, Michailidis N, Friderikos O (2008) Manufacturing of cylindrical gears by generating cutting process: a critical synthesis of analysis methods. CIRP Annals-Manuf Tech 57(2):676–696
Cheng TCE, Sin CCE (1990) A state-of-the-art review of parallel-machine scheduling research. Eur J Oper Res 47(3):271–292
Gokhale R, Mathirajan M (2010) A supplement to scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flowtime in automobile gear manufacturing [online]. Department of Management Studies, Indian Institute of Science. Available from: http://www.mgmt.iisc.ernet.in/~msdmathi. Accessed 13 Jan 2011
Gokhale R, Mathirajan M (2011) Heuristic algorithms for scheduling of a batch processor in automobile gear manufacturing. Int J Prod Res 49(10):2705–2728
Golden BL, Alt FB (1979) Interval estimation of a global optimum for large combinatorial problems. Nav Res Logist Q 26(1):69–77
Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5(4):287–326
Heady RB, Zhu Z (1998) Minimizing the sum of job earliness and tardiness in a multimachine system. Int J Prod Res 36(6):1619–1632
Huang RH, Yang CL, Huang HT (2010) Parallel machine scheduling with common due windows. J Oper Res Soc 61(4):640–646
Hutchison J, Keong Leong G, Ward PT (1993) Improving delivery performance in gear manufacturing at Jeffrey Division of Dresser Industries. Interfaces 23(2):69–79
Kim CO, Shin HJ (2003) Scheduling jobs on parallel machines: a restricted tabu search approach. Int J Adv Manuf Technol 22(3–4):278–287
Kim S-I, Choi H-S, Lee D-H (2007) Scheduling algorithms for parallel machines with sequence-dependent set-up and distinct ready times: minimizing total tardiness. Proceedings of the Institution of Mechanical Engineers, Part B. J Eng Manuf 221(6):1087–1096
Kuo W-H, Hsu C-J, Yang D-L (2009) A note on unrelated parallel machine scheduling with time-dependent processing times. J Oper Res Soc 60(3):431–434
Kurz ME, Askin RG (2001) Heuristic scheduling of parallel machines with sequence-dependent set-up times. Int J Prod Res 39(16):3747–3769
Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (1993) Sequencing and scheduling: algorithms and complexity. In: Graves SC, Rinnooy Kan AHG, Zipkin P (eds) Handbooks in operations research and management science 4, logistics of production and inventory. Elsevier, Amsterdam, pp 445–524
Lee G-C, Kim Y-D, Choi S-W (2004) Bottleneck-focused scheduling for a hybrid flowshop. Int J Prod Res 42(1):165–181
Logendran R, McDonell B, Smucker B (2007) Scheduling unrelated parallel machines with sequence-dependent setups. Comput Oper Res 34(11):3420–3438
Mathirajan M, Sivakumar AI (2006) Minimizing total weighted tardiness on heterogeneous batch processing machines with incompatible job families. Int J Adv Manuf Technol 28(9–10):1038–1047
Nessah R, Chu C, Yalaoui F (2007) An exact method for Pm/sds, r i /∑n i=1 C i problem. Comput Oper Res 34(9):2840–2848
Ovacik IM, Uzsoy R (1995) Rolling horizon procedures for dynamic parallel machine scheduling with sequence-dependent setup times. Int J Prod Res 33(11):3173–3192
Pelagagge PM (1997) Advanced manufacturing system for automotive components production. Ind Manag Data Syst 97(8):327–334
Pfund M, Fowler JW, Gadkari A, Chen Y (2008) Scheduling jobs on parallel machines with setup times and ready times. Comput Ind Eng 54(4):764–782
Pohit G (2006) Application of virtual manufacturing in generation of gears. Int J Adv Manuf Technol 31(1–2):85–91
Rabadi G, Moraga RJ, Al-Salem A (2006) Heuristics for the unrelated parallel machine scheduling problem with setup times. J Intell Manuf 17(1):85–97
Rardin RL, Uzsoy R (2001) Experimental evaluation of heuristic optimization algorithms: a tutorial. J Heuristics 7(3):261–304
Sivrikaya-Şerifoglu F, Ulusoy G (1999) Parallel machine scheduling with earliness and tardiness penalties. Comput Oper Res 26(8):773–787
Sen T, Sulek JM, Dileepan P (2003) Static scheduling research to minimize weighted and unweighted tardiness: a state-of-the-art survey. Int J Prod Econ 83(1):1–12
Shim S-O, Kim Y-D (2007) Minimizing total tardiness in an unrelated parallel-machine scheduling problem. J Oper Res Soc 58(3):346–354
Shin HJ, Leon VJ (2004) Scheduling with product family set-up times: an application in TFT LCD manufacturing. Int J Prod Res 42(20):4235–4248
Acknowledgment
The authors gratefully acknowledge the valuable comments and remarks of the anonymous referees that improved the quality of the paper.
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Below is the link to the electronic supplementary material.
ESM 1
DOC 307 kb
Appendix
Appendix
A procedure for EOS
The idea of statistical estimation techniques for optimal values based on Weibull distribution is explained here as per Rardin and Uzsoy [30].
Begin by letting Z(1), Z(2), . . ., Z(N) be the n independent group minima, and sort them so that: Z(1) ≤ Z(2) ≤. . . Z(n).
Then, the location parameter or optimal value a can be estimated as follows:
This value of a is the EOS that is used for evaluation.
A reliable estimate of the true optimum would be valuable in itself, but Golden and Alt [11] introduce more certainty by computing a lower confidence limit Z l which should be less than or equal to the optimal value Z * with high probability. Specifically, they estimate Weibull scale parameter b from a as
and then compute
In theory, this interval should cover the optimal value Z * with probability approximately (1−e −n).
Rights and permissions
About this article
Cite this article
Gokhale, R., Mathirajan, M. Scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flowtime in automobile gear manufacturing. Int J Adv Manuf Technol 60, 1099–1110 (2012). https://doi.org/10.1007/s00170-011-3653-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-011-3653-3