✍ Scribed by Nodari Vakhania; Evgeny Shchepin
No coin nor oath required. For personal study only.
We consider the multiprocessor job shop scheduling problem (JSP) with unrelated processors, an extension of the classical JSP. The precedence relations between the operations are given by an acyclic directed weighted graph, in which nodes represent operations and arcs represent precedence relations. The whole set of operations is partitioned into m subsets, and operations from kth subset have to be performed by any machine from the respective kth set of unrelated machines. The solution space of this generalized problem increases signiÿcantly as compared with that of the JSP. An algorithm is proposed, which drastically reduces this solution space. If we let and to be the number of operations and machines in each subset of operations and machines, then with a probability of almost 1, we generate approximately ( ) m and 2 m( -1) m times less feasible schedules than the number of all active feasible schedules of any corresponding instance of JSP and our generalized problem, respectively.
📜 SIMILAR VOLUMES