Estimating Job Flow-Times in a Job Shop for Contractually Negotiated Due-Dates

One of the most important aspects of job shop planning is the contract negotiation process. In this process the job shop vendor must negotiate a job due-date acceptable to both job shop and the customer. Failure to obtain reasonably accurate predictions of the job completion time can result in penalties and/or lost future sales for the job shop. As such, estimation of job flow-times is critical to successful job shop operation. This paper presents a network modelling approach to the difficult and complex task of estimating job flow-times not previously presented in the literature. The approach is demonstrated via a case example where the system model is developed as a Q-GERT network and simulation results are obtained.     

A Rollout Metaheuristic for Job Shop Scheduling Problems

In this paper we deal with solution algorithms for a general formulation of the job shop problem, called alternative graph. We study in particular the job shop scheduling problem with blocking and/or no-wait constraints. Most of the key properties developed for solving the job shop problem with infinite capacity buffer do not hold in the more general alternative graph model. In this paper we report on an extensive study on the applicability of a metaheuristic approach, called rollout or pilot method. Its basic idea is a look-ahead strategy, guided by one or more subheuristics, called pilot heuristics. Our results indicate that this method is competitive and very promising for solving complex scheduling problems.     

A Model for Predicting the Performance of a Job Shop

This paper is concerned with presenting a method of modelling a job shop based on queueing theory. The model is very flexible and may be used to explore the relationships between the resources available in the shop (numbers and characteristics of machines, manpower levels and skills), the workload in the shop, the mode of operation of the shop (labour allocation and priority schemes) and the resulting level of congestion within the shop.A range of results is presented, based on the application of the model to a real environment, where good agreement with the observed performance was obtained.     

Giffler and Thompson's Algorithm for Job Shop Scheduling is Still Good for Flexible Manufacturing Systems

In this paper it is shown, through computational results, that a schedule generation algorithm originally designed for the traditional job shop model can still provide good results, in terms of CPU time and solution accuracy, when applied to the flexible manufacturing system (FMS) model. For this, we use two algorithms, for the job shop and the FMS, that generate all active schedules. Both algorithms are improved, by adding to them a branch-and-bound approach, and their behaviour is compared.     

Constraint-Based Job Shop Scheduling with IILOG SCHEDULER

We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and we show how such results can be used within a constraint-based approach. An empirical performance analysis shows that the algorithm we developed performs well. Finally, taking the job shop scheduling problem as a start point, we discuss how constraint-based scheduling can be used to solve more general scheduling problems.     

Optimal Configurations of General Job Shops

In this paper we study the problem of minimizing the expected number of jobs in a single class general open queueing network model of a job shop. This problem was originally posed by Buzacott and Shanthikumar [2] and solved by them for a special case. We extend their work in this paper. We derive feasibility conditions that simplify the analysis of the problem. We show that the optimal configuration can be completely characterized when both the utilizations of the machine centers are high and there are a large number of servers at each machine center. We also derive conditions under which the optimization problem reduces to solving a concave or a convex program and provide conditions under which the uniform flow line and the symmetric job shop (or variants of these) are optimal configurations for the job shop.     

No-wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems

This paper deals with the no-wait job shop problem with a makespan objective. We present some new theoretical properties on the complexity of subproblems associated with a well-known decomposition approach. Justified by the complexity results, we implement a fast tabu search algorithm for the problem at hand. It is extensively tested on known benchmark instances and compares favorably to the best existing algorithms for the no-wait job shop as well as the no-wait flow shop.     

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.     

基于遗传算法的多目标柔性工作车间调度问题求解

本文针对柔性工作车间调度问题给出了一个有意义的综合目标尽可能缩短制造周期的同时尽可能的减少机器负荷。由于传统遗传算法在多目标柔性工作车间调度问题上的局限性，我们提出了一种改进遗传算法：首先，我们给出了针对综合目标的工序调度算法获得初始集合；接着，针对柔性工作车间调度问题的特点，我们在常用的基于工序顺序的编码方法上融入了基于机器分配的编码方法，并据此设计了相应的交叉变异操作；最后借鉴了物种进化现象中的环境迁移思想设计了解决多目标优化问题的迁移操作。实验结果表明，改进的遗传算法在多目标柔性工作车间调度问题的解决上要优于传统遗传算法。     

