کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
476116 | 699417 | 2010 | 10 صفحه PDF | دانلود رایگان |

A common problem in production planning is to sequence a series of tasks so as to meet demand while satisfying operational constraints. This problem can be challenging to solve in its own right. It becomes even more challenging when higher-level decisions are also taken into account. For example, determining which shifts to operate clearly impacts how tasks are then scheduled; additionally, reducing the number of shifts that must be operated can have great cost benefits. Integrating the shift-selection and task-sequencing decisions can greatly impact tractability, however, traditional mathematical programming approaches often failing to converge in reasonable run times. Instead, we develop an approach that embeds mathematical programming, as a mechanism for solving simpler feasibility problems, within a larger search-based algorithm that leverages dominance to achieve substantial pruning. In this paper, we introduce the Shift-Selection and Task Sequencing problem (SS-TS), develop the Test-and-Prune algorithm (T&P), and present computational experiments based on a real-world problem in automotive stamping to demonstrate its effectiveness. In particular, we are able to solve to provable optimality, in very short run times, a number of problem instances that could not be solved through traditional integer programming methods.
Journal: Computers & Operations Research - Volume 37, Issue 7, July 2010, Pages 1298–1307