Abstract:
در این مقاله مسئلۀ زمان بندی تک ماشین با تولید دسته ای و خرابی تصادفی ماشـین بررسـی مـیشـود. در ایـن مسئله هر کار متعلق به یک خانوادٔه کار است و هر خانوادٔه کار زمان آماده سازی معلوم و مستقل از توالی دارد. همچنین فرض میشود یک خرابی ماشین در طول افق برنامه ریزی اتفاق میافتد و زمان شروع و طول تصادفی با توزیع احتمـال دلخواه و از قبل مشخص دارد. تابع هدف مسئله حداقل سازی مجموع حداکثر زودکـرد و حـداکثر دیرکـرد موردانتظـار کارهاست . تاکنون در پژوهش های گذشته مطالعه ای بر این مسئله مشاهده نشده است . برای این مسئله یک مدل جدیـد برنامه ریزی عدد صحیح خطی مختلط توسعه داده شده است . با توجه به NP-hard بودن مسئله برای حل بهینۀ آن ، یـک الگوریتم شاخه و کران جدید با اصول غلبه و یک حد پایین کارا ارائه شده است که از یـک الگـوریتم ابتکـاری جدیـد برای به دست آوردن حد بالا استفاده می کند. به منظور ارزیابی عملکرد الگوریتم های معرفیشده ، تعداد ٢٥٢٠ عدد مسئلۀ نمونه طراحی و با الگوریتم های ارائه شده ، حل شده است . نتایج محاسباتی نشان می دهد ٩٨% مسائل نمونه در محـدودٔه زمانی مشخص شده با الگوریتم شاخه و کران به صورت بهینه حل شده اند و میانگین درصد انحراف از جـواب بهینـه در الگوریتم ابتکاری ارائه شده کمتر از ٣٠% است . این موارد کارایی الگوریتم های ارائه شده را تایید میکند.
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.
Machine summary:
با الهام از گورن ١٩ و سبوکيوقلو٢٠ (٢٠٠٩)، تـابع هدف استوار مجموع موردانتظار حداکثر زودکرد و حداکثر ديرکرد براي اين مسـئله در نظـر گرفتـه شـده اسـت کـه به صورت زير تعريف ميشود: )به تصویر صفحه رجوع شود) که در آن [] و [] مقادير موردانتظار حداکثر زودکرد و حداکثر ديرکردند و به صورت زير محاسبه ميشوند: )به تصویر صفحه رجوع شود) در اين روابط ، نشان دهندٔە زمان تکميل کار ≥( i≥١) در توالي است و با توجه به تصـادفيبـودن زمـان شروع و طول خرابي، مقدار آن نيز تصادفي است .
Scheduling a single machine with job family setup times to minimize total tardiness.
A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness.
Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time.
Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times.
Serial-batching scheduling with time- dependent setup time and effects of deterioration and learning on a single-machine.
1346317 1 Cheng 2 Xiong 3 Pei 4 Fan 5 Tang 6 Mönch 7 Roob 8 Li 9 Kong 10 Emde 11 Hinder 12 Mason 13 Abdallah 14 Jang 15 Shen 16 Zhu 17 Detti 18 Lu 19 Goren 20 Sabuncuoglu 21 Lee 22 Bruno 23 Downey 24 Gupta 25 Chantaravarapan 26 Mixed Integer Linear Programming 27 Branch and Bound 28 Earliest Due Date 29 Back Tracking 30 Pairwise Hill Climbing 31 Minimum Slack Time 32 Schaller 33 O'Donovan