Complexity of shop-scheduling problems with fixed number of jobs: a survey

The paper surveys the complexity results for job shop, flow shop, open shop and mixed shop scheduling problems when the number n of jobs is fixed while the number r of operations per job is not restricted. In such cases, the asymptotical complexity of scheduling algorithms depends on the number m of machines for a flow shop and an open shop problem, and on the numbers m and r for a job shop problem. It is shown that almost all shop-scheduling problems with two jobs can be solved in polynomial time for any regular criterion, while those with three jobs are NP-hard. The only exceptions are the two-job, m-machine mixed shop problem without operation preemptions (which is NP-hard for any non-trivial regular criterion) and the n-job, m-machine open shop problem with allowed operation preemptions (which is polynomially solvable for minimizing makespan).     

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

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

Routing open shop and flow shop scheduling problems

We consider a generalization of the classical open shop and flow shop scheduling problems where the jobs are located at the vertices of an undirected graph and the machines, initially located at the same vertex, have to travel along the graph to process the jobs. The objective is to minimize the makespan. In the tour-version the makespan means the time by which each machine has processed all jobs and returned to the initial location. While in the path-version the makespan represents the maximum completion time of the jobs. We present improved approximation algorithms for various cases of the open shop problem on a general graph, and the tour-version of the two-machine flow shop problem on a tree. Also, we prove that both versions of the latter problem are NP-hard, which answers an open question posed in the literature.     

Optimal policies in stochastic shop scheduling

In this paper a survey is presented of some of the recent results in stochastic open shop, flow shop and job shop scheduling. The distributions of the processing times of the jobs are known in advance, but the actual processing times are not known in advance. The jobs may have due dates. Optimal preemptive and nonpreemptive policies are determined for the minimization of various objective functions, such as the expected makespan, the expected flow time and the expected number of late jobs. The effect of various degrees of dependence between the processing times of any given job on the various machines is investigated. Under given conditions bounds are obtained for the expected makespan in the different models.Partially supported by the National Science Foundation (NSF), under grant ECS-8115344 with the Georgia Institute of Technology.     

Mixed integer formulation to minimize makespan in a flow shop with batch processing machines

Batch processing machines are commonly used in wafer fabrication, kilns, and chambers used for environmental stress screening (ESS). This paper proposes two models to schedule batches of jobs on two machines in a flow shop. A set of jobs with known processing times and sizes has to be grouped, to form batches, in order to be processed on the batch processing machines. The jobs are nonidentical in size. The processing time of a batch is the longest processing time of all the jobs in that batch. Mixed integer formulations are proposed for the flow shop problem when the buffer capacity is unlimited or zero. Numerical examples are presented to demonstrate the application of our model.     

Minimizing the expected weighted number of tardy jobs in stochastic flow shops

This paper is devoted to two types of stochastic scheduling problems, one involving a single machine and the other involving a flow shop consisting of an arbitrary number of machines. In both problem types, all jobs to be processed have due dates, and the objective is to find a job sequence that minimizes the expected weighted number of tardy jobs. For the single-machine case, sufficient optimality conditions for job sequences are derived for various choices of due date and processing time distributions. For the case of a flow shop with an arbitrary number of machines and identically distributed due dates for all jobs, we prove the following intuitively appealing results: (i) when all jobs have the same processing time distributions, the expected weighted number of tardy jobs is minimized by sequencing the jobs in decreasing order of the weights, (ii) when all weights are equal, the jobs should be sequenced according to an increasing stochastic ordering of the processing time distributions.     

A Simulation Study of Due-date Assignment Rules in a Dynamic Job Shop

This paper is a report of a simulation study that investigates a dynamic approach to scheduling jobs in a multi-machine job shop. The workload information of a job is used in different forms to evaluate the shop performance based on three measures: mean job lateness, percentage of tardy jobs and lateness variance. Different combinations of due-date assignment methods and sequencing rules are compared based on specific performance criteria. The results indicate that using the cumulative distribution function of workload information can yield a better performance than using a proportional function of workload information or ignoring shop congestion information. A few situations are identified in which workload information is not critical.     

The equal allocation policy in open shop batch scheduling

We study the optimality of the very practical policy of equal allocation of jobs to batches in batch scheduling problems on an m-machine open shop. The objective is minimum makespan. We assume unit processing time jobs, machine-dependent setup times and batch availability. We show that equal allocation is optimal for a two-machine and a three-machine open shop. Although, this policy is not necessarily optimal for larger size open shops, it is shown numerically to produce very close-to-optimal schedules.     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题,目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时,两类问题在一般优先图上都是强NP-困难的,而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界,并基于许可工件之间的最大匹配设计近似算法,其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题,我们在理论上证明了算法的近似比为$2-\frac 2m$,其中$m$是机器数目。     

