25260

زمان‌بندي استوار در محيط فلوشاپ تركيبي با در نظر گرفتن محدوديت منابع تجديدناپذير وابسته به زمان (مطالعه‌ي موردي)

PhD

مهندسي صنايع

1394-95

1400/06/23

محمد مهدوي مزده

مهدي حيدري

مهندسي صنايع

در اين مطالعه، يك سيستم فلوشاپ تركيبي با دو ايستگاه كه در ايستگاه اول تنها يك ماشين و در ايستگاه دوم بيش از يك ماشين وجود دارد، مورد بررسي قرار مي‌گيرد. در يك سيستم فلوشاپ رايج، كارها به صورت سري از ايستگاه اول تا ايستگاه نهايي پردازش مي‌شوند. فرض بر اين است كه كارها جهت پردازش بر روي ماشين ايستگاه اول، به منبع مصرفي تجديدناپذير (مانند مواد خام) نيز نياز دارند؛ بنابراين سيستم فلوشاپ تركيبي مورد مطالعه،‌ داراي محدوديت منبع بوده و در دوره‌هاي متوالي در دسترس قرار مي‌گيرد. منبع در دسترس در ابتداي دوره، غيرقطعي بوده و در دامنه مشخصي در طول زمان نوسان مي‌كند. هم‌چنين، ايستگاه دوم شامل ماشين‌هايي است كه هر كدام امكان پردازش هر كاري را ندارند و كارها در خانواده‌هايي دسته‌بندي شده‌اند. هدف غايي اين مطالعه، ارائه زمان‌بندي استوار با قابليت اطمينان بالا است به نحوي كه مجموع زماني زودكرد و ديركرد كمينه گردد. اين پژوهش برگرفته از يك مطالعه موردي در حوزه سيستم‌هاي تشخيصي تصويربرداري مولكولي است. تصويربرداري مولكولي زيررشته‌اي از راديولوژي است كه به كمك پرتوداروها جهت مطالعه جزييات ساختاري و كاركردي اعضاي بدن، شناسايي بيماري در مراحل اوليه و تجويز درمان درخور مورد استفاده قرار مي‌گيرد. خروجي اين مطالعه ارائه متدولوژي استوار براي سيستم نوبت‌دهي با توجه به محدوديت دارويي در چنين مركزي است. پرتوداروهاي مورد استفاده در اين طيف مراكز از عنصري شيميايي و پرتوزا به نام تكنسيم-99 با نيم‌عمر حدود 6 ساعت حاصل مي‌شود. پس از تزريق پرتودارو به بيماران و طي گذشت مدت زماني،‌ بدن بيماران در اسكنرهاي مجهز در مراكز تصويربرداري مولكولي اسكن مي‌شوند. در صورتي كه اسكن زودتر از زمان مشخصي اخذ شود، احتمال وجود نويز در اسكن زياد خواهد بود و در صورتي كه اسكن ديرتر از اين زمان اخذ شود، كيفيت عكس از تفسيرپذيري پاييني برخوردار خواهد بود. اين مطالعه موردي بر روي يك مساله فلوشاپ تركيبي با محدوديت منبع غيرقطعي نگاشت شده، سپس به سه زيرمساله مجزا تجزيه شده و براي هر زيرمساله راهكارهايي ارائه مي‌گردد: 1- منبع در دسترس در چه زمان‌هايي بايستي توزيع شوند (چه زماني عنصر پرتوزا بايد استخراج شود)؟ 2- چه زماني كارها با توجه ميزان منبع غيرقطعي در ايستگاه اول زمان‌بندي شود؟ (چه زماني پرتودارو با توجه عدم‌قطعيت در ميزان اكتيويته تكنسيم-99 آماده شده و تزريق صورت گيرد)؟ 3- كارها پس از اتمام عمليات قبلي، به كدام ماشين اختصاص يافته و در چه زماني پردازش بر روي آن‌ها صورت گيرد (چه زماني اسكن شروع شود)؟ زيرمساله اول با بررسي و تحليل شرايط بهينگي منبع، به مدل رياضي برنامه‌ريزي نيمه‌مقعر نگاشت مي‌شود. زيرمساله دوم به مساله زمان‌بندي تك‌ماشينه با در نظر گرفتن محدوديت منبع تجديدناپذير با تامين دوره‌اي و تابع هدف مجموع انحراف از زمان موعد تحويل، نگاشت مي‌شود. زيرمساله سوم نيز به مساله ماشين‌هاي موازي همسان با در نظر گرفتن خانواده كارها، ماشين‌هاي واجدالشرايط و زمان ترخيص و با هدف كمينه كردن مجموع انحراف از زمان موعد تحويل، نگاشت مي‌شود. سپس بر اساس راهكارهاي پيشنهادي براي هر زيرمساله، مكانيزمي پيشرو، جهت تعامل تصميمات هر زيرمساله با يك‌ديگر توسعه داده مي‌شود. در بخش مديريت عدم‌قطعيت منبع، مجموعه عدم‌قطعيت جديدي جهت كاهش محافظه‌كاري و افزايش قابليت اطمينان مدل‌هاي رياضي و الگوريتم‌هاي توسعه يافته، ارائه مي‌شود. نتايج نوبت‌دهي در طول يك هفته براي 30 الي 40 بيمار، نشان از قابليت اطمينان و مقياس‌پذيري بسيار بالا (هم در تئوري و هم در عمل) الگوريتم‌ها و مجموعه عدم‌قطعيت پيشنهادي دارد. سنجه درصد انحراف از زمان ايده‌آل اسكن با استفاده از الگوريتم‌هاي پيشنهادي و الگوي مديريت عدم‌قطعيت نوين، حدود 2 درصد براي 30 بيمار و 5 درصد براي 35 بيمار در هفته است. اين در حالي است كه در شرايط فعلي مركز اين انحراف براي 30 بيمار به طور متوسط بالاي 50 درصد است.

