具有指数和位置学习效应的机器排序问题

本文考虑指数学习效应和位置学习效应同时发生的新的排序模型.工件的实际加工时间不仅依赖于已经加工过工件正常加工时间之和的指数函数,而且依赖于该工件所在的位置.单机排序情形下,对于最大完工时间和总完工时间最小化问题给出多项式时间算法.此外某些特殊情况下,总权完工时间和最大延迟最小化问题也给出了多项时间算法.流水机排序情形,对最大完工时间和总完工时间最小化问题在某些特殊情形下给出多项时间算法.     

一类具有资源限制的调度问题

研究了具有线性退化及学习效应作用下的单台机器调度问题,对于工件的到达时间是其资源消耗量的正的严格单调递减函数时,考虑了总资源消耗量限定情形下求最大完工时间最小化问题给出了最优算法.     

工件可转包加工的排序问题研究

研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS).     

恶化率与工件无关的线性加工时间调度问题

讨论恶化率与工件无关的线性加工时间调度问题 .对于工件间具有平行链约束 ,目标函数为极小化最大完工时间的单机问题 ,分别就链不允许中断和链允许中断两种情况给出了最优算法 .对于工件间没有优先约束 ,目标函数为极小化完工时间和的平行机问题 ,证明了工件按基本加工时间不减排列可以得到最优调度 .     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

混合无等待流水线干扰管理调度方法研究

针对带分批约束的混合无等待流水加工环境中干扰事件的出现导致初始调度计划发生偏离的问题,研究如何运用干扰管理理论来应对工件变更扰动情况,建立了兼顾最小化工件完工时间加权和指标(初始调度目标)和最小化工件完工滞后时间加权和指标(偏离校正目标)的干扰管理调度模型,提出了双层微粒群优化策略与随机多邻域搜索机制相结合的混合求解算法。数值算例仿真实验结果表明,包含“插入-交换”大概率邻域搜索算子的混合微粒群优化算法求解本文所构建的干扰管理调度模型是有效的。     

在线可中断二台机器流水作业问题

本文研究了可中断的二台机器流水作业排序问题,目标函数为最小化最大完工时间,工件实时到达,工件信息在工件到达之前不可知。我们给出了该在线问题的下界,并对问题中只有两个到达时间的特殊情况给出了3/2竞争的在线算法。     

带学习效应和资源依赖的单机排序模型

在工业生产中,随着员工操作技能的熟练程度的增加,对于相同的任务越往后加工,所花的时间将会减少。 同时,为了尽早完工,管理者也会考虑给加工工件分配一定量的额外资源来缩短工件加工时间。 本文基于以上实例,讨论了工件的实际加工时间既具有学习效应又依赖所分配资源的单机排序问题。 在问题中,假设工件的学习效应是之前已加工工件正常加工时间和的指数函数。 同时随着分配给工件资源量的增加,工件的实际加工时间呈线性减少,所需费用呈线性增加。对这一排序模型,主要探讨以下五个目标函数:最小化最大完工时间与资源消耗量总费用的和;最小化总完工时间与资源消耗量总费用的和;最小化加权总完工时间与资源消耗量总费用的和;最小化总提前、总延误、总共同交货期与资源消耗量总费用的和以及最小化总提前、总延误、总松弛交货期与资源消耗量总费用的和。 本文对前三个目标函数相应的排序问题给出了多项式时间可求解的算法。 对后两个目标函数所涉及的排序问题借助于指派问题分别给出了时间复杂性为O(n³)的算法。     

工件按加工长度不增序到达的最小化最大流程在线分批排序

研究单处理机工件按加工长度不增顺序到达的在线分批排序问题．工件按时在线到达,目标是最小化最大流程．流程时间是指工件的完工时间与到达时间的差值,它体现了工件在系统内的逗留时间．对于批容量有界的情形,给出了一个竞争比为1＋√5/2的最好可能的在线算法;对于批容量无界的情形,给出了一个竞争比为√2的最好可能的在线算法．     

工件延误和可拒绝下的单机重新排序问题的近似方案

研究工件延误产生干扰且延误工件可拒绝下的单机重新排序问题.在该问题中,给定计划在零时刻到达的一个工件集需在一台机器上加工,工件集中的每个工件有它的加工时间和权重,在工件正式开始加工前,按照最短赋权加工时间优先的初始排序已经给定,目标函数是极小化赋权完工时间和,据此每个工件的承诺交付截止时间也给定.然而,在工件正式开始加...     

基于重新排序时间错位限制下的最小化总完工时间的平行分批排序（英文）

In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.     

Rescheduling with new orders and general maximum allowable time disruptions