Hybrid Rollout Approaches for the Job Shop Scheduling Problem

In this paper, we focus on heuristic approaches for solving the deterministic job shop scheduling problem. More specifically, a new priority dispatch rule and hybrid rollout algorithms are developed for approaching the problem under consideration. The proposed solution algorithms are tested on a set of instances taken from the literature and compared with other methods. The computational results validate the effectiveness of the developed solution approaches and show that the proposed rollout algorithms are competitive with respect to several state-of-art heuristics for solving the job shop scheduling problem. The author thanks Dr. Marco Mancini and Dr. Alessandro Tarasio for valuable suggestions about computational issues.     

A new neighborhood and tabu search for the Blocking Job Shop

The Blocking Job Shop is a version of the job shop scheduling problem with no intermediate buffers, where a job has to wait on a machine until being processed on the next machine. We study a generalization of this problem which takes into account transfer operations between machines and sequence-dependent setup times. After formulating the problem in a generalized disjunctive graph, we develop a neighborhood for local search. In contrast to the classical job shop, there is no easy mechanism for generating feasible neighbor solutions. We establish two structural properties of the underlying disjunctive graph, the concept of closures and a key result on short cycles, which enable us to construct feasible neighbors by exchanging critical arcs together with some other arcs. Based on this neighborhood, we devise a tabu search algorithm and report on extensive computational experience, showing that our solutions improve most of the benchmark results found in the literature.     

Introducing Undergraduates to the Spirit of OR whilst Imparting Substantive Skills

This paper presents analytical expressions for the moments of job flow time in a job shop by computing the moments of a random number of random variables assuming that the job shop satisfies the sufficient conditions of the Jackson decomposition principle. The mathematical equivalence of the proposed method to the Laplace transform method is shown and then demonstrated in a simple example. Then, expressions for the moments of job flow time in more realistic (and more complex) job shop settings are derived by computing the moments of a random number of random variables, provided that expressions for the moments of job flow time are available for the corresponding single stage shop. It is shown that the analytical expressions developed are exact as long as the assumptions of the Jackson decomposition principle hold. Any violation of these assumptions makes the derived expressions approximations, and their accuracy should be tested by simulation.     

考虑机器能耗的绿色作业车间调度问题

针对传统作业车间调度,在保证交货期的前提下,以机器能耗最小为目标研究带有关机/重启策略的绿色车间调度问题。首先建立数学规划模型,然后在遗传算法的框架下,根据问题特点提出了一种局部调整的解码方式,在排产时进行工序的移动并确定其开始加工时刻。最后进行小规模算例运算,验证数学规划模型的有效性,再利用算例对基于局部调整解码和顺序解码的遗传算法进行对比测试,结果表明提出的局部调整解码可以在降低机器能耗的同时提高求解效率。     

遗传算法对车间作业调度的研究

应用遗传算法对车间作业调度问题进行研究,针对ＪＳＳＰ的具体特性,文中提出变异函数和二次编码的思想,获得较好的仿真结果。     

A mathematical model of a flexible manufacturing system with limited in-process inventory

This paper describes a computationally simple, asymptotic model of a flexible job shop, especially designed for estimating the influence of limited in-process inventory level on the production rate. Its main features make it very similar to the one by Solberg. While Solberg's model consists of a closed queuing network, we propose an open queuing network with a limited amount of inprocess customers; a single customer class is assumed, the various actual processing routes being accounted for by routing probabilities. For such a queuing network, the product form of state probabilities is valid, and the normalization constant can be very simply obtained by a convolution algorithm, close to the one used by Solberg. Various performance indices are calculated, regarding the job shop behaviour over a long period of time. Comparison of analytical results of the model and simulation results are provided in order to estimate the amount of error introduced by assuming exponentially distributed processing times and Poisson inputs in the mathematical representation. Simulations were carried out in FORTRAN-based SLAM language.     

Improved Bounds for Acyclic Job Shop Scheduling

