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

ما یک الگوریتم گسترش محدودیت پیشرفته برای توالی ماشین ترکیبی و مساله زمان‌بندی سطح را ارایه می‌کنیم، که در چارچوب شاخه و کران(شاخه-محدودیت) استفاده می‌شود. روش جدید تنها مثال حل‌نشده از Drexl و سایرین (‏۲۰۰۶)‏و چهار تا از ۸ نمونه حل‌نشده (‏۲۰۱۳)‏Yavuz را حل می‌کند. این مقاله همچنین ۱۸ مورد جدید را معرفی می‌کند که ۹ مورد از آن‌ها توسط الگوریتم حل شده‌اند. توالی بهینه تا ۲۵۰ ماشین به دست می‌آید.

Highlights•An advanced constraint propagation algorithm is developed on a new multi-level structure of auxiliary variables.•The new algorithm solves 24 of the 36 original instances without branching.•A branch-and-bound framework is developed to utilize constraint propagation.•The new algorithm solves 5 of nine unsolved instances from the literature.•۱۸ new instances with up to 250 cars are created and 9 of them are solved.AbstractWe present an advanced constraint propagation algorithm for the combined car sequencing and level scheduling problem, used within a branch-and-bound framework. The new method solves the only unsolved instance from Drexl et al. (2006) and four of the eight unsolved instances from Yavuz’s (2013) testbeds. The paper also introduces 18 new instances, 9 of which are solved by the algorithm. Optimal sequences of up to 250 cars are obtained.