Concurrent operations assignment and sequencing for particular assembly problems in flow lines

In this paper, we deal with the problem of optimally assigning and sequencing the operations of a set of jobs to the machines of a flow line. The operations of each job are to be executed according to the precedence constraints specified by the operation graph. Here, we analyze the special case in which the assembly operations are strictly ordered. The problem consists in assigning the operations to the machines and sequencing them so that some productivity index is maximized. The model proposed fits in particular situations where few identical product items requiring a large amount of operations are to be produced, and accounts for such issues as: limited buffer capacity, FCFS versus LCFS buffer operation, set-up and transportation times, machines with different speeds, tools and tool magazine restrictions. In this scenario, polynomial-time dynamic programming algorithms for makespan or inventory costs minimization are proposed.