Two-Machine Super-Shop Scheduling Problem (Q3978740)

The author introduces a new scheduling model called two-machine super- shop. This model is a straightforward generalization of flow-shop, job- shop, open-shop and mixed-shop problems for two machines \(A\) and \(B\). Each job consists of two operations, where one of the two operations may be a dummy operation with zero processing time. All jobs are partitioned into three classes, the first class consists of jobs with machine order \(AB\) for the operations, the second class includes jobs with machine order \(BA\), whereas the third class contains jobs without any predetermined machine order. If all jobs belong to the first class or all jobs belong to the second class, we get the flow-shop problem. If all jobs belong to the first or second class, the model describes job-shop. If all jobs belong to the third class, open-shop problem are characterized. Finally, if all jobs belong to the first or third class or, if all jobs belong to the second or third class, then we get mixed- shop problems. A polynomial algorithm is developed for two-machine super-shop problems with the makespan as performance measure. If we denote the number of jobs by \(n\) and the maximum cardinality of the first class and the second class by \(k\) \((\leq n)\), the time complexity of the algorithm is \(O(k\cdot\log k+n)\). It is worthwile to mention that this time complexity of the algorithm for super-shop problems is as good as the time complexities of the best available algorithms for the special cases of flow-shop, job-shop, open-shop and mixed-shop.