مدل‌سازي و زمان‌بندي مسيله‌ي جريان كارگاهي تركيبي با ماشين هاي پردازش دسته‌يي

Modeling and Scheduling Hybrid Flowshop with Batch Processing Machines

در اين پژوهش مسيله‌ي زمان‌بندي جريان كارگاهي تركيبي با ماشين هاي پردازش دسته‌يي، با هدف كمينه كردن زمان تكميل كل كارها مورد مطالعه قرار گرفته است. ماشين هاي پردازش دسته‌يي از قابليت پردازش همزمان چند كار در يك دسته برخوردارند. ظرفيت ماشين ها و اندازه‌ي كارها در هر مرحله مشخص است. دسته ها پس از تشكيل تا آخرين مرحله ثابت مي‌مانند. مجموع اندازه كارهاي هر دسته نبايد از كوچك‌ترين ظرفيت ماشين ها بيشتر شود. زمان پردازش دسته ها برابر طولاني‌ترين زمان پردازش كارها در دسته است. ابتدا مدل برنامه ريزي خطي عدد صحيح مختلط براي مسيله‌ي مورد نظر پيشنهاد داده مي‌شود. به‌دليل پيچيدگي بالاي مسيله‌ي مورد بررسي، الگوريتم فراابتكاري رقابت استعماري براي حل مسيله‌ توسعه داده شده است. در نهايت عملكرد الگوريتم پيشنهادي در برابر الگوريتم هاي شبيه‌سازي تبريد و بهينه‌سازي اجتماع ذرات موجود در ادبيات، مورد بررسي قرار گرفته است. نتايج نشان مي دهد كه الگوريتم رقابت استعماري نسبت به دو الگوريتم ديگر براي مسيله‌ي مورد نظر عملكرد بهتري دارد.

Although batch scheduling has attracted many researchers, they mainly focus on flow shop scheduling problems. Yet, in real world industries, we rarely have a production system with only one processor at each working station. Machines are usually duplicated in parallel at each station to balance the production capacity of shop floor and to decrease the impact of bottleneck stations. This paper deals with a hybrid flow shop scheduling problem with batch processing machines (BPMs). The objective is to minimize makespan (i.e., maximum completion time of jobs). Batch processing machines can simultaneously process several jobs in a batch. The processing time of a batch is the longest processing time among all the jobs in that batch. Once a batch is formed by a set of jobs, it cannot be changed over stages. As the first study, in this paper, a mathematical model in form of a mixed integer linear programming model is proposed for the mentioned problem. Using CPLEX, the small-sized instances of the problem can be solved to optimality by the model. Yet, due to the NP-hardness of the problem under study, large instances cannot be optimally solved in a reasonable amount of time. Consequently, a novel population-based algorithm based on imperialist competitive metaheuristic algorithm is also proposed. This algorithm includes some advanced features of imperialist behavior mechanisms, imperialist competition operators, and revolutionary phases. The proposed algorithm is first finely tuned using Taguchi method. Then, to evaluate the proposed algorithm, its effectiveness is compared with a commercial solver (CPLEX) and two available metaheuristics algorithms in the literature, a simulated annealing algorithm, and a particle swarm optimization algorithm. In this regard, a set of large instances is generated and the tested algorithms are compared. The computational results indicate efficient performance of the proposed algorithm over the existing metaheuristics.