Modelling and scheduling a batch-type production on identical machines (Q1099069)

A new formulation and a near-optimal algorithm are presented for some variation of an NP-hard parallel scheduling problem with forest-type constraints and a \(C_{\max}\) optimality criterion where multiple performing of each operation is required. The problem is formulated using a state space approach. In the algorithm the priority in which the assignment of operations to machines is made is based on the level of operation in the graph of precedence constraints. The worst-case performance bound of the algorithm is given, and the average performance is illustrated with computational examples.