Output details

A Submodular Optimization Approach to Bicriteria Scheduling Problems with Controllable Processing Times on Parallel Machines

<12>Scheduling problems with controllable processing times have been intensively studied since the 1980s with the main focus on single-criterion versions; results on more general (hence much more challenging) bicriteria versions are scarce. We overcome the limitations of traditional bicriteria research by introducing for scheduling problems their equivalent submodular optimization counterparts. Although the bicriteria aspect creates an additional difficulty, making submodular optimisation problems parametric, our new algorithms are either faster than known methods or solve previously intractable problems. In contrast with earlier approaches that construct trade-off in a step-by-step manner, the new technique finds a trade-off directly as a parametric function.