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

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

工件加工时间是开工时间线性函数的单机排序问题

研究了具有线性恶化工件的单机排序问题,其中线性恶化工件指的是工件的加工时间是开工时间的线性增长函数.在一般情况下,对目标函数为极小化完工时间平方和与极小化总误工数问题分别给出了最优算法.此外,在分段情况下,对目标函数为极小化最大完工时间问题也给出了最优算法.     

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

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

两类加工时间是一般函数的单机排序问题

考虑了两类有一般加工时间函数的排序问题. 工件的加工时间分别为基本加工时间与开工时间函数、位置函数的和. 对加工时间依赖开工时间的模型,证明了一定条件下极小化最大完工时间和极小化总完工时间是多项式可解的. 对加工时间依赖开工位置的模型,给出极小化最大完工时间和极小化总完工时间的最优序,同时证明了极小化加权总完工时间的一个最优排序性质并给出一个贪婪算法.     

并行分批排序综述

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

有关单机两代理排序问题的两个结果

研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.     

具有线性减少加工时间的资源约束单机排序问题

讨论具有连续资源的单机排序问题.在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数.考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量.第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间.对两类问题讨论了最优排序的某些特征.基于对问题的分析,分别给出了求解最优资源分配的方法.结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立.     

无关机上极小化求和问题的平行分批排序(英文)

本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对p_(ij)≤p_(ik)(i=1,…,m;1≤j≠k≤n)这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨论了p_(ij)=p_i(i=1,…,m;j=1,…,n)这种情况,当不考虑工件可被拒绝时,对极小化加权总完工时间的排序,我们给出了其最优算法;当考虑工件可被拒绝时,对极小化被接收工件的加权总完工时间加上被拒绝工件的总拒绝费用的排序,我们设计了一拟多项时间算法.     

工件间具有串并有向图约束的单机随机排序问题

研究机器发生随机故障的单机排序问题,其中工件间的优先约束为串并有向图,目标函数为极小化加权完工时间和,证明了此问题多项式时间可解,并给出了多项式时间算法.     

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

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

A computational study with a new algorithm for the three-machine permutation flow-shop problem with release times

We consider the three-machine permutation flow-shop scheduling problem with release times where the objective is to minimize the maximum completion time. A special solvable case is found for the F2/r_j/C_max problem, which sharpens the boundary between easy and hard cases and can be used to compute a tight lower bound for our problem. Two dominance rules are generalized and applied to generating initial schedules, directing the search strategy and decomposing the problem into smaller ones. The branch and bound algorithm proposed here combines an adaptive branching rule with a fuzzy search strategy to narrow the search tree and lead the search to an optimal solution as early as possible. Our extensive numerical experiments have led to a classification of ‘easy' vs. ‘hard' problems, dependent only on the relative size of the release times. The algorithm has quickly solved approximately 90% of the hardest test problem instances with up to 200 jobs and 100% of the large problems classified as easy.     

Two-machine flow shop scheduling with deteriorating jobs: minimizing the weighted sum of makespan and total completion time

This paper considers a two-machine flow shop scheduling problem with deteriorating jobs in which the processing times of jobs are dependent on their starting times in the sequence. The objective is to minimize the weighted sum of makespan and total completion time. To analyse the problem, we propose a mixed integer programming model, and discuss several polynomially solvable special cases. We also present a branch-and-bound algorithm with several dominance rules, an upper bound and a lower bound. Finally, we present results of computational experiments conducted to evaluate the performance of the proposed model and the exact algorithm.     

Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs

We study a two-machine flowshop scheduling problem with time-dependent deteriorating jobs, i.e. the processing times of jobs are an increasing function of their starting time. The objective is to minimize the total completion time subject to minimum makespan. We propose a mixed integer programming model, and develop two pairwise interchange algorithms and a branch-and-bound procedure to solve the problem while using several dominance conditions to limit the size of the search tree. Several polynomial-time solvable special cases are discussed. Finally, numerical studies are performed to examine the effectiveness and the efficiency of the proposed algorithms.     

Bi-criteria single machine scheduling with a time-dependent learning effect and release times

This paper deals with a bi-criteria single machine scheduling problem with a time-dependent learning effect and release times. The objective is to minimize the weighted sum of the makespan and the total completion time. The problem is NP-hard, thus a mixed integer non-linear programming formulation is presented, and a set of dominance properties are developed. To solve the problem efficiently, a procedure is then proposed by incorporating the dominance properties with an ant colony optimization algorithm. In the proposed algorithm, artificial ants construct solutions as orders of jobs based on the heuristic information as well as pheromone trails. Then, the dominance properties are added to obtain better solutions. To evaluate the algorithm performance, computational experiments are conducted.     

Two-machine flow shop total tardiness scheduling problem with deteriorating jobs

This paper studies a two-machine scheduling problem with deteriorating jobs which their processing times depend on their waiting time. We develop a branch and bound algorithm to minimize the total tardiness criteria. A lower bound, several dominance properties and an initial upper bound derived from a heuristic algorithm are used to increase the speed of branch and bound algorithm and decrease its required memory space. Computational results are presented to evaluate effectiveness and efficiency of the algorithms.     

A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness

This paper addresses the NP-hard problem of scheduling N jobs on a single machine with due dates, sequence-dependent setup times and no preemption where the objective is to minimize the maximum tardiness. An algorithm based on branch-and-bound permutation schemes is developed including the implementation of lower and upper bounding procedures, and three dominance rules. Computational experiments demonstrate the effectiveness of the algorithm. In the experiments, the impacts of control parameters to generate test instances on algorithm performance (CPU times) are studied by statistics methods.     

Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times

In this paper, we study the identical parallel machine scheduling problem with a planned maintenance period on each machine to minimize the sum of completion times. This paper is a first approach for this problem. We propose three exact methods to solve the problem at hand: mixed integer linear programming methods, a dynamic programming based method and a branch-and-bound method. Several constructive heuristics are proposed. A lower bound, dominance properties and two branching schemes for the branch-and-bound method are presented. Experimental results show that the methods can give satisfactory solutions.     

Parallel machine scheduling problems with a single server

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.     

Minimizing makespan on a single batching machine with release times and non-identical job sizes

We consider the problem of scheduling jobs with release times and non-identical job sizes on a single batching machine; our objective is to minimize makespan. We present an approximation algorithm with worst-case ratio 2+ε, where ε>0 can be made arbitrarily small.