زمان بندی کار پرسنل بیمارستان با استفاده از روش ستون سازی

زمان بندی کار پرسنل بیمارستان عبارت است از تعیین برنامه کاری دوره ای برای هر یک از پرسنل بیمارستان، به طوریکه، 1) کلیه کارهای بیمارستان توسط پرسنل انجام شود. 2) خواسته های پرسنل برای انتخاب ساعت کاری، لحاظ شود. 3) هزینه بیمارستان حداقل شود. در این مقاله زمان بندی پرسنل بیمارستان نمازی شیراز که یکی از بزرگترین بیمارستانهای جنوب کشور است مورد بررسی قرار گرفته شده است. در این بیمارستان شش نوع شیفت کاری صبح، عصر، شب، صبح-عصر، صبح-شب و تعطیل وجود دارد. در بخش جراحی این بیمارستان که شامل 25 پرسنل پرستاری، بهیاری و کمک بهیاری است احتیاج به برنامه های هفتگی برای هر یک از پرسنل می باشد این برنامه ها علاوه بر سه ویژگی بالا، باید به گونه ای باشند که 4) اضافه کاری پرسنل حداقل شود. 5) تعداد پرسنل قرضی از واحدهای دیگر تا حد امکان کم شود. 6) برنامه های هفتگی دارای حداقل شیفتهای صبح-عصر و صبح-شب باشند و بین تعداد شیفتهای صبح و عصر تعادل باشد. 7) حداقل تعداد شیفت شب هر پرسنل که به سابقه کاری آن پرسنل بستگی دارد، در برنامه های هفتگی رعایت شود. مساله زمان بندی بیمارستان نمازی شیراز یک مسئله اعداد صحیح است که حل آن بوسیله مدل اعداد صحیح و توسط نرم افزار های موجود در ایران زمان بر است. از طرفی بزرگ شدن تعداد پرسنل بصورت نمایی در زمان حل تاثیر گذار می باشد. روش ستون سازی یکی از روشهای سریع برای حل این نوع مسائل می باشد. روش ستون سازی بر اساس تجزیه دانتزیک-ولف کار می کند. در تئوری دانتزیک-ولف مدل مساله به یک مساله اصلی و تعدادی مسائل کوچکتر به نام زیر مساله تجزیه می شوند. در مساله اصلی جواب بهینه بر اساس ترکیب محدب نقاط گوشه ای (در مسائل کران دار) مناسب به دست می آید این نقاط گوشه ای را زیر مساله ها در اختیار مساله اصلی قرار می دهند که این کار به صورت مرحله ای انجام می شود. حسن روش ستون سازی این است که برای رسیدن به جواب بهین به تمامی نقاط گوشه ای احتیاج نیست. در مساله بیمارستان نمازی، مساله اصلی شامل تابع هدف و محدودیتهای کلی می باشد برای هر یک از پرسنل یک زیر مساله وجود دارد وظیفه زیر مساله ها تولید برنامه های هفتگی برای پرسنل می باشد که این برنامه های هفتگی در اختیار مساله اصلی قرار می گیرد تا بتواند با ترکیب محدب آنها به یک جواب بهین مناسب برسد. جواب بهین به دست آمده از روش ستون سازی به طور معمول صحیح نمی باشد برای رسیدن به جواب صحیح می توان روش ستون سازی را در قالب درخت شاخه و کران پیاده سازی کرد یعنی اینکه تا رسیدن به جواب صحیح، در هر گره درخت شاخه و کران روند ستون سازی اجرا شود. در درخت شاخه و کران الگوه های متفاوتی برای شاخه زدن روی متغیرها وجود دارد به طور مثال می توان روی هر متغیر غیر صحیح شاخه زد یا اینکه روی تعدادی از متغیرها که مجموع آنها مقدار غیر صحیح دارد شاخه زد. انتخاب الگوی شاخه زدن تآثیر زیادی روی اندازه درخت و در نتیجه زمان رسیدن به جواب صحیح دارد. البته می توان برای هر مساله کاربردی الگوی شاخه زدن خاص پیشنهاد کرد که سریعتر به جواب صحیح برسیم.