We study the rescheduling with new orders on a single machine under the general maximum allowable time disruptions. Under the restriction of general maximum allowable time disruptions, each original job has an upper bound for its time disruption (regarded as the maximum allowable time disruption of the job), or equivalently, in every feasible schedule, the difference of the completion time of each original job compared to that in the pre-schedule does not exceed its maximum allowable time disruption. We also consider a stronger restriction which additionally requires that, in a feasible schedule, the starting time of each original job is not allowed to be scheduled smaller than that in the pre-schedule. Scheduling objectives to be minimized are the maximum lateness and the total completion time, respectively, and the pre-schedules of original jobs are given by EDD-schedule and SPT-schedule, respectively. Then we have four problems for consideration. For the two problems for minimizing the maximum lateness, we present strong NP-hardness proof, provide a simple 2-approximation polynomial-time algorithm, and show that, unless \(\text {P}= \text {NP}\), the two problems cannot have an approximation polynomial-time algorithm with a performance ratio less than 2. For the two problems for minimizing the total completion time, we present strong NP-hardness proof, provide a simple heuristic algorithm, and show that, unless \(\text {P}= \text {NP}\), the two problems cannot have an approximation polynomial-time algorithm with a performance ratio less than 4/3. Moreover, by relaxing the maximum allowable time disruptions of the original jobs, we present a super-optimal dual-approximation polynomial-time algorithm. As a consequence, if the maximum allowable time disruption of each original job is at least its processing time, then the two problems for minimizing the total completion time are solvable in polynomial time. Finally, we show that, under the agreeability assumption (i.e., the nondecreasing order of the maximum allowable time disruptions of the original jobs coincides with their scheduling order in the pre-schedule), the four problems in consideration are solvable in polynomial time.     

原始工件的完工时间限制下的最小化最大延误时间的重新排序

考虑由两个代理引起的重新排序问题,其中每个代理都在公共的加工资源下完成各自的不可中断加工的工件.每个代理要求在仅依赖工件的完工时间时最小化某一个特定的目标函数.考虑在原始工件的完工时间限制下的两个代理的单机最小化最大延误时间的重新排序问题.证明了该问题能在多项式时间或者拟多项式时间内解决.     

On single processor scheduling problems with learning dependent on the number of processed jobs

The importance of the role that learning plays in manufacturing, industry and computer systems is undeniable as well as the profit that can be increased if this phenomenon is taken into consideration for short- and long-term optimization. In this paper, we focus on scheduling jobs on a single processor, where its effectiveness can increase with the number of processed jobs, to minimize one of the following objectives: the maximum completion time with the release dates, the maximum lateness and the number of late jobs. It is proved that these well known polynomially solvable problems become at least NP-hard with the considered learning models. To solve them we provide some elimination procedures that are used to construct a branch and bound algorithm. Furthermore, we propose some fast heuristics for the problem of minimizing the number of late jobs with the general model of the learning effect.     

Scheduling time-dependent jobs under mixed deterioration

We consider a new model of time-dependent scheduling. A set of deteriorating jobs has to be processed on a single machine which is available starting from a non-zero time. The processing times of some jobs from this set are constant, while other ones are either proportional or linear functions of the job starting times. The applied criteria of schedule optimality include the maximum completion time, the total completion time, the total weighted completion time, the maximum lateness and the number of tardy jobs. We delineate a sharp boundary between computationally easy and difficult problems, showing polynomially solvable and NP-hard cases.     

Some single-machine scheduling problems with actual time and position dependent learning effects

In this paper we study some single-machine scheduling problems with learning effects where the actual processing time of a job serves as a function of the total actual processing times of the jobs already processed and of its scheduled position. We show by examples that the optimal schedules for the classical version of problems are not optimal under this actual time and position dependent learning effect model for the following objectives: makespan, sum of kth power of the completion times, total weighted completion times, maximum lateness and number of tardy jobs. But under certain conditions, we show that the shortest processing time (SPT) rule, the weighted shortest processing time (WSPT) rule, the earliest due date (EDD) rule and the modified Moore’s Algorithm can also construct an optimal schedule for the problem of minimizing these objective functions, respectively.     

带有分批费用的容量有界的单机平行分批排序问题

考虑的问题是在添加工资费用或包装费用等附加的分批费用下,如何使单机平行分批中总完工时间和分批费用之和达到最小.首先我们假定工件和批处理机都在零时刻到达,工件被成批地进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用.然后对具有m个不同的加工时间,批容量有界且为固定值b的情形下目标函数为∑C_j与分批费用之和这一排序问题,利用动态规划的方法给出了多项式时间算法,时间界为O(b²m2m²222^m).     

Single machine scheduling with a general exponential learning effect

In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.