优先序约束的排序问题：基于最大匹配的近似算法

本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题，目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时，两类问题在一般优先图上都是强NP-困难的，而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界，并基于许可工件之间的最大匹配设计近似算法，其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题，我们在理论上证明了算法的近似比为$2-\frac 2m$，其中$m$是机器数目。     

A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines

We study the problem of minimizing the makespan in a two-stage assembly flow shop scheduling problem with uniform parallel machines. This problem is a generalization of the assembly flow shop problem with concurrent operations in the first stage and a single assembly operation in the second stage. We propose a heuristic with an absolute performance bound which becomes asymptotically optimal as the number of jobs becomes very large. We show that our results slightly improve earlier results for the simpler assembly flow shop problem (without uniform machines) and for the two-stage hybrid flow shop problem with uniform machines.     

Fuzzy job shop scheduling with lot-sizing

This paper deals with a problem of determining lot-sizes of jobs in a real-world job shop-scheduling in the presence of uncertainty. The main issue discussed in this paper is lot-sizing of jobs. A fuzzy rule-based system is developed which determines the size of lots using the following premise variables: size of the job, the static slack of the job, workload on the shop floor, and the priority of the job. Both premise and conclusion variables are modelled as linguistic variables represented by using fuzzy sets (apart from the priority of the job which is a crisp value). The determined lots’ sizes are input to a fuzzy multi-objective genetic algorithm for job shop scheduling. Imprecise jobs’ processing times and due dates are modelled by using fuzzy sets. The objectives that are used to measure the quality of the generated schedules are average weighted tardiness of jobs, the number of tardy jobs, the total setup time, the total idle time of machines and the total flow time of jobs. The developed algorithm is analysed on real-world data obtained from a printing company.     

Lead time selection and the behaviour of work flow in job shops

Few studies in job shop scheduling consider dynamic shop load and work flow issues. However, these issues are of importance to management responsible for shop floor control. This research investigates relevant internal performance measures and their relationship to external measures. As well, a new dispatching mechanism that seeks to even out the distribution of jobs in queue is investigated. Results show that a shop load balance index, which takes both shop load levels and load variability into account, has a very strong relationship to the lead times required to maintain a desired level of delivery performance. It appears that good performance based on internal measures is consistent with good performance based on external measures.     

Workforce-constrained maintenance scheduling for military aircraft fleet: a case study

The problem is related to a fleet of military aircraft with a certain flying program in which the availability of the aircraft sufficient to meet the flying program is a challenging issue. During the pre- or after-flight inspections, some component failures of the aircraft may be found. In such cases, the aircraft are sent to the repair shop to be scheduled for maintenance jobs, consisting of failure repairs or preventive maintenance tasks. The objective is to schedule the jobs in such a way that sufficient number of aircrafts is available for the next flight programs. The main resource, as well as the main constraint, in the shop is skilled-workforce. The problem is formulated as a mixed-integer mathematical programming model in which the network flow structure is used to simulate the flow of aircraft between missions, hanger and repair shop. The proposed model is solved using the classical Branch-and-Bound method and its performance is verified and analyzed in terms of a number of test problems adopted from the real data. The results empirically supported practical utility of the proposed model.     

Optimization of processing identical jobs by means of cyclic schedules

Some cyclic job shop problems with identical jobs are under study. Using dynamic programming, we propose an algorithm for solving one of these problems exactly. In the special case of a fixed number of jobs which can be processed simultaneously, we construct a fully polynomial time approximation scheme.     

Scheduling in network flow shops

We consider the general problem of static scheduling of a set of jobs in a network flow shop. In network flow shops, the scheduler not only has to sequence and schedule but also must concurrently determine the process routing of the jobs through the shop. In this paper, we establish the computational complexity of this new class of scheduling problem and propose a general purpose heuristic procedure. The performance of the heuristic is analyzed when makespan, cycle time and average flow time are the desired objectives.This research has been supported by the UCLA Academic Senate Grant #95.     

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

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

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

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

可转包两台流水作业机排序的近似算法

研究可转包的两台流水作业机排序问题, 目标是极小化最大完工时间和总外包费用之和. 首先给出最坏情况界为2的近似算法, 接着对工件满足有序化约束的情形给出最坏情况界为\frac{3}{2}的改进算法, 以上算法界均为紧界.     

Two-stage open shop scheduling with a bottleneck machine

It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P≠NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the m⩾2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4.