로트 스트리밍 흐름공정 일정계획의 스트레치 최소화
On Lot-Streaming Flow Shops with Stretch Criterion
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Lot-streaming is the process of splitting a job (lot) into sublots to allow the overlapping of operations between successivemachines in a multi-stage production system. A new genetic algorithm (NGA) is proposed for an n-job, m-machine, lot-streamingflow shop scheduling problem with equal-size sublots in which the objective is to minimize the total stretch. The stretch ofa job is the ratio of the amount of time the job spent before its completion to its processing time. NGA replaces the selectionand mating operators of genetic algorithms (GAs) by marriage and pregnancy operators and incorporates the idea of inter-chromosomal dominance and individuals’ similarities. Extensive computational experiments for medium to large-scale lot-streamingflow-shop scheduling problems have been conducted to compare the performance of NGA with that of GA.
Abstract
Lot-streaming is the process of splitting a job (lot) into sublots to allow the overlapping of operations between successivemachines in a multi-stage production system. A new genetic algorithm (NGA) is proposed for an n-job, m-machine, lot-streamingflow shop scheduling problem with equal-size sublots in which the objective is to minimize the total stretch. The stretch ofa job is the ratio of the amount of time the job spent before its completion to its processing time. NGA replaces the selectionand mating operators of genetic algorithms (GAs) by marriage and pregnancy operators and incorporates the idea of inter-chromosomal dominance and individuals’ similarities. Extensive computational experiments for medium to large-scale lot-streamingflow-shop scheduling problems have been conducted to compare the performance of NGA with that of GA.
참고문헌 (18)
- Bender, M.A., "Approximation algorithms for average stretch scheduling", Journal of Scheduling, 7, pp.195~222 (2004)
- Buscher, U., "An integrated Tabu search algorithm for the lot streaming problem in job-shops", European Journal of Operational Research, 199(1), pp.385~399 (2009)
- Chan, W. -T., "New resource augmentation analysis of the total stretch of SRPT and SJF in multiprocessor scheduling", Theoretical Computer Science, 359, pp.430~439 (2006)
- Chang, J.H., "A comprehensive review of lot streaming", International Journal of Production Research, 43(8), pp.1515~1536 (2005)
- Cheng, M., "A review of lot streaming", International Journal of Production Research, 51(23-24), pp.7023~7046 (2013)
- Defersha, F.M., "Jobshop lot streaming with routing flexibility, sequence-dependent setups, machine release dates and lag time", International Journal of Production Research, 8(15), pp.2331~2352 (2012)
- Dreo, J., "Metaheuristics for Hard Optimization : Methods and Case Studies" (2005), Springer
- Goldberg, D.E., "Genetic algorithms in search, optimization, and machine learning" (1989), Addison-Wesley
- Hall, N. G., "Scheduling and lot streaming in two-machine open shops with no-wait in process", Naval Research Logistics, 52, pp.261~275 (2005)
- Kalir, A.A., "Evaluation of the potential benefits of lot streaming in flow-shop systems", International Journal of Production Economics, 66(2), pp.131~142 (2000)
- Liepins, G.E., "Genetic algorithms : Foundation and applications", Annals of Operations Research, 21(1-4), pp.31~58 (1989)
- Low, C., "Benefits of lot splitting in job-shop scheduling", International Journal of Advanced Manufacturing Technology, 24, pp.773~780 (2004)
- Marimuthu, S., "Evolutionary algorithms for scheduling m-machine flow shop with lot streaming", Robotics and Computer-Integrated Manufacturing, 24(1), pp.125~139 (2008)
- Muthukrishnan, S., "Online scheduling to minimize average stretch", Siam Journal on Computing, 34(2), pp.433~452 (2005)
- Pan, Q. -K., "discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem", Information Sciences, 183, pp.2455~2468 (2011)
- Pinedo, M.L., "Scheduling : Theory, Algorithms, and Systems" (2012), Springer
- Tseng, C.-T., "A discrete particle swarm optimization for lot-streaming flow-shop scheduling problem", European Journal of Operational Research, 191(1), pp.360~373 (2008)
- Zhang, W., "Multi-job lot streaming to minimize the mean completion time in m-1 hybrid flowshops", International Journal of Production Economics, 96, pp.189~200 (2005)