Reversible-shop scheduling (Q1821023)

The concepts of reversible-shop and route-dependent reversible-shop are defined. In a reversible shop a job is processed on the machines in a given order, say \(M_ 1,M_ 2,...,M_ m\) or in the reverse order \(M_ m,M_{m-1},...,M_ 1\). The processing time on each machine is independent of the route taken by the job. For the route-dependent reversible shop the processing times differs for each of the two routes. For two machines the reversible shop is an open shop. It is shown that minimizing the makespan for a reversible shop with 3 machines is binary NP-hard. Efficient algorithms are given for some special cases involving dominating machines. Machine \(M_ k\) is dominated by \(M_ r\) iff the maximum processing time of an operation on \(M_ k\) is less than or equal to the minimum processing time of an operation on \(M_ r\). Efficient algorithms are given for the 3 machines \(M_ 1\), \(M_ 2\), \(M_ 3\) where \(M_ 2\) dominates the other two, or \(M_ 1\) dominates \(M_ 2\) and \(M_ 2\) dominates \(M_ 3\). When all processing times are equal to 1 for an arbitrary number of machines efficient algorithms are given for minimizing the makespan and minimizing the sum of completion times both in the case of infinite and zero storage space between the machines. For route-dependent reversible-shop with 3 machines an efficient algorithm is presented for the case machine \(M_ 2\) dominates the other two machines \(M_ 1\), \(M_ 3\).