Interval Scheduling Under Linear Constraints

The traditional combinatorial optimization problem generally considers the optimization problem under given parameters.Combinatorial optimization problems under linear constraints consider the parameters in classic combinatorial optimization problems as linearly constrained decision variables,enabling decision makers to comprehensively consider the optimization of parameters and the structure of combinatorial optimization problems,and a more complete decision process enriches the utility of combinatorial optimization problems.Multiple scenarios such as transportation,production and processing,and hospital triage in real life bring wider applications.Based on the combinatorial optimization problem under linear constraints,we consider the classical combinatorial optimization problem,e.g.interval scheduling problem,interval partitioning problem,and several new models are proposed,including the interval scheduling problem under linear constraints,the interval partitioning problem under linear constraints and weighted interval scheduling problem under linear constraints.This thesis discusses the complexity results of the new models and discusses related algorithms based on linear programming technique.The main contributions of this thesis include:·Several interval scheduling problem under linear constraints are proposed.We discuss their computational complexity,and prove the NP-hardness of these problems.·Some related algorithms are discussed and designed for the problems raised,and we propose a polynomial time algorithm when there is a constant number of constraints for the interval scheduling problem with weighted linear constraints.