带强制工期的可中断平行机排序问题

讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.     

带强制工期的双机开放车间排序问题

讨论了强制工期相等的n个工件在双机开放车间加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,同题可能会无可行排序.先讨论了问题的可行性.如果问题可行,找出一个可行序列作为预排序列,并提出了一个算法计算每个工件尽可能迟的开工时间.而后,提出了一个多项式时间最优算法,在预排序列的基础上,通过调整两台机器上最先加工的工件来获得最优排序.     

极小化最大提前完工时间的两平行机排序问题

讨论了在两台同型平行机上,加工带截止期限的n个工件,在机器可空闲条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会无可行排序.先讨论问题的可行性,通过子集和问题归约,证明了判定问题的可行性是NP-complete的.如果问题可行,接着讨论了问题的复杂性,通过划分问题归约,证明了其是NP-complete的.最后,考虑了工件加工时间相等的特殊情形,提出了一个算法在多项式时间内获得最优排序.     

极小化最大提前完工费用的可中断排序问题

讨论了带截止期限的$n$个工件在单机上加工,工件间存在优先约束,在允许机器空闲的条件下,确定一个工件的可中断排序,极小化最大提前完工费用.首先考虑两种特殊情形:(1)截止期限相同,存在优先约束;(2)截止期限任意,不存在优先约束.针对两种情形分别给出了时间复杂度为$O(n^2)$的算法.在此基础上,考虑普遍情形,即截止期限任意,存在优先约束,也给出了一个时间复杂度为$O(n^2)$的算法.由于工件不允许延迟,问题可能会无可行排序,需先对问题的可行性进行讨论.     

带有退化效应和序列相关运输时间的排序问题

考虑带有退化效应和序列相关运输时间的单机排序问题. 工件的加工时间是其开工时间的简单线性增加函数. 当机器单个加工工件时, 极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的, EDD序对于极小化最大延迟问题不是最优排序, 另外, 就交货期和退化率一致情形给出了一最优算法. 当机器可分批加工工件时, 分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法.     

带调整时间的一类排序问题

进一步讨论带磨损因子的排序问题,在相应问题中对工件j,j=1,2,…,n,引入了调整时间sj,它同磨损因子bj一样同该工件何时加工无关.要求适当排列这n个工件的加工顺序,使目标函数值达最小.给出了加工全程、完工时间之和及JIT问题在引入调整时间下的最优算法.     

工件加工时间增加的排序问题(1‖Cmax)

讨论了工件加工时间随工件开工时间线性增加的排序问题,考虑的目标函数是最大完工时间,证明了加工时间是简单线性增加情况下最大完工时间问题是多项式时间可解的,对于加工时间是一般线性增加情况,研究了最优排序的性质,同时证明了两种特殊情况下最大完工时间问题也是多项式时间可解的。     

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

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

一个具有退化的两个代理的排序问题

考虑两个代理的带有退化的单机排序问题.第一个代理J以完工时间和为目标函数,第二个代理J以最大延迟为目标函数,并且两个代理的加工时间是按时间退化的,所谓按时间退化就是每个工件的加工时间是其开始加工时间的函数.问题的目标是寻找一种排序,使得两个代理的目标函数之和达到最小.证明该问题可在O(n_1n_2(n_1+n_2))时间内求解.     

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time

We consider a scheduling problem in which n jobs with distinct deadlines are to be scheduled on a single machine. The objective is to find a feasible job sequence that minimizes the total weighted completion time. We present an efficient branch-and-bound algorithm that fully exploits the principle of optimality. Favorable numerical results are also reported on an extensive set of problem instances of 20-120 jobs.     

Single-machine common due window assignment and scheduling to minimize the total cost

In this paper we consider a single-machine common due window assignment and scheduling problem with batch delivery cost. The starting time and size of the due window are decision variables. Finished jobs are delivered in batches. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find a job sequence, a delivery date for each job, and a starting time and a size for the due window that jointly minimize the total cost comprising earliness, weighted number of tardy jobs, job holding, due window starting time and size, and batch delivery. We provide some properties of the optimal solution and present polynomial-time algorithms for the problem.     

Parallel machine scheduling with a common due window

In this paper, we consider a machine scheduling problem where jobs should be completed at times as close as possible to their respective due dates, and hence both earliness and tardiness should be penalized. Specifically, we consider the problem with a set of independent jobs to be processed on several identical parallel machines. All the jobs have a given common due window. If a job is completed within the due window, then there is no penalty. Otherwise, there is either a job-dependent earliness penalty or a job-dependent tardiness penalty depending on whether the job is completed before or after the due window. The objective is to find an optimal schedule with minimum total earliness–tardiness penalty. The problem is known to be NP-hard. We propose a branch and bound algorithm for finding an optimal schedule of the problem. The algorithm is based on the column generation approach in which the problem is first formulated as a set partitioning type formulation and then in each branch and bound iteration the linear relaxation of this formulation is solved by the standard column generation procedure. Our computational experiments show that this algorithm is capable of solving problems with up to 40 jobs and any number of machines within a reasonable computational time.     

储存时间有上限的两阶段供应链排序问题

研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输:加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件.工件的运输完成时刻与完工时刻之差定义为工件的储存时间,且有相应的储存费用,且任意工件的储存时间都不超过某一常数.若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻,则有相应的提前(延误)惩罚费用.目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和.先证明该问题是NP-难的,后对单位时间的储存费用不超过单位时间的延误惩罚费用的情形给出了伪多项式时间算法.     

基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．     

具有老化效应的单机共同工期安排和工件可拒绝排序问题

研究共同工期安排和具有老化效应的单机排序问题。在整个加工过程中,工件的实际加工时间是与其所在位置和工件本身老化率相关的函数,生产商可以通过支付一定的处罚费用而拒绝加工某些工件。鉴于生产过程中出现老化效应,通过采取维修活动来提高生产率。目标是划分接受工件集和拒绝工件集,确定接受工件集中工件的加工次序和维修活动安排的位置,以极小化接受工件的提前、延误、工期与拒绝工件的总处罚费用的加权和。对这一问题,首先将其转化为指派问题并构造了最优多项式时间算法;其次,证明了目标函数满足一定条件下的问题的更一般形式能够在多项式时间内得到最优解;最后,对本文问题的一个特殊情况,设计了具有更低时间复杂度的多项式动态规划算法。