具有优先约束的不完全恒速机排序问题

讨论了任务具有优先约束的可中断不完全恒速机排序问题,若处理机具有不同开始加工时间的可中断排序问题存在最优算法,则相应的不完全恒速机排序问题也有最优算法。     

处理机具有准备时间的Qm,aj｜pj=1｜Cmax排序问题

讨论了处理机具有准备时间的Qm,aj|pj=1|Cmax排序问题,通过这一问题的一个下界,给出了一个最优算法,算法的复杂性为O（m^2）。     

各机器具有相同加工时间的Flow Shop 成组排序问题

本文讨论了m台机器的Folw Shop成组排序问题，工件在不同机器上的加工时间相同，目标函数为极小化完工时间和。给出了一个多项式时间可解的最优算法。     

排序问题P2|prmp|Cmax在中断—重复模型下的调度

对于传统的中断-恢复模型下的P2｜prmp｜Cmax问题，已有最优调度规则。但中断-恢复模型并不是一般意义下的中断模型。在某些情况下，被中断的任务不能被简单的恢复加工，而是在该任务被重新加工之前必须有一定的延迟时间。延迟可能是该项任务的一部分（或者是全部）需要返工的时间。本文在研究了排序问题P2｜prmp｜Cmax在中断-重复模型下的调度，指出对于选择哪一个任务被中断的问题是NP—hard的；而对于如何处理被中断的任务的问题，指出当被中断任务的最初被加工时间由Xj增加为Xj＋△xj=Xj/（1-1/2aj）时，可使得两台处理机的时间表长相等，从而达到最优。最优时间表长为：Cmax^＊=1/2n∑j=1pj＋ajxj/（2-aj）。最后给出了在中断-重复模型下的调度规则。     

具有机器故障的单机随机JIT排序问题

对中断－继续和中断－重复两种模型研究具有机器故障的单机随机JIT排序问题, 目标函数是期望完工时间 与工期方差和. 对中断－继续模型证明SSDE问题的最优排序具有关于期望加工时间的V-形性质, 并给出了一个拟多项式 的动态规划算法. 同时对SSDE问题和ESSD问题 进行了比较, 证明了SSDE问题的最优解是一个非常好的ESSD问题的近似最优解. 在一定的条件下, SSDE问题 的最优解就是ESSD问题的最优解. 对中断－重复模型, 由于完工时间的方差无法求出, JIT排序问题至今没得到解决, 故从实际 应用角度用SSDE问题替代ESSD问题, 证明了SSDE问题最优解具有关于期望占用机器时间的V-形性质, 并给出了 一个拟多项式的动态规划算法, 提出了一个研究JIT问题的中断－重复模型的新思路.     

极小化总完工时间的同时加工排序

讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.     

一个不同时刻加工成本有差异的单机排序问题

考虑一个单机排序问题:一批工件在零时刻到达可加工,加工时不可中断,在某个给定时间区间外的加工工时将招致额外的加工成本;当时间区间为给定参数时,要求确定一个最优加工序,当时间区间为决策变量时,要求找到一个最优序及最优区间位置, 由此来最小化总额外加工成本．文中对各种区间外单位加工工时之额外成本的情况给出了多项式算法, NP-hardness的证明及伪多项式时间算法．     

关于一类自由作业机器排序问题

文章研究文［１］中提出的加工时间依赖于机器的自由作业排序问题。Ｍ．Ｄｏｒｏｒ在［１］中提出了一个算法（算法３．４）。最近，Ａ．Ｊ．Ｖａｋｈａｒｉａ、Ｂ．Ｃａｔａｙ［２］及项思明、唐国春［３］均指出Ｍ．Ｄｏｒｏｒ的算法不是最优的。项思明和唐国春提出对这类问题在机器连续加工情形下的一种求解方法，即将排序问题化成指派问题。本文对这种解法作了简化，并回答文［３］中提出的几个问题。     

带机器故障的两台机带权误工数排序问题

讨论机器带故障中断的两台平行机排序问题,工件加工时间均为单位时间,目标是极小化带权误工工件数.当转移时间t=0时给出了最优的算法.当t≠0时,给出了一个多项式时间的近似算法,并证明算法解与最优解至多相差一个带权误工数.     

