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.     

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

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

基于排队论的内场维修设备数量确定方法

在内场车间维修设备配置研究中,为了科学合理地确定维修设备数量需求,运用排队论的基本方法,结合飞机内场维修工作特点,提出了基于排队论的内场维修设备数量确定方法,构建了相应的数量确定模型,结合实例验证了该方法可行有效.结果表明方法可以提高飞机基层级内场车间维修设备数量确定的准确性.     

Two-machine shop scheduling: Compromise between flexibility and makespan value

In this paper, we consider the problem of providing flexibility to solutions of two-machine shop scheduling problems. We use the concept of group-scheduling to characterize a whole set of schedules so as to provide more choice to the decision-maker at any decision point. A group-schedule is a sequence of groups of permutable operations defined on each machine where each group is such that any permutation of the operations inside the group leads to a feasible schedule. Flexibility of a solution and its makespan are often conflicting, thus we search for a compromise between a low number of groups and a small value of makespan. We resolve the complexity status of the relevant problems for the two-machine flow shop, job shop and open shop. A number of approximation algorithms are developed and their worst-case performance is analyzed. For the flow shop, an effective heuristic algorithm is proposed and the results of computational experiments are reported.     

Scheduling open shops with parallel machines

The parallel shop and the open shop are two machine environments that have received much attention in the literature of scheduling theory. A common generalization—the open shop with parallel machines—is considered in this paper. Polynomial-time algorithms are presented for obtaining minimum-length preemptive schedules for three cases. Open shops with single-operation machines of equal speed are scheduled with essentially no more difficulty than an ordinary open shop. Open shops with multiple-operation machines of equal speed are scheduled with the aid of a sequence of network flow computations. The general open shop problem with parallel machines of arbitrary speeds can be solved by linear programming, in much the same way as an optimal preemptive schedule can be found for unrelated parallel machines.     

Analysis of Job Flow-Time in a Job Shop

This paper is concerned with analytical determination of the mean and standard deviation of the job flow-time in a job shop in which the F.C.F.S. dispatching rule is in use. A hypothetical job shop is constructed to generate simulation results for comparison with the analytical results. Consistency of the results reveals the validity of the analytical model. It is also shown that the model is quite robust at a low level of shop load. So the model can be applied to analyze certain types of actual shops.     

A Model for Shop Makespans and Lead Times

A model has been constructed which enables a component manufacturing shop to be interactively defined at a V.D.U., and used to calculate the average job makespan (time taken on the shop) under a variety of assumptions relating to work content, capacity and operational procedures. A second phase of the model allows the production controller to define a scheduling technique and lead-time assignment method, and provides guidance on how the makespan should be converted to lead times (time allowed on the shop). The model uses a mixture of queueing theory and simulation. This paper principally describes the methodology, but uses of the model are briefly discussed.     

A Simulation Study of Sequencing in Batch Production

A simulation experiment is described involving the sequencing of jobs through a hypothetical batch production shop under conditions of variable shop load and route configurations for the jobs. Performance of the system is measured in a number of ways and regression models are presented for the prediction of flow time.     

A survey of scheduling problems with setup times or costs

The first comprehensive survey paper on scheduling problems with separate setup times or costs was conducted by [Allahverdi, A., Gupta, J.N.D., Aldowaisan, T., 1999. A review of scheduling research involving setup considerations. OMEGA The International Journal of Management Sciences 27, 219–239], who reviewed the literature since the mid-1960s. Since the appearance of that survey paper, there has been an increasing interest in scheduling problems with setup times (costs) with an average of more than 40 papers per year being added to the literature. The objective of this paper is to provide an extensive review of the scheduling literature on models with setup times (costs) from then to date covering more than 300 papers. Given that so many papers have appeared in a short time, there are cases where different researchers addressed the same problem independently, and sometimes by using even the same technique, e.g., genetic algorithm. Throughout the paper we identify such areas where independently developed techniques need to be compared. The paper classifies scheduling problems into those with batching and non-batching considerations, and with sequence-independent and sequence-dependent setup times. It further categorizes the literature according to shop environments, including single-machine, parallel machines, flow shop, no-wait flow shop, flexible flow shop, job shop, open shop, and others.     

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.     