1400/07/03

Robust Scheduling of Hybrid Flowshops considering Time-dependent Non-renewable Resources (A Case Study)

1/1/1900 12:00:00 AM

In this research, we study a hybrid flowshop with two stages in which the first stage contains only one machine and the second stage is controlled by two machines. In a classical flowshop, jobs are processed from the first to the final stage in a series. We assume that jobs of the first stage require a non-renewable resource; hence, the hybrid flowshop is resource-constrained, and the resource is available at different periods. The resource is available at the beginning of any period and is uncertain and fluctuates in certain support. Moreover, the second stage includes several machines which are not able to process every job, and jobs are categorized into families. The ultimate goal of this research is to propose robust schedulings with a decent reliability to minimize the sum of total earliness and tardiness. This research is derived from the appointment scheduling of outpatients in an imaging department. The main goal of this study is to coordinate the assignments of radiopharmaceuticals and imaging scanners with the scheduling of outpatients. The radio-pharmaceuticals are a periodically supplied but non-renewable resource and should be prepared in a strict time window. We investigate optimal and robust scenarios to avoid deteriorating the quality of the schedules. Most procedures in molecular imaging require Technetium-99m with a limited half-life and involve several steps that are constrained by strict time windows. We develop several practical resource scenarios to schedule robust appointments for a significant number of outpatient demands on a limited number of scanners. We also develop a novel, less conservative robust optimization approach to capture the uncertainty of the resource. In this approach, the uncertainty handling mechanism recursively feeds the realized parameters in a convex vector to the next parameter. We introduce a mathematical model with the objective to better utilize the available activity administered from Technetium-99m supplies without compromising the scan quality and reducing the unnecessary radiation exposure to patients. We decompose the complete problem into three sub-problems: 1. When to elute? (pseudo-concave programming), 2. when to prepare the radio-pharmaceutical and inject to patients considering the uncertainty of alluded activity (single machine scheduling considering periodically supplied nonrenewable resource and uncertainty in resource to minimize the total earliness and tardiness), and 3. when to scan? (parallel machine scheduling considering release times, family jobs, and eligible machines to minimize the total earliness and tardiness). We first investigate the structural properties of each sub-problem and develop optimal and sub-optimal algorithms. We propose a novel uncertainty set to reduce the conservatism and increase the reliability of mathematical models and algorithms. In this approach, unlike the classical robust optimization approaches, we directly enforce the perturbations of the uncertain parameter in the realization mechanism. We also discuss the superiority of this approach w.r.t. the adjustable robust optimization. The main motivation of this study is to reduce any deviation from the ideal scanning start time. If the patient is scanned too early, then the scanned image will be too noisy, and the analysis of the image will be impossible. If the patient is scanned too late, again, it will result in poor image quality. Our proposed algorithm, along with the novel uncertainty set indicates that about 2 percent of 30 patients and 5 percent of 35 patients during a week (including 10 minutes allowable tolerance) for the deviation of ideal start time criterion. In the current status of the center, it has been found that there is above 50 percent deviation for 30 patients in a week. Speaking about conservatism, the novel approach provides an improvement of 8 to 40 percent in the objective function by the increase of patients number from 30 to 55 in 72 percent of cases compared to the classical robust optimization approach. We implement and solve out integrated mixed-integer programming model on a Hyper-computing cluster called SURFsara Cartesius Dutch supercomputer; nevertheless, we showed that the developed algorithm can be run on a single home PC with a high scalability and provides more than acceptable bounds for the problem.

مركز تصويربرداري پزشكي , پرتودارو , زمانبندي , تحليل بهينگي , پيچيدگي زماني , بهينه سازي استوار قابل تنظيم , برنامه ريزي عدد صحيح آميخته

Medical Diganostic Center , Radiopharmaceutical , Scheduling , Optimality Analysis , Mixed Integer Programming , َAdjustable Robust Optimization , Computational Complexity