Abstract: Weconsider non-preemptive open shop scheduling problem on two machines and its variations with machine routing and resource constraints. While the classic two-machine open shop is solvable in linear time, its variations are often NP-hard even in the simplest settings. The routing open shop is a natural generalization of the open shop and traveling salesman problem. Here the jobs are located at nodes of some transportation network, while the machines traverse the network to execute the jobs in the open shop environment. In the open shop with resource constraints, each job requires additional resources of renewable and non-renewable types. In the latter case, we investigate the problem with processing times controllable through the resource consumption given by a convex function. Although we indicate and analyze NP-hard special cases of the problems under consideration, we focus on the known and new polynomially solvable subcases of those problems. Such approaches as list scheduling, max-flow models, greedy algorithms, and instance reduction techniques for the makespan minimization objective are discussed. We use a twostage algorithm for the open shop with resource-dependent durations, where processing times and the lower bound on the makespan are calculated at the first step, and then an optimal schedule is constructed.

Cite: Zakharova Y. , Chernykh I. , Krivonogova O.
On Computational Complexity of Two-Machine Open Shop Variations with Routing and Resource Constraints
In compilation Optimization and Applications : Book of abstrats XV International Conference on Optimization Methods and Applications (OPTIMA-2024). 2024. – C.117.

Identifiers: No identifiers

Citing: Пока нет цитирований