最小化加权误工工件数的多代理平行分批排序

考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,并且当工件具有单位权时,可在多项式时间解决.进一步证明当代理数固定时,两个问题都有FPTAS算法.     

人工带隙材料的拓扑性质

近年来,人工带隙材料(如声子晶体和光子晶体)由于其优异的性能,已成为新一代智能材料的研究焦点.另一方面,材料拓扑学由凝聚态物理领域逐渐延伸到其他粒子或准粒子系统,而研究人工带隙材料的拓扑性质更是受到人们的广泛关注,其特有的鲁棒边界态,具有缺陷免疫、背散射抑制和自旋轨道锁定的传输等特性,潜在应用前景巨大.本文简要介绍拓扑材料特有的鲁棒边界态的物理图像及其物理意义,并列举诸如光/声量子霍尔效应、量子自旋霍尔效应、Floquet拓扑绝缘体等相关工作;利用Dirac方程,从原理上分析光/声拓扑性质的由来;最后对相关领域的发展方向和应用前景进行了相应的讨论.     

同时最小化最大费用和最大完工时间的双代理无界平行分批排序

有两个代理A和B, 每个代理都各自有一个工件集. 同一个代理的工件可以在同一批中加工, 而且每一个代理都有一个需要最小化的函数. 研究在无界平行分批处理机上同时最小化代理A的最大费用和代理B的最大完工时间问题, 并给出一个算法, 它可在多项式时间内找到关于这个问题的所有Pareto最优点.     

关于最小化最大延迟的分批排序问题的一个动态规划算法的注解（英文）

In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batching machine scheduling problem of minimizing the maximum lateness, denoted 1|p-batch|L_(max), a dynamic programming algorithm with time complexity O(n~2) is well known in the literature.Later, this algorithm is improved to be an O(n log n) algorithm. In this note, we present another O(n log n) algorithm with simplifications on data structure and implementation details.