有使用限制的二台机器流水作业问题

本文研究了机器有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间,工件加工可以被机器的不可用时间段中断。我们讨论了两台机器上均有使用限制离线问题的可近似情形,并给出了性能比为3/2的近似算法。同时我们还考虑了在第二台机器上存在一个不可用时间段情况下的半在线问题,给出了一个竞争比为3/2的半在线算法。     

Two-Machine Flow Shop Scheduling with Nonregular Criteria

We consider a two-machine flow shop problem with a common due date where the objective is to minimize the sum of functions which penalize early as well as tardy completion of jobs. Since the problem is NP-hard in the strong sense, we investigate some general properties of optimal schedules for the problem, we develop lower and upper bounds, derive dominance criteria, and propose an enumerative algorithm for finding an optimal schedule. The performance of the proposed algorithm together with the influence of the individual components is thoroughly discussed.     

安装、加工和拆卸时间分离的两台机器混合作业问题

混合作业是经典的自由作业和异序作业的一种综合,其中一些工件可以按任意的机器顺序进行处理,而另一些工件必须遵守预先指定的机器顺序.本文研究安装、加工和拆卸时间分离的两台机器混合作业排序问题,该问题已经被知道是强NP困难的,本文把流水作业中的同顺序作业概念推广到混合作业,并得到这个混合作业问题在同顺序意义下的最优解,这个解对于一般情形是3/2近似解,但对于一些有意义的特殊情形是整体最优的.     

A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

We give a $(2+?)$-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture on the approximability of this scheduling problem (Skutella, 2016).     

流水车间作业排序问题蚁群算法研究

本文运用蚁群算法研究辨台处理机、目标函数为时间表长最小的同顺序排列流水车间作业排序问题，设计出解决该问题的算法步骤与流程。最后，通过仿真比较该算法与解决该问题的其它启发式算法性能，计算效果比较满意。     

基于蝙蝠退火算法的无等待流水线调度问题研究

无等待流水线调度问题(no-wait flow shop scheduling problem,NWFSP)是一类比较重要的复杂生产调度问题,并已经被证明是典型的NP问题.蝙蝠算法(Bat algorithm,BA)是一种较新颖的群体智能算法.本文针对蝙蝠算法在求解无等待流水线调度问题上的不足,提出一种蝙蝠退火算法,它通过采用ROV的编码方式以实现离散问题的连续编码,同时为了避免算法早熟现象引入了模拟退火算法.算法采用基于NEH的局部搜索规则,在很大程度上提高了算法的性能.利用标准Car问题和Rec问题算例进行仿真实验,结果表明了改进算法的可行性和有效性.     

柔性Flow shop最小和调度问题的启发式研究

本文研究有n个作业须在s个处理机中心进行加工，处理机中心i由l1个同速机组成的非抢占式柔性nowshop加权完成时间调度问题。每个作业有同样的加工路径通过每个处理机中心，但只需在处理机中心的任一台机器上加工处理，作业到达时间相同。目的是确定一个作业在每个处理机中心机器上的可行调度序列，使所有作业在最后处理机中心的加权完成时间总和最小化。在作业处理时间和权重有界、每个作业的工序处理时间为同分布的随机变量、不同作业的处理时间相互独立时，通过分组这种机器环境，我们证明该问题在作业数趋于无究时，一个基于加权最短处理时间的启发式算法是渐近最优的。     

加权完工时间和的调整时间可分离Flow shop排序问题

讨论了2台机器调整时间可分离的FlowShop排序问题,目标函数为极小化加权完工时间和.给出了对于一种特殊情况,问题存在多项式最优算法的充分条件.接着又给出了求解该问题的一个分枝定界法.     

Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates

We present a $(2+2ln2+\epsilon )$-approximation algorithm for the classical nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on identical parallel machines subject to release dates and precedence constraints, improving upon the previously best known 4-approximation algorithm from 1998. The result carries over to the more general problem with precedence delays and generalizes a recent result by Li (2017) for the problem without release dates or delays.     

求解零等待流水车间调度问题的改进蝙蝠算法

针对零等待流水车间调度问题特性,设计了一种蝙蝠算法进行求解.算法模拟蝙蝠捕食搜索行为进行寻优,利用基于最小位置值规则的随机键编码方式来表示问题解,采用基于NEH方法的局部搜索策略和随机交换、插入、逆序操作的变邻域搜索策略来提高局部优化性能,进一步根据Metropolis概率准则接受劣解来避免早熟.通过典型算例对所提算法进行仿真测试并与粒子群算法和RAJ启发式算法进行对比,结果表明所设计算法求解零等待流水车间调度问题的有效性和优越性,是求解流水车间生产调度问题的一种有效工具.     

