Scheduling and Buffer Allocation for Cyclic Permutation Flow-Shops using Max-Plus based Formulation

摘要

Scheduling is a decision-making process that concerns the allocation of limited resources to a set of tasks with the view of optimizing one or more objectives. In this work, we are concerned with the cyclic permutation flow-shop problem where a set of parts is repeatedly produced (cyclic) and the sequence of parts on all the machines remains the same (permutation). We develop a mathematical formulation for the above problem using max-plus algebra. Buffers help in reducing the machine idle times and can be modeled as machines with zero processing times for all parts. The location and capacity of buffers have a significant impact on the throughput of the system. The max-plus formulation is extended to determine the ideal locations and capacities of buffers that yield a higher throughput by examining the inter-operation dependencies.