成组加工中带可分配工期的最大延误问题

研究成组加工中带可分配工期的最大延误问题的排序与工期分配,对于成组加工中带可分配工期的最大延误问题的不同模型,或给出其最优序．或证明其是NP-难问题．     

延误工件个数与最大加工时间压缩比例之和的可控排序

研究工件加工时间可控的排序问题，讨论的目标函数是延误工件个数与最大加工时间压缩比例之和，证明这一问题是多项式时间可解的。     

成组加工中带可分配工期的误工任务数问题

本文研究了成组加工时带可分配工期的误工任务数问题的排序与工期分配.对于成组加工中带可分配工期的误工任务数问题的不同模型,或给出其最优序,或证明了其是NP-难问题.     

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

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

最小化提前/延误赋权工件数及时窗惩罚的排序问题

研究赋权提前/延误工件数的公共时窗单机排序问题,时窗的位置和大小待定且由惩罚费用衡量.首先给出最优排序的一些性质,进而提出一个多项式时间算法以最小化这些费用的和.     

分类数很大时的成组排序问题

成组排序具有深刻的实际应用背景,是近年来国外研究得较多的一个热点.已有的某些动态规划算法的复杂性随分类数的增长呈指数型增长趋势,本文用“归并”和解不超过四个新的子问题的方法把分类数较大时的问题转化为分类数较小时的相应问题,简化了问题的求解.     

分支定界法求解最小带权误工工件数排序

设有n个工件J_1,J_2,…,J_n要在一台机器上加工。已知工件J_i的工时(加工时间)是Pi,工期(预定交付期限)是d_i,权(工件误工时,即在工期之后完工所造成的损失)是w_i.记s=(s(1),…,s(n))为1,2,…,n的一个排列(置换),并记S为1,2,…,n所有排列的全体。如何在S中寻找一个排列s,使在按照次序J_(s(1)),J_(s(2))…,J_(s(n))进行加     

具有退化工件和工期窗口安排的排序问题

针对具有退化工件的排序模型,考虑了单机排序和两台机器流水作业的工期窗口安排问题,在这一模型中,工件的加工时间是与其开工时间和退化率有关的一个线性函数。目标是找到一个最优排序和确定工期窗口的开始时间及大小以便最小化所有工件的费用函数,费用函数由四部分组成:提前、延误、工期窗口开始时间和工期窗口大小。对所研究的单机问题,详细地讨论了符合现实情况的几种类型问题,并得到了问题的最优解;对两台机器流水作业问题,给出了多项式算法。     

带固定工件的单机排序问题1｜FB, rj,pmtn｜∑j Uj的多项式算法

研究具有若干固定工件和自由工件,其中固定工件必须在指定时间窗内加工,而自由工件具有不同交工的时间,并且其加工可以中断的单机排序问题,其目标是极小化工件的误工数.该问题可以表示为1|FB,rj,pmtn|∑j Uj.首先讨论了问题的几个重要性质,以此为基础建立了求解该问题的动态规划算法,其时间复杂度为O(n4+m log m),其中m和n分别是固定工件数和自由工件数.     

最小化加权误工工件数的多代理平行分批排序

考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,并且当工件具有单位权时,可在多项式时间解决.进一步证明当代理数固定时,两个问题都有FPTAS算法.     

极小化最大完工时间的单机分批加工问题

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b相似文献   

Minimizing Weighted Number of Early and Tardy Jobs with a Common Due Window Involving Location Penalty

This paper studies a single machine scheduling problem to minimize the weighted number of early and tardy jobs with a common due window. There are n non-preemptive and simultaneously available jobs. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. The window size is a given parameter but the window location is a decision variable. The objective of the problem is to find a schedule that minimizes the weighted number of early and tardy jobs and the location penalty. We show that the problem is NP-complete in the ordinary sense and develop a dynamic programming based pseudo-polynomial algorithm. We conduct computational experiments, the results of which show that the performance of the dynamic algorithm is very good in terms of memory requirement and CPU time. We also provide polynomial time algorithms for two special cases.     

A Branch and Bound Algorithm to Minimize the Total Weighed Number of Tardy Jobs and Delivery Costs

This paper addresses the production and delivery scheduling integration problem; a manufacturer receives ₋ orders from one customer while the orders need to be processed on one or two machines and be sent to the customer in batches. Sending several jobs in batches will reduce the transportation cost but it may increase the number of tardy jobs. The objective is to minimize the sum of the total weighted number of tardy jobs and the delivery costs. The structural properties of the problem for a single machine and special cases of the two-machine flow shop problem are investigated and used to set up a new branch and bound algorithm. A heuristic algorithm for upper bound calculation and two approaches for lower bound calculation are also introduced. Results of computational tests show significant improvement over an existing dynamic programming method.     

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

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

含有批处理机的三机流水作业加工总长问题在某些情形下的强NP困难性

本文研究含有批处理机的三台机器流水作业加工总长问题在某些情形下的计算复杂性。在批处理机上同时加工的工件组成一个工件批，一个工件批的所有工件同时开始、同时结束。当批处理机的容量有限时，我们证明了下列情形为强NP困难的：第一台机器是批处理机、其余两台机器是单机；第二台机器是单机、其余两台机器是批处理机；第三台机器是批处理机、其余两台机器是单机。     

加工时间是开工时间线性分段函数的单机总误工问题

研究工件加工时间是开工时间的线性分段函数的单机排序问题,其中工件的加工时间是开工时间的线性增加函数,但是有一个上界,在时刻T(T是已知常数)以后开始加工的工件,其加工时间不再因开工时间的推迟而增大,优化的目标是极小化总误工工件数.当工件的工期与加工时间满足某种一致性关系的时候,不管工件的加工时间是开工时间的简单线性分段函数,还是其基本加工时间是与恶化率有关的分段线性函数,证明这两种情况都是多项式时间可解的.