A Branch-and-Bound Algorithm to Minimize the Makespan in a Flowshop with Blocking

This work addresses the minimization of the makespan criterion for the flowshop problem with blocking. In this environment there are no buffers between successive machines, and therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. We propose a lower bound which exploits the occurrence of blocking. A branch-and-bound algorithm that uses this lower bound is described and its efficiency is evaluated on several problems. Results of computational experiments are reported.     

极小化加权完工时间和的Flowshop问题的算法

本文讨论了极小化加权完工时间和的Flowshop问题.我们给出了一个最坏情况误差界为m的启发式算法,对于m=2的情况,如果工件具有一致权因子,即pi相似文献   

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.     

Flowshop/No-idle Scheduling to Minimize Total Elapsed Time

This paper studies four n-job, m-machine flowshop problems when processing times of jobs on various machines follow certain conditions. The objective is to obtain a sequence, which minimizes total elapsed time under no-idle constraint. Under no-idle constraint, the machines work continuously without idle-interval. We prove two theorems. We introduce simple algorithms without using branch and bound technique. Numerical examples are also given to demonstrate the algorithms.     

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.     

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

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

Scheduling Three-Operation Jobs in a Two-Machine Flow Shop to Minimize Makespan

This paper considers a variant of the classical problem of minimizing makespan in a two-machine flow shop. In this variant, each job has three operations, where the first operation must be performed on the first machine, the second operation can be performed on either machine but cannot be preempted, and the third operation must be performed on the second machine. The NP-hard nature of the problem motivates the design and analysis of approximation algorithms. It is shown that a schedule in which the operations are sequenced arbitrarily, but without inserted machine idle time, has a worst-case performance ratio of 2. Also, an algorithm that constructs four schedules and selects the best is shown to have a worst-case performance ratio of 3/2. A polynomial time approximation scheme (PTAS) is also presented.     

A Heuristic Solution Procedure to Minimize Makespan on a Single Machine with Non-linear Cost Functions

We consider the static single-facility scheduling problem where the processing times of jobs are a nondecreasing and differentiable function of their starting (waiting) times and the objective is to minimize the total elapsed time (makespan) in which all jobs complete their processing. We give a criterion for optimality of two jobs to be scheduled next to each other, and based on this criterion we propose a heuristic algorithm to solve the problem. The effectiveness of the algorithm is empirically evaluated for quadratic and exponential cost functions. In the quadratic case it is compared with the static heuristic algorithm proposed by Gupta and Gupta.     

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 Savings Index Heuristic Algorithm for Flowshop Scheduling with Sequence Dependent Set-up Times

This paper considers the permutation flowshop scheduling problem with significant sequence dependent set-up times and develops a savings index heuristic algorithm to find an approximately minimum makespan schedule. The proposed algorithm determines the savings in time associated with a particular sequence and selects the sequence with the maximum time savings as the best heuristic solution. Computational experience indicating the effectiveness and efficiency of the proposed savings index heuristic algorithm are reported and discussed.     

主次指标为最小化总完工时间和存储费用的带有准备时间的单机分批排序问题

In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. We show that this problem is strongly NP-hard. We also give an O(n2) time algorithm for the special case that all stocking costs of jobs in unit time are 1.     

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.     

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

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

A Heuristic Scheduling Algorithm

This paper describes a heuristic algorithm developed to schedule a group of individuals such that every person performs each of the different activities they desire at some point during the time-frame of the schedule and the difference between the exogenously given number of people desired at each available location-activity-period position and those allocated to these positions is minimized. The contribution of the present work is in the formulation of the problem, and the resulting ease with which good solutions to large-scale problems can be generated, rather than in the mechanics of the algorithm itself. The mathematic formulation of the scheduling problem is presented first, and subsequently, the solution strategy is elaborated. Experimental results on some reasonably large problems are also presented.     

一种新的两道工序柔性流水车间排序问题

本文针对F_2(p),h11.1|m_1=1,m_2=μ≥2|C_(max)这一问题给出了几种近似算法,并对每种近似算法进行了最坏情形分析,给出了最坏情形界.     

一种可控的两台机流水作业排序问题

在经典的两台机流水作业排序问题F_2‖C_(max)的基础上进行修改,将工件J_j在两台机上的加工时间由常数A_j和B_j改成A_j(x)=a_j+c_jx和B_j(x)=b_j-d_jx,其中x是某区间上的可控(决策)变量.排序的目标是,选择适当的x(对应相应的加工时间是A_j(x)、B_j(x))(j=1,2,…,n)及相应的工件的加工顺序σ=[σ(1),σ(2),…,σ(n)],使时间表长(即最后一个工件J_σ(n)在第二台机上的完工时间)G_(max达到最小.给出了解决问题的有效方法.     

Two-Machine Flowshop Batching and Scheduling

We consider in this paper a two-machine flowshop scheduling problem in which the first machine processes jobs individually while the second machine processes jobs in batches. The forming of each batch on the second machine incurs a constant setup time. The objective is to minimize the makespan. This problem was previously shown to be NP-hard in the ordinary sense. In this paper, we first present a strong NP-hardness result of the problem. We also identify a polynomially solvable case with either anticipatory or non-anticipatory setups. We then establish a property that an optimal solution for the special case is a lower bound for the general problem. To obtain near-optimal solutions for the general problem, we devise some heuristics. The lower bound is used to evaluate the quality of the heuristic solutions. Results of computational experiments reveal that the heuristics produce solutions with small error ratios. They also suggest that the lower bound is close to the optimal solution.     

目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法

本文研究了两台机器带柔性维修时间限制的排序问题,其中第一台机器在固定的时间内必须进行维修,而第二台机器一直可用,目标是最小化所有工件的最大完工时间。工件在加工过程中不允许中断。对于该问题,我们给出了一个性能比为的近似算法,并证明了该性能比是紧的。