مدل سازی مسئلۀ زمان بندی تک ماشین با تولید دسته ای و خرابی تصادفی و حل آن به وسیلۀ روش شاخه و کران (مقاله علمی وزارت علوم)
درجه علمی: نشریه علمی (وزارت علوم)
آرشیو
چکیده
در این مقاله مسئلۀ زمان بندی تک ماشین با تولید دسته ای و خرابی تصادفی ماشین بررسی می شود. در این مسئله هر کار متعلق به یک خانوادۀ کار است و هر خانوادۀ کار زمان آماده سازی معلوم و مستقل از توالی دارد. همچنین فرض می شود یک خرابی ماشین در طول افق برنامه ریزی اتفاق می افتد و زمان شروع و طول تصادفی با توزیع احتمال دلخواه و از قبل مشخص دارد. تابع هدف مسئله حداقل سازی مجموع حداکثر زودکرد و حداکثر دیرکرد موردانتظار کارهاست. تاکنون در پژوهش های گذشته مطالعه ای بر این مسئله مشاهده نشده است. برای این مسئله یک مدل جدید برنامه ریزی عدد صحیح خطی مختلط توسعه داده شده است. با توجه به NP-hard بودن مسئله برای حل بهینۀ آن، یک الگوریتم شاخه و کران جدید با اصول غلبه و یک حد پایین کارا ارائه شده است که از یک الگوریتم ابتکاری جدید برای به دست آوردن حد بالا استفاده می کند. به منظور ارزیابی عملکرد الگوریتم های معرفی شده، تعداد 2520 عدد مسئلۀ نمونه طراحی و با الگوریتم های ارائه شده، حل شده است. نتایج محاسباتی نشان می دهد 98% مسائل نمونه در محدودۀ زمانی مشخص شده با الگوریتم شاخه و کران به صورت بهینه حل شده اند و میانگین درصد انحراف از جواب بهینه در الگوریتم ابتکاری ارا ئه شده کمتر از 30% است. این موارد کارایی الگوریتم های ارائه شده را تأیید می کند.Modeling a single machine scheduling problem with batch production and the random breakdown and solving it by branch and bound method
Purpose: Scheduling of batch production and machine disruption are the two main challenges in manufacturing organizations. Due to the complexity of production processes, many industries try to group jobs according to family criteria and use a common setup time to process every family. Also, machine breakdown is an influential factor in the planning of production systems. In this paper, the problem of scheduling a single machine with family setup times and breakdowns is studied. It is assumed that there is a breakdown with an uncertain start time and duration based on the specified probability distribution functions during the planning horizon. The objective function of this problem is the sum of the expected maximum earliness and maximum tardiness.
Design/methodology/approach: For the problem under study, a new mixed integer linear programming model has been developed. Due to the NP-hardness of the problem, a new branch and bound algorithm with the dominance rules and an efficient lower bound is presented for its optimal solving, which uses a new heuristic approach to achieve the upper bound.
Findings: To evaluate the performance of the introduced algorithms, 2520 instances were designed and solved with the presented algorithms. The computational results indicated that 98% of the instances were optimally solved in the specified time limitation by the branch and bound algorithm, and the average percentage of deviation from the optimal solution in the proposed heuristic approach was less than 30%. The results demonstrated the efficiency of the proposed algorithms.
Research limitations/implications: Considering the newness of the problem investigated in this paper, the proposed instances and algorithms can be used as a basis for evaluating other solution methodologies in future research studies. Also, considering other modes of machine failures such as scenario-based failures or re-scheduling the jobs to minimize the deviations of the actual schedule from the planned program, situations with more than one machine such as parallel machines, flow shops, and job shops, other objective functions related to scheduling such as maximum completion time or total completion time, as well as the development of other exact, heuristic or meta-heuristic algorithms are suggested as subjects for future study.
Practical implications: The problem studied in this paper can be attractive and practical for manufacturing organizations. Industries such as automotive, ship and aircraft manufacturing, steel, telecommunication power supply manufacturing, electronic, computer processors, and all industries and systems that somehow deal with the batch production process and unexpected machine breakdowns, can benefit from the results of this research.
Social implications: Because in this study, the starting and finishing times of machine breakdowns were predicted, by applying the results of this research, the production of defective products will be prevented when the machine breaks down, and this leads to the reduction of waste in the environment. Also, according to the objective function defined in the problem investigated in this article, the implication of the results of this research in production environments leads to the reduction of earliness and tardiness costs, which in turn increases the work efficiency of human resources and as a result, increases the job satisfaction.
Originality/value: It seems no study has been conducted on the single machine scheduling problem with batch production, random breakdown, and the objective function of minimizing the sum of the expected maximum earliness and maximum tardiness of the jobs. Particularly, innovations of this paper are threefold: i) a new mixed integer linear programming model was developed for the problem; ii) a novel heuristic approach was proposed to solve the problem, based on hill climbing (PHC); and iii) a new branch and bound algorithm with the dominance rules and an efficient lower bound was presented to solve the problem optimally, which used the PHC heuristic approach to achieve the upper bound.
تبلیغات