In acyclic job shop scheduling problems there are n jobs and m machines. Each job is composed of a sequence of operations to be performed on different machines. A legal schedule is one in which within each job, operations are carried out in order, and each machine performs at most one operation in any unit of time. If D denotes the length of the longest job, and C denotes the number of time units requested by all jobs on the most loaded machine, then clearly lb = max[C,D] is a lower bound on the length of the shortest legal schedule. A celebrated result of Leighton, Maggs, and Rao shows that if all operations are of unit length, then there always is a legal schedule of length O(lb), independent of n and m. For the case that operations may have different lengths, Shmoys, Stein and Wein showed that there always is a legal schedule of length , where the notation is used to suppress terms. We improve the upper bound to . We also show that our new upper bound is essentially best possible, by proving the existence of instances of acyclic job shop scheduling for which the shortest legal schedule is of length . This resolves (negatively) a known open problem of whether the linear upper bound of Leighton, Maggs, and Rao applies to arbitrary job shop scheduling instances (without the restriction to acyclicity and unit length operations). Received June 30, 1998 RID="*" ID="*" Incumbent of the Joseph and Celia Reskin Career Development Chair RID="†" ID="†" Research was done while staying at the Weizmann Institute, supported by a scholarship from the Minerva foundation.     

一种多策略引导的电磁场优化算法求解作业车间调度问题

电磁场优化算法是目前一种比较新颖的群智能优化算法,其利用不同极性电磁场所产生的引斥力,使电磁粒子朝最优解移动。针对标准电磁场优化算法在求解作业车间调度问题时容易陷入局部极值点、收敛精度差等问题,提出了一种多策略引导的电磁场优化算法。算法中粒子受到三种不同来源的引斥力,在迭代过程中通过计算每种移动策略的临代电差、累计电差和综合电差来决定粒子的引导方式,并通过概率变异算法来避免陷入局部最优解。通过作业车间调度问题FT、LA系列测试实例仿真实验,对新算法与其他算法的测试结果进行比较分析,研究表明该算法具有更高的求解精度和更快的计算速度。     

车间作业调度的可行化判定及不可行解的纠正

生产调度过程中出现不可行解是调度研究经常遇到的问题之一.提出了对JSP调度方案进行可行化判定和纠正不可行解的可行算子,算子包括了基于有向图拓扑排序原理对车间作业调度方案进行可行判定的方法和将不可行解纠正为可行解的算法.证明了该纠正算法总能成功,并对算子的功能进行了拓展使之还可应用于不完备调度.最后讨论了可行算子的特点、时间效率和应用前景.     

Job Release: Part of a Hierarchical System to Manage Manufacturing Lead Times in Make-to-order Companies

A methodology to manage manufacturing lead times is currently being developed by the authors. The system is specifically designed to address the needs of small- to medium-sized make-to-order companies. It involves a hierarchical production planning system in which integration between the production and marketing functions is facilitated. Considerations of capacity are included at both of the decision levels addressed—the customer enquiry stage and the job release stage. This paper describes the job release stage, showing how it is linked with the higher-level stage by controlling a hierarchy of backlog lengths. At the job release stage the released backlog length for each work centre is maintained between predetermined minimum and maximum levels. It is shown that shop floor throughput times—an important part of manufacturing lead times—can be controlled by controlling released backlog lengths. The releasing mechanism is described and it is argued that there can be many benefits of job release—including reduced shop congestion, lower work-in-progress and lower costs.     

Job routing and operations scheduling: a network-based virtual cell formation approach

Virtual cellular manufacturing inherits the benefits of traditional cellular manufacturing and maintains the responsiveness to the changing market and routing flexibility of a job shop by integrating machine-grouping, shop layout design and intercellular flow handling. The primary goal of virtual cell formation is to minimize the throughput time of a given job. This paper proposes a method for virtual cell formation by adopting the double-sweep algorithm for the k-shortest path problem, and a heuristic is devised to schedule the virtual cells for the multiple job orders. Results generated from this method include not only the optimal candidates of the virtual cell with the shortest throughput time with sub-optimal alternative route(s) and throughput time(s) as the alternative candidates in case some resources are restricted or are not available. The procedure of virtual cell creation and scheduling is illustrated explicitly with examples. Since most of the scheduling problems are NP-hard and virtual cell scheduling is even more complex due to the bottleneck machines that are demanded by jobs at other cells. For multiplicity of possible virtual cell candidates, in addition to the precedence and resource constraints, heuristic solutions are found to be reasonable.