ارائه حدود پایین جدید روی مقدار بهینه زمان انجام کل کارها در یک سیستم تک ماشینه‌ی پردازش‌گر انباشته

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دکتری صنایع؛ دانشگاه صنعتی امیرکبیر

2 نویسنده مسئول و دانشیار دانشکده صنایع؛ دانشگاه صنعتی امیرکبیر

چکیده

در این مقاله زمان‌بندی یک ماشین پردازش‌گر انباشته با هدف حداقل‌سازی زمان انجام کل کارها (Cmax) بررسی شده است. منظور از یک ماشین پردازشگر انباشته، ماشینی است که قابلیت انجام عملیات هم‌زمان روی گروهی از کارها را در قالب یک دسته یا انباشته دارد. البته با اعمال این محدودیت که مجموع اندازه کارهایی که در یک انباشته با‌‌هم می‌آیند از ظرفیت ماشین (B)بیشتر نباشد. برای هر یک از کارها دو عامل اندازه و زمان پردازش مفروض است. زمان انجام عملیات ماشین بر روی یک انباشته برابر با زمان عملیات مورد نیاز کاری است که در میان کارهای متعلق به آن انباشته بزرگ‌ترین زمان پردازش را دارد. برای این مساله، دو روش جدید تولید حد پایین روی مقدار بهینه تابع هدف با نام‌های LB2 و LB3 ارائه شده و ثابت می‌شود که نسبت به تنها حد پایین موجود در ادبیات موضوع مساله (LB1) عملکرد بهتری دارند. هم‌چنین ثابت می‌شود که عملکرد LB3 حداقل به خوبی عملکرد  LB2 است.

کلیدواژه‌ها


عنوان مقاله [English]

New Lower Bounds for the Optimal Makespan on a Single Batch Processing Machine

نویسندگان [English]

  • Ali Hosein Zade Kashan 1
  • Behroz Karimi 2
چکیده [English]

This paper considers minimizing makespan (Cmax) on a single batch-processing machine. A batch-processing machine can process a group of jobs simultaneously, as long as the total size of jobs in the batch does not exceed the machine capacity (B). For each job, we assume a specific job size and job processing time. The processing time of a batch is just the longest processing time of all jobs in the batch. We introduce two new procedures for obtaining lower bounds of the optimal makespan, entitled LB2 and LB3, respectively. We prove that both of the new bounds are tighter than the only existing bound called LB1. We also prove that LB3 is at least as tight as LB2.

کلیدواژه‌ها [English]

  • Scheduling
  • batch-processing machine
  • lower bounds
  • makespan
