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

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

基于加工时间之和学习效应下的单机成组排序问题

研究具有加工时间之和学习效应下的一个新型成组排序问题,工件的学习效应是之前工件加工时间之和的函数,组学习效应是成组加工所在的位置的函数. 考虑最大完工时间和总完工时间两个问题,证明了这两个问题都是多项式时间可解的,并提出了相应的多项式时间算法.     

具有安装时间和学习效应的单机排序问题

讨论了工件具有安装时间和学习效应的单机排序问题。安装时间是依赖于已加工完的工件的实际加工时间的简单函数,即p-s-d形式。工件的加工时间不仅与已完成工件的加工时间有关,还与工件的加工位置有关。证明了极小化最大完工时间,极小化完工时间k总和,极小化完工时间k次幂的和是多项式可解的,另外还证明了满足一定条件下的极小化加权完工时间和,极小化最大延误和极小化延迟时间和问题是多项式可解的。     

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

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

同时具有学习效应和退化效应的单机排序问题

本文给出了一种同时具有一般化学习效应和退化效应的单机排序模型。在此模型中,工件的实际加工时间既与工件所在位置又与其开工时间有关,且工件在加工之后具有一个配送时间。其中学习效应是工件所在位置的函数,退化效应是工件开工时间的函数。证明了极小化最大完工时间和极小化总完工时间问题是多项式可解的,在满足一定的条件下,极小化加权总完工时间和极小化最大延误问题也是多项式可解的。推广了一些已有文献中的结论。     

具有凸资源约束的单机指数学习效应问题

研究在所有工件的正常加工时间均相同的情况下具有指数学习效应和凸资源约束的单机排序问题.给出了两种模型:在资源消耗总费用有限的情况下,以工件的最大完工时间为目标函数;在工件的最大完工时间有限的情况下,以资源消耗总费用为目标函数.求两种模型下的最优排序和最优资源分配,使得目标函数最小.证明这两个问题都是多项式时间可解的,并给出了相应的算法.     

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

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

具有恶化效应和凸资源分配关系的单机排序问题

研究工件加工时间具有恶化效应和凸资源关系的单机排序问题,其中工件的实际加工时间是其正常的加工时间,工件开工时间(具有恶化效应)及消耗资源量的函数。目标为在最大完工时间(总完工时间、总等待时间、完工时间总绝对差与等待时间总绝对差)小于或等于给定常数的条件下找到工件的最优排序和最优的资源分配使工件的总资源消耗量最少。在单机状态下,证明了此问题是多项式时间可解的,并给出了求解该问题的算法和数值实例。     

带恶化和综合学习效应的成组排序问题研究

本文研究了成组技术下带恶化和综合学习效应的排序问题,工件的加工时间带综合学习效应。对最小化时间表长问题,我们给出了多项式算法,并且证明了带一致关系的最小化总完工时间问题也是多项式可解的。     

一类具有学习效应和安装时间的单机排序问题

本文主要讨论了工件加工时间具有学习效应和安装时间的单机排序问题。工件的加工时间不仅与之前已加工完的工件加工时间有关,还与工件的加工位置有关。安装时间是依赖于已加工完的工件的实际加工时间的简单函数,即p-s-d形式。本文证明了极小化最大完工时间,极小化总完工时间,极小化完工时间的平方和问题具有多项式算法,也证明了极小化加权总完工时间,极小化最大延误和极小化总误工问题在某些条件下具有多项式算法。     

Single-machine scheduling problems with an actual time-dependent deterioration

In this paper, we consider the single machine scheduling problems with an actual time-dependent deterioration effect. By the actual time-dependent deterioration effect, we mean that the processing time of a job is defined by increasing function of total actual processing time of jobs in front of it in the sequence. We show that even with the introduction of an actual time-dependent deterioration to job processing times, makespan minimization problem, total completion time minimization problem, the total lateness, and the sum of the quadratic job completion times minimization problem remain polynomially solvable, respectively. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness minimization problem, and the total tardiness minimization problem can be solved in polynomial time under certain conditions.     

Solvable Cases of the No-Wait Flow-Shop Scheduling Problem

The no-wait flow-shop scheduling problem (NWFSSP) with a makespan objective function is considered. As is well known, this problem is ????-hard for three or more machines. Therefore, it is interesting to consider special cases, i.e. special structured processing time matrices, that allow polynomial time solution algorithms. Furthermore, it is well known that the NWFSSP with a makespan objective function can be formulated as a travelling salesman problem (TSP). It is observed that special structured processing time matrices for the NWFSSP lead to special structured distance matrices for which the TSP is polynomially solvable. Using this observation, it is shown that some NWFSSPs with fixed processing times on all except two machines are well solvable while the others are conjectured to be ????-hard. Also, it is shown that NWFSSPs with a mean completion time objective function restricted to semi-ordered processing time matrices are easily solvable.     

Single-machine scheduling simultaneous with position-based and sum-of-processing-times-based learning considerations under group technology assumption

This paper considers the problems of scheduling with the effect of learning on a single-machine under group technology assumption. We propose a new learning model where the job actual processing time is linear combinations of the scheduled position of the job and the sum of the normal processing time of jobs already processed. We show that the makespan minimization problem is polynomially solvable. We also prove that the total completion time minimization problem with the group availability assumption remains polynomially solvable under agreeable conditions.     

Shop scheduling problems with multiprocessor tasks on dedicated processors

The computational complexity of shop scheduling problems with multiprocessor tasks on dedicated processors is investigated. The objective is makespan minimization. Preemption of tasks is not allowed. For open and flow-shop problems with three stages, complete classifications into polynomial solvable and NP-hard problems are given. These classifications depend on the compatibility structures of the problems. Furthermore, results for open-shop problems with unit processing times are derived. Finally, it is shown that most of the special cases of the job-shop problem which are polynomially solvable remain polynomially solvable in the multiprocessor task situation.Supported by the Deutsche Forschungsgemeinschaft, Project JoPTAG.     

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

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

Single-machine group scheduling with general deterioration and learning effects

In this paper we consider single-machine group scheduling problems with effects of learning and deterioration at the same time. By effects of learning and deterioration, we mean that the group setup times are general linear functions of their starting times and the jobs in the same group have general position-dependent and time-dependent learning effects. The objective of scheduling problems is to minimize the makespan and the sum of completion times, respectively. We show that the problems remain solvable in polynomial time under the proposed model.     

在成组技术下带恶化和学习效应的单机排序问题

本文研究了带依靠时间的恶化效应和依靠位置的学习效应的成组排序问题。模型中,组安装时间是开始安装时间的线性函数,工件的加工时间带恶化和学习效应,目标函数分别为最小化时间表长问题和最小化总完工时间问题。基于对问题的分析,给出了多项式算法。