Scheduling policies for a repair shop problem

In this paper, we analyze a repair shop serving several fleets of machines that fail from time to time. To reduce downtime costs, a continuous-review spare machine inventory is kept for each fleet. A spare machine, if available on stock, is installed instantaneously in place of a broken machine. When a repaired machine is returned from the repair shop, it is placed in inventory for future use if the fleet has the required number of machines operating. Since the repair shop is shared by different fleets, choosing which type of broken machine to repair is crucial to minimize downtime and holding costs. The optimal policy of this problem is difficult to characterize, and, therefore, is only formulated as a Markov Decision Process to numerically compute the optimal cost and base-stock level for each spare machine inventory. As an alternative, we propose the dynamic Myopic(R) policy, which is easy to implement, yielding costs very close to the optimal. Most of the time it outperforms the static first-come-first-served, and preemptive-resume priority policies. Additionally, via our numerical study, we demonstrate that repair shop pooling is better than reserving a repair shop for each fleet.     

Minimizing maximum completion time in a proportionate flow shop with one machine of different speed

A flow shop with identical machines is called a proportionate flow shop. In this paper, we consider the variant of the n-job, m-machine proportionate flow shop scheduling problem in which only one machine is different and job processing times are inversely proportional to machine speeds. The objective is to minimize maximum completion time. We describe some optimality conditions and show that the problem is NP-complete. We provide two heuristic procedures whose worst-case performance ratio is less than two. Extensive experiments with various sizes are conducted to show the performance of the proposed heuristics.     

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.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

Bilevel programming approach applied to the flow shop scheduling problem under fuzziness

This paper presents a fuzzy bilevel programming approach to solve the flow shop scheduling problem. The problem considered here differs from the standard form in that operators are assigned to the machines and imposing a hierarchy of two decision makers with fuzzy processing times. The shop owner considered higher level and assigns the jobs to the machines in order to minimize the flow time while the customer is the lower level and decides on a job schedule in order to minimize the makespan. In this paper, we use the concepts of tolerance membership function at each level to define a fuzzy decision model for generating optimal (satisfactory) solution for bilevel flow shop scheduling problem. A solution algorithm for solving this problem is given. Mathematics Subject Classification: 90C70, 90B36, 90C99     

The Robustness of Selected Job-shop Dispatching Rules with Respect to Load Balance and Work-flow Structure

Most of the published job-shop research has focused primarily on the identification of dispatching rules which perform well under a variety of shop conditions. Most of the research has assumed that the job shop was an open shop in the sense that a virtually unlimited number of job routeings was possible, as compared to a closed shop, which has much more standardized routeings. Also, most research has further assumed that the capacities at all machines are relatively even, and thus no permanent bottleneck exists. In this research, some of the best-known dispatching rules are studied to determine whether the rules are robust with respect to capacity balance and work-flow structure. In order to be useful in all types of job shop, a rule should perform well regardless of the balance of capacity and work-flow structure in the shop. Results indicate that most of the rules studied are not affected by either of the above factors.     

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.     

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.     

Modeling job shop scheduling with batches and setup times by timed Petri nets

Batch and setup times are two important factors in practical job shop scheduling. This paper proposes a method to model job shop scheduling problems including batches and anticipatory sequence-dependent setup times by timed Petri nets. The general modeling method is formally presented. The free choice property of the model is proved. A case study extracted from practical scheduling is given to show the feasibility of the modeling method. Comparison with some previous work shows that our model is more compact and effective in finding the best solution.     

Local search algorithms for the multiprocessor flow shop scheduling problem

The multiprocessor flow shop scheduling problem is a generalization of the ordinary flow shop scheduling problem. The problem consists of both assigning operations to machines and scheduling the operations assigned to the same machine. We review the literature on local search methods for flow shop and job shop scheduling and adapt them to the multiprocessor flow shop scheduling problem. Other local search approaches we consider are variable-depth search and simulated annealing. We show that tabu search and variable-depth search with a neighborhood originated by Nowicki and Smutnicki outperform the other algorithms.