具有特殊工件的平行机在线排序问题

本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M1.我们提供了竞争比为(2m2-2m 1)/(m2-m 1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的竞争比为13/7≈1.857,并且提供了竞争比的下界(1 (平方根33))14≈1.686.     

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.     

Randomized On-Line Scheduling Similar Jobs to Minimize Makespan on Two Identical Processors

In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound.     

A No-Wait Flowshop Scheduling Heuristic to Minimize Makespan

The scheduling problem in the no-wait or constrained flowshop, with the makespan objective, is considered in this article. A simple heuristic algorithm is proposed on the basis of heuristic preference relations and job insertion. When evaluated over a large number of problems of various sizes, the solutions given by the proposed heuristic are found to be fairly accurate and much superior to those given by the two existing heuristics.     

Scheduling Reclaimer Operations in the Stockyard to Minimize Makespan

This paper considers a reclaimer scheduling problem in which one has to collect bulk material from stockpiles in the quay in such a way that the time used is minimized. When reclaimers are allowed to work on the same stockpile simultaneously, a fully polynomial time approximation scheme (FPTAS) is designed. Further, we present a 2-approximation algorithm in the case that any stockpile can be handled by only one reclaimer at a time. When the number of reclaimers is two, we give a 3/2-approximation algorithm. Numerical experiments show that the algorithms perform much better than our worst case analysis guarantees.     

Scheduling Malleable Tasks on Parallel Processors to Minimize the Makespan

The problem of optimal scheduling n tasks in a parallel processor system is studied. The tasks are malleable, i.e., a task may be executed by several processors simultaneously and the processing speed of a task is a nonlinear function of the number of processors allocated to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the number of processors is sufficient to process all the tasks simultaneously, i.e. n≤m. The objective is to find a task schedule and a processor allocation such that the overall task completion time, i.e. the makespan, is minimized. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. An O(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave and the number of tasks is a constant, the problem can be solved in polynomial time. A relaxed problem, in which the number of processors allocated to each task is not required to be integer, can be solved in O(nmax {m,nlog ² m}) time. It is proved that the minimum makespan values for the original and relaxed problems coincide. For n=2 or n=3, an optimal solution for the relaxed problem can be converted into an optimal solution for the original problem in a constant time.     

具有周期维护最小化时间表长的两台平行机调度问题(英文)

本文讨论了具有周期维护的两台平行机调度问题,目标函数为最小化时间表长.设T为维护周期,t为每次对机器维护需要的时间,当t≤T/3时,本文证明了对于该问题由LPT算法得到的最坏误差界为2.     

依赖机器的两台机自由作业排序问题

文章研究加工时间仅依赖于机器的两台机自由作业排序问题 O2 | pij = pi, p2 < p1 < 2p2, Non-Idle | ΣCj。项思明和唐国春(1998)证明了可将该问题转化成指派问题。俞文ci 和应刚(1998)给出了这一问题的显式解,并用较长的篇幅证明其显式解的正确性;他们还举例说明所给出的显式最优排序并不排除其他形式的最优解的存在;但他们未说明所给出的显式解何时才是唯一最优解。本文将给出问题 O2 | pij = pi, p2 < p1 < 2p2, Non-Idle | ΣCj的显式解的直观的最优性证明,并讨论问题显式解何时是唯一的最优解。     

On Flow Shop Scheduling with Release and Due Dates to Minimize Maximum Lateness

A branch-and-bound algorithm for a two-machine scheduling problem by Grabowski is generalized to the case of an arbitrary number of machines. The lower bounds are obtained by the relaxation of the capacity constraints on the machines. An approach to strengthen these lower bounds is developed. Computational experience with 6-, 10-, 15-, 20-, 30-, 40-, 50-job problems is presented.     

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

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

加工时间和尺寸成正比单机排序和工件运输的最小化最大完工时间问题

在单机排序和工件运输的最小化最大完工时间问题中,工件首先在一台机器上加工,然后被一辆有容量限制的汽车运送到一个顾客．当工件的加工时间和尺寸无关时, Chang和Lee已经证明该问题是强NP困难的．他们也给出了一个启发式算法,它的最差执行比为5／3,并且这个界是紧的．本文考虑工件的加工时间和尺寸成正比的情形,证明了Chang和Lee的算法有更好的最差执行比53／35,并提供了一个新的启发式算法,它的最差执行比是3／2,并且这个界是最好的．     

混沌神经网络优化算法用于求解无等待流水调度问题的最小最大完工时间

利用李小平等提出的相邻工件加工结束时间差矩阵,将求解无等待流水调度问题的最小最大完工时间(Makespan)问题映射为TSP问题,构造对应的能量函数,进而得到随机混沌神经网络(SCSA)算法.实验结果证明该混沌神经网络优化算法优于RAJ算法和GANRAJ算法.     

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

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

Approximations for the Two-Machine Cross-Docking Flow Shop Problem

We consider in this article the Two-Machine Cross-Docking Flow Shop Problem, which is a special case of scheduling with typed tasks, where we have two types of tasks and one machine per type. Precedence constraints exist between tasks, but only from a task of the first type to a task of the second type. The precedence relation is thus a directed bipartite graph. Minimizing the makespan is strongly NP-hard even with unit processing times, but any greedy method yields a 2-approximation solution. In this paper, we are interested in establishing new approximability results for this problem. More specifically, we investigate three directions: list scheduling algorithms based on the relaxation of the resources, the decomposition of the problem according to the connected components of the precedence graph, and finally the search of the induced balanced subgraph with a bounded degree.     

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

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

Scheduling Equal Processing Time Jobs to Minimize the Weighted Number of Late Jobs

We prove that the problem P ∣ p _i = p, pmtn ∣ ∑w _i U _i is unary NP-hard although the corresponding nonpreemptive problem can be solved in O(n log n) time, where n is the number of jobs. This contrasts the fact that usually preemptive problems are not harder than their nonpreemptive counterparts.     

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

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

Bicriteria Scheduling on a Series-Batching Machine to Minimize Makespan and Total Weighted Completion Time with Equal Length Job

It is known that the problem of minimizing total weighted completion time on a series-batching machine is NP-hard. We consider a series-batching bicriteria scheduling problem of minimizing makespan and total weighted completion time with equal length job simultaneously. A batching machine can handle up to b jobs in a batch, where b is called the batch capacity of the machine. We study the unbounded model with b≥n, where n denotes the number of jobs. A dynamic programming algorithm is proposed to solve the unbounded model, which can find all Pareto optimal schedules in O（n3） time.     

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

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

Optimal Scheduling of a Two-stage Hybrid Flow Shop

We present an exact branch-and-bound algorithm for the two-stage hybrid flow shop problem with multiple identical machines in each stage. The objective is to schedule a set of jobs so as to minimize the makespan. This is the first exact procedure which has been specifically designed for this strongly -hard problem. Among other features, our algorithm is based on the exact solution of identical parallel machine scheduling problems with heads and tails. We report the results of extensive computational experiments on instances which show that the proposed algorithm solves large-scale instances in moderate CPU time.