Subset-restricted interchange for dynamic min-max scheduling problems (Q2706175)

This paper deals with scheduling two specific jobs within a sequence of \(n\) jobs, i.e. the so-called pair-wise job interchange problem. This problem is extended to the case that interchanging of the two given jobs is permitted only, if the intermediate jobs belong to a restricted subclass of jobs. The problem then is to determine the order of the two jobs which is optimal with respect to a cost function. In order to solve the problem efficiently a precedence order is derived and utilized by the subsequently applied branch and bound algorithm. By means of numerical examples it is shown that the algorithm with precedence order saves on an average about 58\% of the CPU time compared with an algorithm without precedence order necessary for solving the problem.