传统组合优化问题一般研究在给定参数下的优化问题。线性约束下的组合优化问题将经典组合优化问题中的参数变成受线性约束的决策变量,使决策者综合考虑参数的优化与组合优化问题的结构,更加完整的决策过程丰富了组合优化问题的实用性,并提出了大量具有挑战性的问题,拓展了组合优化问题的研究。在实际生活中的交通运输、生产加工、医院分诊等多个场景带来更广泛的应用。本文基于线性约束下的组合优化问题框架,结合经典的区间排序问题和区间划分问题提出了若干种新的模型,包括线性约束下的区间排序问题、线性约束下的区间划分问题和带权线性约束下的区间排序问题。本文讨论了新模型的计算复杂性结果,并基于线性规划手段讨论相关算法。本文主要贡献有:·提出了多个线性约束下的区间排序问题模型,讨论了其计算复杂性,得到了其为NP难问题。·对于提出的问题讨论设计了相关算法,对于带权的线性约束下的区间排序问题约束个数为常数时,设计了多项式时间算法。