×

Job scheduling and management of wearing tools with stochastic tool lifetimes. (English) Zbl 1147.90344

Summary: The problem of scheduling jobs using wearing tools is studied. Tool wearing is assumed to be stochastic and the jobs are processed in one machining centre provided with a limited capacity tool magazine. The aim is to minimize the expected average completion time of the jobs by choosing their processing order and tool management decisions wisely. All jobs are available at the beginning of the planning period. This kind of situation is met in production planning of CNC-machines. Previous studies concerning this problem have either assumed deterministic wearing for the tools or omitted the wearing completely. In our formulation of the problem, tool wearing is stochastic and the problem becomes very hard to solve analytically. A heuristic based on genetic algorithms is therefore given for the joint problem of job scheduling and tool management. The algorithm searches the most beneficial job sequence when the tool management decisions are made by a removal rule taking into account the future planned usage of the tools. The cost of each job sequence is evaluated by simulating the job processing. Empirical tests with heuristics indicate that by taking the stochastic information into account, one can reduce the average job processing time considerably.

MSC:

90B36 Stochastic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adiri IJ, Bruno E, Frostig AHG, Rinnooy K (1989) Single machine flow-time scheduling with a single breakdown. Acta Inform 26:679–696 · Zbl 0657.68033 · doi:10.1007/BF00288977
[2] Ahmad M, Sheikh AK (1984) Berstein reliability model: derivation and estimation of parameters. Rel Eng 8:131–148 · doi:10.1016/0143-8174(84)90020-9
[3] Akturk MS, Ghosh JB, Gunes ED (2002) Scheduling with tool changes to minimize total completion time: a study of heuristics and their performance. Naval Res Logist 50:15–30 · Zbl 1044.90031 · doi:10.1002/nav.10045
[4] Billatos SB, Kendall LAA (1991) General optimization model for multi-tool manufacturing systems. Trans ASME 113(10):10–16 · doi:10.1115/1.2912743
[5] Birge JR, Louveaux F (1997) Introduction to stochastic programming. Springer Verlag · Zbl 0892.90142
[6] Crama Y, Kolen AWJ, Oerlemans AG, Spieksma FCR (1994) Minimizing the number of tool switches on a flexible machine. Int J Flex Manuf Syst 6:33–53 · doi:10.1007/BF01324874
[7] Gibbs D, Crandell TM (1991) An introduction to CNC machining and programming. Industrial Press
[8] Gray E, Seidmann A, Stecke KE (1993) A synthesis of decision models for tool management in automated manufacturing. Manage Sci 39:549–567 · doi:10.1287/mnsc.39.5.549
[9] Hirvikorpi M, Knuutila T, Nevalainen O (2006) Job ordering and management of wearing tools in flexible manufacturing. Eng Optimiz 38(2):227–244 · doi:10.1080/03052150500420363
[10] Iakovou E, Ip CM, Koulamas C (1996) Optimal solutions for the machining economics problem with stochastically distributed tool lives. Eur J Oper Res 92(1):63–68 · Zbl 0913.90118 · doi:10.1016/0377-2217(95)00131-X
[11] Iawata K, Murostu Y, Iwatsubo T, Fujii S (1972) A probabilistic approach to the determination of the optimum cutting conditions. J Eng Ind Ser B 94(4):1099–1107 · doi:10.1115/1.3428310
[12] Jianqiang M, Keow LM (1997) Economical optimization of tool replacement intervals. Int Manuf Syst 8(1): 59–62 · doi:10.1108/09576069710158817
[13] Knuutila T, Puranen M, Johnsson M, Nevalainen O (2001) Three perspectives for solving the job grouping problem. Int J Prod Res 39(18):4261–4280 · Zbl 1175.90143 · doi:10.1080/00207540110072984
[14] Lee CY, Liman SD (1992) Single machine flow-time scheduling with scheduled maintenance. Acta Inform 29:375–382 · Zbl 0780.68063 · doi:10.1007/BF01178778
[15] Lee CY (1996) Machine scheduling with an availability constraint. J Glob Optim 9:395–416 · Zbl 0870.90071 · doi:10.1007/BF00121681
[16] Lee CY (1997) Minimizing the makespan in two-machine flowshop scheduling problem with an availability constraint. Oper Res Lett 20:129–139 · Zbl 0882.90069 · doi:10.1016/S0167-6377(96)00041-7
[17] Murthy DNP, Xie M, Jiang R (2004) Weibull models. Wiley · Zbl 1047.62095
[18] Qi X, Chen T, Tu F (1999) Scheduling the maintenance on a single machine. J Oper Res Soc 50:1071–1078 · Zbl 1054.90550
[19] Reeves CR (1995) Modern heuristic techniques for combinatorial problems. McGraw-Hill International
[20] Storer RH, Wu DS, Vaccari R (1983) New search spaces for sequencing problems with application to job shop scheduling. Manage Sci 29:273–288 · Zbl 0517.90035 · doi:10.1287/mnsc.29.3.273
[21] Tang CS, Denardo EV (1988) Models arising from a flexible manufacturing machine. Oper Res 36(5):767–784 · Zbl 0665.90044 · doi:10.1287/opre.36.5.767
[22] Turkcan A, Akturk MS, Storer RH (2003) Non-identical parallel CNC machine scheduling. Int J Prod Res 41(10):2143–2168 · Zbl 1052.90566 · doi:10.1080/0020754031000087184
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.