Two machine mixed shop scheduling problem with controllable machine speeds (Q1821024)

The paper considers a two machine scheduling problem in which the objective is to determine an optimal machine speed pair and an optimal schedule. Each job consists of two operations. We have a mixed shop scheduling problem which means that for a subset of the jobs the order of processing on the machines is fixed (flow shop) and for the remaining jobs the order is free (open shop). The machine speeds are controllable. The objective function takes the form \(C_ 0t^{q_ 1}_{\max}+C_ 1(s')^{q_ 2}+C_ 2(t')^{q_ 2}\), where \(C_ 0\), \(C_ 1\), \(C_ 2\), \(q_ 1\), \(q_ 2\) are constant, \(t_{\max}\) is the makespan of the schedule, s' and t' are the speeds of the two machines. An \(0(n^ 2 \log n)\) algorithm is presented to solve this problem assuming that power and root of the functions encountered in the algorithm can be calculated in constant time.