平行机上带有前瞻区间的不相容工件组在线排序问题

研究当不相容工件组的个数与机器数相等时，具有前瞻区间的单位工件平行机无界平行分批在线排序问题工件按时在线到达，目标是最小化最大完工时间．具有前瞻区间是指在时刻t，在线算法能预见到时间区间（t，t＋β[]内到达的所有工件的信息．不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工．当β≥1时，提供了一个最优的在线算法；当0≤p〈1时，提供了一个竞争比为1＋α的最好可能的在线算法，其中＆是方程OL0＋（1＋β）α＋β-1=0的一个正根．最后，给出了当β=0时稠密算法竞争比的下界，并提供了达到该下界的最好可能的稠密算法．

不相容工件组的单机随机调度问题研究

研究不相容工件组在单台批处理机上的分批加工问题,工件具有随机的到达时间和加工时间。不相容工件组是指属于不同组的工件不能被安排在同一批中加工。首先,以长期平均代价最小为优化目标,以缓冲库中工件数为实时状态,建立了基于半马尔科夫决策过程的系统模型。然后,通过策略迭代算法对其进行优化控制,同时为了缓解大状态空间导致的维数灾问题,给出了基于模拟退火的Q学习算法。仿真实验验证了所提出方法的有效性。

具有前瞻区间的两个工件组单机在线排序问题

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在无界平行分批排序中,一台容量无限制机器可将多个工件形成一批同时加工,每一批的加工时间等于该批中最长工件的加工时间.具有前瞻区间是指在时刻t,在线算法能预见到时间区间（t,t＋β）内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为1＋α的最好可能的在线算法,其中α是方程2α~2＋（β＋1）α＋β-2=0的一个正根,这里0≤β〈1.

最小化时间表长的带有多个工件组单机无界继列批在线排序

考虑了批容量无界情形下带有多个工件组的单机继列分批的在线排序问题.每个工件具有各自的安装时间和加工时间(s,p),属于不同组的工件不能在同一批中加工,目标函数是最小化最大完工时间,给出了此问题的一个竞争比为2的最好可能的在线算法.