[1] حسین زاده کاشان، علی؛ “ارائه حدود بالا و پایین برای مسائل زمانبندی تک ماشین و جریان کارگاهی در سیستمهای تولید انباشتهای با فرض وجود نیازمندی ظرفیتی متفاوت برای کارها”. رساله دکتری مهندسی صنایع، دانشگاه صنعتی امیرکبیر، 1388
[2] Azizoglu, M.; Webster, S.; “Scheduling a batch processing machine with incompatible job families”. Computers & Industrial Engineering, vol. 39, p.p. 325-335, 2000.
[3] Boudhar, M.; Finke, G.; “Scheduling on a batch machine with job compatibilities”, Belgian Journal of Operations Research, Statistics and Computer Science, vol. 40, p.p. 69–80, 2000.
[4] Chang, P.Y.; Damodaran, P.; Melouk, S.; “Minimizing makespan on parallel batch processing machines”, International Journal of Production Research, vol. 42, p.p. 4211-4220, 2004.
[5] Damodaran, P., Chang, P.Y.; “Heuristics to minimize makespan of parallel batch processing machines”, International Journal of Advance Manufacturing Technology, vol. 37, p.p. 1005-1013, 2008.
[6] Damodaran, P.; Manjeshwar, P.K.; Srihari, K.; “Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms”, International journal of production economics, vol. 103, p.p. 882-891, 2006.
[7] Damodaran, P.; Srihari, K.; “Mixed integer formulation to minimize makespan in flow shop with batch processing machines”. Mathematical and Computer Modeling, vol. 40, p.p. 1465-1472, 2004.
[8] Dobson, G.; Nambimadom, R.S.; “The batch loading and scheduling problem”, Research Report, Simon School of Business Administration. University of Rochester, Rochester, NY, 1992.
[9] Dupont, L.; Dhaenens-Flipo, C.; “Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure”, Computers & Operations Research, vol. 29, p.p. 807-819,2002.
[10] Dupont, L.; Jolai Ghazvini, F.; “Minimizing Makespan on a Single Batch Processing Machine with Non identical Job Sizes”, European journal of Automation Systems, vol. 32, p.p. 431-440, 1998.
[11] Husseinzadeh Kashan, A.; Karimi, B.; “Scheduling a single batch-processing machine with arbitrary job sizes and incompatible job families: an ant colony framework”, Journal of the Operational Research Society, vol. 59, p.p. 1269-1280, 2008.
[12] Husseinzadeh Kashan, A.; Karimi, B.; “An improved mixed integer linear formulation and several lower bounds for minimizing makespan on a flowshop with batch processing machines”, International Journal of Advanced manufacturing Technology, vol. 40, p.p. 582-594, 2009.
[13] Husseinzadeh Kashan, A.; Karimi, B.; Fatemi Ghomi, S.M.T.; “A note on: Minimizing makespan on a single batch processing machine with non-identical job sizes”, Theoretical Computer Science, vol. 410, p.p. 2754-2758, 2009.
[14] Husseinzadeh Kashan, A.; Karimi, B.; Jenabi, M.; “A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes”, Computers & Operations Research, vol. 35, p.p. 1084-1098, 2008.
[15] Husseinzadeh Kashan, A.; Karimi, B.; Jolai, F.; “Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes”, International Journal of Production Research, vol. 44, p.p. 2337-2360, 2006.
[16] Husseinzadeh Kashan, A.; Karimi, B.; Jolai, F.; “An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes”. Engineering Applications of Artificial Intelligence, vol. 23, p.p. 911-922, 2010.
[17] Koh, S.G.; Koo, P.H.; Kim, D.C.; Hur, W.S.; “Scheduling a single-batch-processing machine with arbitrary job sizes and incompatible job families”, International Journal of Production Economics, vol. 98, p.p. 81–96, 2005.
[18] Lee, C.Y.; Uzsoy, R.; Martin-Vega, L.A.; “Efficient Algorithms for Scheduling Semiconductor Burn-in Operations”, Operations Research, vol. 40, p.p. 764-775, 1992.
[19] Liao L.M.; Huang, C.J.; “Tabu search heuristic for two-machine flowshop with batch processing machines”, Computers & Industrial Engineering, In Press, 2010.
[20] Mathirajan, M.; Sivakumar, A.I.; “A Literature Review, Classification and Simple Meta-analysis on Scheduling of Batch Processors in Semiconductor”,International Journal of Advanced Manufacturing Technology, vol. 29, p.p. 990-1001, 2006.
[21] Melouk, S.; Damodaran, P.; Cheng, P.Y.; “Minimizing make span for single machine batch processing with non-identical job sizes using simulated annealing”, International Journal of Production Economics, vol. 87,p.p. 141-147, 2004.
[22] Rafiee Parsa, N.; Karimi, B.; Husseinzadeh Kashan, A.; “A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes”, Computers & Operations Research, vol. 37, p.p. 1720-1730, 2010.
[23] Uzsoy, R.; “A Single Batch Processing Machine with Non-identical Job Sizes”, International Journal of
Production Research, vol. 32, p.p. 1615-1635, 1994.
[24] Wang, H.M.; Chou, F.D.; “Solving the parallel batch- processing machines with different release times, job sizes, and capacity limits by metaheuristics”, Expert Systems with Applications, vol 37. p.p. 1510-1521,2010.
[25] Zhang, G.; Cai, X.; Lee, C.Y.; Wong, C.K.; “Minimizing makespan on a single batch processing machine with nonidentical job sizes”, Naval Research Logistics, vol. 48, p.p. 226-240, 2001.
[26] Zhang, W.G.; Chen, H.P.; Lu, D.; Shao, H.; “A Novel Differential Evolution Algorithm for a Single Batchprocessing
Machine with Non-identical Job Sizes”,Proc. Fourth International Conference on Natural Computation, p.p. 447-451, 2008.
[27] Zhang, Y.L.; Chen, H.P.; Shao, H.; Xu, R.; “Minimizing Makespan for Single Batch Processing Machine with Non-identical Job Sizes Using a Novel Algorithm: Free Search”, Proc. International Conference on Information Technology and Computer
Science p.p. 180-183, 2009.