带权的误工排序问题的最优算法

研究工件有不同的权(重要性)、但是与工件加工时间有反向"一致性"关系,并且在保证工件的一个子集T中的工件必须不误工的前提下,使得带权的误工工件的个数(误工造成损失的费用)为最少的排序问题1∣T,(pi≤pj ) (wi≥wj)∣∑wjUj ;提出该问题的最优算法,证明提出的算法得到的排序是最优排序,而且证明这个最优排序在所有最优排序中不误工工件总的加工时间为最小.     

Properties of optimal schedules in preemptive shop scheduling

In this work we show that certain classical preemptive shop scheduling problems with integral data satisfy the following integer preemption property: there exists an optimal preemptive schedule where all interruptions and all starting and completion times occur at integral dates. We also give new upper bounds on the minimal number of interruptions for various shop scheduling problems.     

A projective algorithm for preemptive open shop scheduling with two multiprocessor groups

We study a multiprocessor extension of the preemptive open shop scheduling problem, where the set of processors is partitioned into processor groups. We show that the makespan minimization problem is polynomially solvable for two multiprocessor groups even if preemptions are restricted to integral times.     

Uniform machine scheduling with machine available constraints

1.IntroductionIntheclassicalparallelmachineschedulingareaweassumethatmachinesarealwaysavailable.However,aspointedin[1],inrealindustrysettingsthisassumptionmaynotbetrue.Forexample,machinesmaynotalwaysbeavailablebecauseoftheirpreventivemaintenanceduringtheschedulingperiod.Thatistosay,eachmachineiisunavailablefromsibuntilrib(05sib5rib),where0SkSm,withmbeingthenumberofunavailabilityperiodsformachineiduringtheplanninghorizon.Inotherwords,somepapersstatethatmachinesareavailableintimewindows,whichi…     

带有固定区间的单机双代理可中断总误工问题

研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断,且工件到达时间与工期满足一致关系,目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序,使得满足第二个代理目标可行情况下,第一个代理目标函数值最小.在固定区间等于加工时间的情况下,利用分块原则,提出了一个伪多项式时间动态规划算法,并给出了固定区间大于加工时间情况下的时间复杂度分析.     

P_m,a_i‖C_(max)问题的A_(kk)算法的最坏情况性能比

讨论任务的加工是不可中断,机器速度相同且机器具有不同开始加工时间的排序问题,目标函数是极小化最大完工时间.对于一般情况,给出了关于Akk算法的最坏情况性能比.     

可抢占条件下的项目调度研究综述

可抢占条件下的项目调度通过暂时中断某些活动的执行,释放资源给更重要的活动,从而优化项目的工期、成本等绩效指标。可抢占项目调度问题以其重要的理论价值和应用背景,受到了学界和业界的广泛关注。对国内外可抢占项目调度的研究成果进行了系统性总结与梳理,综述了可抢占项目调度问题的数学模型及其求解算法,总结了可抢占项目调度问题的一些扩展问题和应用情况,最后指出了未来进一步的研究方向。     

Almost nonpreemptive schedules

Graph-theoretical models are described for solving preemptive and nonpreemptive scheduling problems with renewable resources. Conditions are obtained for nonpreemptive schedules to exist. These results may be applied for reducing the preemptions in the schedules obtained by the two-phase method developed for preemptive scheduling on unrelated processors.     

Preemptive scheduling and antichain polyhedra

We present a theoretical framework, which is based upon notions of ordered hypergraphs and antichain polyhedra, and which is dedicated to the combinatorial analysis of preemptive scheduling problems submitted to parallelization constraints.This framework allows us to characterize specific partially ordered structures which are such that induced preemptive scheduling problems may be solved through linear programming. To prove that, in the general case, optimal preemptive schedules may be searched inside some connected subset of the vertex set of an Antichain Polyhedron.     

Computation scheduling in multiprocessor systems with several types of additional resources and arbitrary processors

The problem of feasible preemptive scheduling in a multiprocessor system is considered for when scheduled intervals are assigned, processor performance can be arbitrary, there are several types of additional resources, and the time for executing tasks depends linearly on the amount of additional resources allocated to them. Polynomial algorithms based on reducing the original problem to a flow problem and a linear programming problem are developed.