Flow shop learning effect scheduling problem with release dates

In a real-world assembly environment, the components of a product arrive at a plant over time. Works-in-process are assembled into end-products by following an identical processing route. When a worker at a particular stage repeatedly handles similar tasks and gains the knowledge to execute a task efficiently, the processing time for later tasks is shortened significantly. This assembly process can be described as the flow shop learning effect scheduling problem with release dates, in which the learning effect is dependent on position. The objective is to minimize one of three different criteria, namely, makespan, total completion time and total quadratic completion time. This scheduling problem is formulated as a mixed integer programming (MIP) model. For small-scale problems, a branch and bound (B&B) algorithm with an efficient branching rule is proposed to obtain optimal solutions. The MIP model and the B&B algorithm provide key evidence for academic research. For large-scale problems, the asymptotic optimality of a class of shortest processing time available (SPTA)-based heuristics is proven in terms of probability limit. The convergence property indicates that an SPTA-based heuristic can serve as an optimal schedule under the industrial setting, where thousands of tasks are typically executed on a set of machines. Extensive numerical experiments demonstrate the effectiveness of the proposed algorithms.