Minimizing maximum earliness in single-machine scheduling with flexible maintenance time
Author(s):
Abstract:
We consider minimizing the maximum earliness in the single-machine scheduling problem with flexible maintenance. In this problem, preemptive operations are not allowed, the machine should be shut down to perform maintenance, tool changing or resetting takes a constant time, and the time window inside which maintenance should be performed is prede ned. We show that the problem is NP-hard. Afterward, we propose some dominance properties and an ecient heuristic method to solve the problem. Also, we propose a branch-and-bound algorithm, in which our heuristic method, the lower bound, and the dominance properties are incorporated. The algorithm is computationally examined using 3,840 instances up to 14,000 jobs. The results impressively show that the proposed heuristic algorithm obtains the optimal solution in about 99.5% of the cases using an ordinary processor in a matter of seconds at most.
Keywords:
Language:
English
Published:
Scientia Iranica, Volume:24 Issue: 4, 2017
Pages:
2082 to 2094
https://magiran.com/p1734817
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یکساله به مبلغ 1,390,000ريال میتوانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.
In order to view content subscription is required
Personal subscription
Subscribe magiran.com for 70 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!