An Algorithm for the Job Shop Scheduling Problem based on Global Equilibrium Search Techniques

The job shop scheduling problem is considered, and an algorithm based on the global equilibrium search method is proposed for its solution. Computational experiments using well-known benchmark problems are presented. Several new upper bounds for these problems are obtained.Research partially supported by NSF and AirForce grants.     

具有优势机器的无空闲同顺序Flow Shop排序问题

本文讨论具有优势机器的无空闲同顺序Flow Shop排序问题的两种特殊情况,第一种情况是具有增减系列优势机器,第二种情况是具有减增系列优势机器．对于目标函数是最大完工时间,加权完工时间和,最大延误和延误工件数等问题,给出了求解最优排序的有效方法．     

New neighborhood structures for the Double Traveling Salesman Problem with Multiple Stacks

The changing requirements in transportation and logistics have recently induced the appearance of new vehicle routing problems that include complex constraints as precedence or loading constraints. One of these problems that have appeared during the last few years is the Double Traveling Salesman Problem with Multiple Stacks (DTSPMS), a vehicle routing problem in which some pickups and deliveries must be performed in two independent networks, verifying some precedence and loading constraints imposed on the vehicle. In this paper, four new neighborhood structures for the DTSPMS based on reinsertion and permutation of orders to modify both the routes and the loading planning of the solutions are introduced and described in detail. They can be used in combination with any metaheuristic using local search as a subprocedure, guiding the search to unexplored zones of the solution space. Some computational results obtained using all proposed neighborhood structures are presented, providing good quality solutions for real sized instances.      

混合FlowShop环境下的提前／滞后调度问题的遗传算法

讨论了混合Flow Shop环境下的提前/滞后调度问题,这是一个NP-难题。为此,首先给出了问题的数学模型,然后构造了一个有效的遗传算法。最后给出了实验结果和结论。     

Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay

We consider the makespan minimization for a unit execution time task sequencing problem with a bipartite precedence delays graph and a positive precedence delay d. We prove that the associated decision problem is strongly NP-complete and we provide a non-trivial polynomial sub-case. We also give an approximation algorithm with ratio .     

APPOXIMATION ALGORITHM FOR MAX—BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION

Using outward rotations,we obtain an approximation algorithm for Max-Bisection problem,i.e.,Partitioning the vertices of an unirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges.In many interesting cases,the algorithm performs better than the algorithms of Ye and of Halperin and Zwick .The main tool used to obtain this result is semidefinite programming.     

机器具有优势关系下的工件加工时间可控的流水作业排序问题

本文主要研究机器具有优势关系下的工件加工时间可控的流水作业排序问题.我们主要对以下两种情形进行了讨论:工件加工时间为线性恶化和线性学习.对于每一种加工模型,我们分别研究了几类不同的优势机器,并且对每种情况均给出了多项式时间算法.     

Approximation algorithms for UET scheduling problems with exact delays

In this paper we consider coupled-task single-machine and two-machine flow shop scheduling problems with exact delays, unit processing times, and the makespan as an objective function. The main results of the paper are fast 7/4- and 3/2-approximation algorithms for solving the single- and two-machine problems, respectively.     

Makespan minimization in open shops: A polynomial time approximation scheme

In this paper, we demonstrate the existence of a polynomial time approximation scheme for makespan minimization in the open shop scheduling problem with an arbitrary fixed numberm of machines. For the variant of the problem where the number of machines is part of the input, it is known that the existence of an approximation scheme would implyP = NP. Hence, our result draws a precise separating line between approximable cases (i.e., withm fixed) and non-approximable cases (i.e., withm part of the input) of this shop problem. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by the DIMANET/PECO Program of the European Union.Supported by a research fellowship of the Euler Institute for Discrete Mathematics and its Applications. This research was done while Gerhard Woeginger was with the Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, NL-5600 MB Eindhoven, The Netherlands.     

A New Heuristic Method for the Permutation Flow Shop Scheduling Problem

A new heuristic method for the permutation flow shop scheduling problem is presented and compared with two other heuristics named NEH and SPIRIT. The new heuristic method is based on a property of the scheduling problem that provides an upper bound on the idle time of the last machine between any two adjacent jobs regardless of their position in the sequence of jobs. The results from computational experience have shown that the new heuristic outperforms, in solution quality, all others for problems having up to 50 jobs and 30 machines.