مقاله #666

چکیده

در این مقاله قصد داریم یک مسئله‌ی برنامه ریزی تور چند فعالیتی را که دارای تقاضای زمانی متغیری می‌باشد، مورد حل و فصل قرار دهیم. هدف این بوده که به محاسبه‌ی یک زمانبند تیمی برای تعداد ثابتی از کارکنان پرداخته تا بتوانیم مسائلی نظیر پوشش مازاد و پوشش ناکافی در بخش‌های فعالیتی موازی را در یک افق یک هفته ای به حداقل سطح ممکن برسانیم. محدودیت‌های پیچیده‌ی مختلفی در این مسئله وجود دارد: همه‌ی کارکنان متفاوت بوده و می‌توانند چندین فعالیت مختلف را در طول یک شیفت روز انجام داده، زمان استراحت و توقف، انعطاف پذیر بوده و تقاضاها برای بازه‌ی زمانی 15 دقیقه ای صادر می‌شود. کارکنان دارای نقش‌های قانونی می‌باشند که باید آن‌ها را انجام دهند ولی تابع هدف هیچ کدام از مقیاس‌های کیفی مربوط به زمانبندی هر فرد را در نظر نمی‌گیرد. به طور دقیق تر، در این مسئله به ترکیب همزمان زمانبندی‌های روزهای تعطیل، زمانبندی شیفت، تخصیص شیفت، تخصیص فعالیت، توقف و اجرای تخصیص می‌پردازد.

برای حل این مسئله، چهار روش را توسعه داده‌ایم: یک مدل برنامه نویسی خطی صحیح ترکیبی فشرده، یک روش مشابه با انشعاب و قیمت، مشابه با روشی با یک برنامه‌ی پویا برای حل ابتکاری زیر مسائل، یک روش ابتکاری diving و یک روش ابتکاری حریصانه بر مبنای حل کننده‌ی پیشنهادی ما برای حل زیر مسئله. نتایج محاسباتی که بر مبنای موارد واقعی و نمونه‌هایی از موارد واقعی بدست آمده است نشان می‌دهد که روش پیشنهادی ما می‌تواند راهکارهای با کیفیتی را در زمانی کوتاه فراهم سازد. الگوریتم‌های ما در یک نرم افزار تجاری ادغام شده‌اند که در حال حاضر در یک شرکت مورد استفاده قرار می‌گیرد.