A comparative study of some priority dispatching rules under different shop loads

Priority dispatching rules and shop load affect job-shop performance. This paper evaluates ten different priority dispatching rules with respect to six different performance criteria under light, medium and heavy shop loads. Simulation was used as a tool to determine the rankings of the dispatching rules for a given shop load and performance criteria. A comparative study was conducted to investigate the performance of these rules. Two rules, ‘shortest processing time” and ‘least work remaining’, performed well under criteria related to the processing time. It was found that the rules that perform well in average and r.m.s. tardiness perform poorly under percentage-of-jobs-late criterion. The experimental results are conveyed with critical comments on the performance of the dispatching rules under different loading conditions of the shop.     

Time completion for various dispatching rules in job shops

This study investigates the relative priority of various job shop dispatching rules for various shop utilization levels under both deterministic and stochastic assumptions with regard to processing times. The primary criterion for evaluation is that of percentage on time completion. The results indicate that an assumption of accurately predetermining actual operation times in most cases is not likely to weaken the analysis and impact of research studies which are performed using such an assumption. Also conclusions indicate that the ranking of dispatching rules according to their effectiveness varies significantly with shop utilization levels.     

Priority dispatching rules in job shops with assembly operations and random delays

The article reports the results of an experimental investigation into priority dispatching rules for a job shop with assembly operations. A job is made up of several parts, where parts are individual entities requiring several operations in different machine centres. The study was directed towards rules which attempt to co-ordinate the completion time of parts required in the same job. This mainly involves rules that utilise job status information such as operation float, number of parts completed, and number of operations remaining on each part. Results indicate that job status information improves most of the measures of performance used.     

Evaluation of simple dispatching rules for dynamic single-machine earliness/tardiness problem

Abstract. This paper investigates the effects of four simple dispatching rules on just-in-time production related performance measures of mean and maximum absolute lateness. The rules used are modified due date (MDD), shortest processing time (SPT), earliest due date (EDD), and first in first out (FIFO). A single machine is used under three utilization levels. Due-dates are set according to total work content rule. The results indicate that each rule performs well under certain conditions. The MDD rule is the best one to minimize mean absolute lateness. The EDD and FIFO rules do well in minimizing the maximum absolute lateness. Economic interpretation of these performance measures are also discussed.     

A heuristic approach to n/ m job shop scheduling: fuzzy dynamic scheduling algorithms

n/m shop scheduling is a ‘ NP-Hard’ problem. Using conventional heuristic algorithms ( priority rules) only, it is almost impossible to achieve an optimal solution. Research has been carried out to improve the heuristic algorithms to give a near-optimal solution. This paper advocates a fuzzy logic based, dynamic scheduling algoridim aimed at achieving this goal. The concept of new membership functions is discussed in die algorithm as a link to connect several priority rules. The constraints to determine the membership function of jobs for a particular priority rule are established, and three membership functions are developed. In order to decide the weight vector of priority rules, an aggregate performance measure is suggested. The methodology for constructing the weight vector is discussed in detail. Experiments have been carried out using a simulation technique to validate the proposed scheduling algorithm.     

A comparative analysis of due date based job sequencing rules in a flow shop with multiple processors

The literature on job scheduling recognizes the importance of due date performance criteria such as mean tardiness and maximum tardiness. A number of studies test a large number of sequencing rules for these criteria in job shop and flow shop settings. The object of this present research is to examine the performance of some well-known priority rules in a flow shop with multiple processors. This study investigates the performance of ten priority rules in terms of mean and maximum tardiness. It examines the effects of problem characteristics, such as number of jobs, number of machines stages and number of parallel processors at each stage, and the performance of priority rules using regression analysis. The findings of the study suggest that the primary determinants of tardiness-based criteria are problem characteristics. In addition, both the regression analysis and the analysis of variance provide strong evidence of the strategy-effect. Finally, a detailed performance review of examined priority rules for various problem characteristics is presented.     

Simple subcontracting rules for make-to-order shops with limited subcontractor capacity: an assessment by simulation

Companies that produce a high variety of customised products often suffer from large fluctuations in demand. Subcontracting can be an important means of overcoming resulting capacity shortages during high demand periods. A set of effective subcontracting rules, for determining which jobs to subcontract and which to produce internally, has recently been presented in the literature for this type of company. But evaluations of these rules have assumed subcontractor capacity is infinite. This study examines the impact of limited subcontractor capacity on the performance of the three best-performing subcontracting rules for make-to-order companies using a simulation model of an assembly job shop. Limiting subcontractor capacity inhibits the ability of a subcontracting rule to protect the internal shop from surges in demand, which negatively affects performance. However, significant performance differences between the rules evaluated are maintained, which underlines the importance of choosing the right subcontracting rule. Further analysis reveals that a limit on the work that can be subcontracted leads to less work being subcontracted more often, which requires adequate response by management. Meanwhile, the assumption of infinite capacity results in sporadically subcontracting a large amount of work. The results have important implications for future research and practice.     

2MTO,a new mapping tool to achieve lean benefits in high-variety low-volume job shops

This paper proposes the ‘Mapping Tool for Make-To-Order companies’ (2MTO), a new approach to map, analyse and achieve lean benefits in high-variety-low-volume job shops. The focus is, mainly, on the transitional phase from push to pull, when there is a compelling need to acquire a deep understanding of the current state of the system under analysis. Sometimes, in this initial phase, a pure pull approach cannot be developed and a job shop configuration must be maintained. If so, 2MTO allows selecting a suitable hybrid Production Planning and Control system to control Work-In-Process and to limit lead times, so as to quickly achieve lean benefits, without significantly altering the original layout. 2MTO is fully explained making reference to an Italian precision mechanic company, where the application of the method led to a successful implementation of a Workload Control system.     

A comparison of dispatching rules for executing a resource-constrained project with estimated activity durations

This research examines the performance of 13 dispatching rules for executing a resource-constrained project whose estimated activity durations may differ from the actual activity durations. The dispatching rules are tested in environments characterized by three factors, namely, the order strength of the precedence relationship, the level of resource availability and the level of estimation errors in the activity durations. The results show that project environment affects only the performance differences but not the grouping of the better dispatching rules. The greatest number of successors, rank positional weight, greatest cumulative resource requirement and minimum activity slack dispatching rules consistently perform better than the other dispatching rules, unaffected by the accuracy of the estimated activity durations. This finding validates the results of many past studies in the deterministic project environment for choosing the right dispatching rule for both projects with and without well-estimated activity durations.     

Efficient composite heuristics for total flowtime minimization in permutation flow shops

In this paper, permutation flow shops with total flowtime minimization are considered. General flowtime computing (GFC) is presented to accelerate flowtime computation. A newly generated schedule is divided into an unchanged subsequence and a changed part. GFC computes total flowtime of a schedule by inheriting temporal parameters from its parent in the unchanged part and computes only those of the changed part. Iterative methods and LR (developed by Liu J, Reeves, CR. Constructive and composite heuristic solutions to theP∥Σ_Ci$P\parallel \Sigma C_i$ scheduling problem, European Journal of Operational Research 2001; 132:439–52) are evaluated and compared as solution improvement phase and index development phase. Three composite heuristics are proposed in this paper by integrating forward pair-wise exchange-restart (FPE-R) and FPE with an effective iterative method. Computational results show that the proposed three outperform the best existing three composite heuristics in effectiveness and two of them are much faster than the existing ones.     

A multi-objective particle swarm for a flow shop scheduling problem

Flow shop problems as a typical manufacturing challenge have gained wide attention in academic fields. In this paper, we consider a bi-criteria permutation flow shop scheduling problem, where weighted mean completion time and weighted mean tardiness are to be minimized simultaneously. Since a flow shop scheduling problem has been proved to be NP-hard in strong sense, an effective multi-objective particle swarm (MOPS), exploiting a new concept of the Ideal Point and a new approach to specify the superior particle's position vector in the swarm, is designed and used for finding locally Pareto-optimal frontier of the problem. To prove the efficiency of the proposed algorithm, various test problems are solved and the reliability of the proposed algorithm, based on some comparison metrics, is compared with a distinguished multi-objective genetic algorithm, i.e. SPEA-II. The computational results show that the proposed MOPS performs better than the genetic algorithm, especially for the large-sized problems.     

基于杂合遗传算法的工艺路线可变Job Shop调度研究

提出一种将遗传算法与启发式规则、模拟退火法等搜索方法结合在一起的杂合遗传算法,用于求解工艺路线可变的JobShop调度问题。通过对某双极型集成电路封装企业的JobShop调度仿真,结果表明算法是有效和可行的。     

A heuristic to minimize total flow time in permutation flow shop

In this paper, we address an n-job, m-machine permutation flow shop scheduling problem for the objective of minimizing the total flow time. We propose a modification of the best-known method of Framinan and Leisten [An efficient constructive heuristic for flowtime minimization in permutation flow shops. Omega 2003;31:311–7] for this problem. We show, through computational experimentation, that this modification significantly improves its performance while not affecting its time-complexity.     

An investigation of order release and flow time allowance policies for assembly job shops

The effects of a number of essentially different work order release and flow time allowance policies on the assembly order flow times and assembly order due date performance are investigated. Work orders within an assembly order have different routing length. The assembly order flow time is the time that elapses between the release of the first work order and the completion of the last work order of the assembly order. The timing of the release of work orders, and the distribution of the flow time allowance over the work orders in an assembly order were varied, and used systematic computer simulation to investigate the effects on performance. The results show that the best performance is obtained with simultaneous work order release, an average operation flow time allowance equal to the average operation waiting time and equalized flow time allowances per work order in an assembly order.     

A hybrid approach to sequencing jobs using heuristic rules and neural networks

A hybrid approach to solve job sequencing problems using heuristic rules and artificial neural networks is proposed. The problem is to find a job sequence for a single machine that minimizes the total weighted tardiness of the jobs. Two different cases are considered: (1) when there are no setups, and (2) when there are sequence-dependent setup times. So far, successful heuristic rules for these cases are: apparent tardiness cost (ATC) rule proposed by Vepsalainen and Morton for the former case, and an extended version of the ATC rule (ATCS) proposed by Lee, Bhaskaran, and Pinedo for the latter. Both approaches utilize some look-ahead parameters for calculating the priority index of each job. As reported by Bhaskaran and Pinedo, the proper value of the look-ahead parameter depends upon certain problem characteristics, such as due-date tightness and due-date range. Thus, an obvious extension of the ATC or the ATCS rule is to adjust the parameter values depending upon the problem characteristics: this is known to be a difficult task. In this paper, we propose an application of a neural network as a tool to ‘predict’ proper values of the look-ahead parameters. Our computational tests show that the proposed hybrid approach outperforms both the ATC rule with a fixed parameter value and the ATCS using the heuristic curve-fitting method.     

A comparative analysis of two different approaches to scheduling in flexible flow shops

This work is an investigation about the relative effectiveness of two approaches to scheduling in flexible flow shops: one approach advocating the possible use of different dispatching rules at different stages of the flow shop, and the other suggesting the use of the same dispatching rule at all the stages of the flow shop. In the latter approach, the dispatching rule contains the information related to both process time and duedate. Both approaches aim at the minimization of measures related to flowtime and tardiness of jobs. This paper essentially is an attempt at exploring the relative effectiveness of these two approaches to scheduling.     

基于混合流水作业组织的集装箱码头装卸作业集成调度优化

集装箱码头集疏运资源调度的对象是由岸桥、集卡、场桥所构成的多阶段一体化的集装箱装、卸、运操作系统,将该系统的调度优化基于多阶段混合流水线调度问题建立混合整数规划模型,同时考虑集装箱码头现实作业中预定义顺序、避免岸桥交叉作业、以及取决于作业顺序的切换时间等现实约束,针对问题自身的特点设计了两阶段启发式算法,得出各阶段设备的指派结果及作业顺序。通过与基于现行调度规则的调度方案以及与目标函数理论下界值的对比实验,显示了所提出的集成调度模型及求解算法能够有效降低船舶在港时间并实现集卡资源的共享,为集装箱码头集疏运资源的集成调度提供了新的思路。     

A hybrid knowledge discovery model using decision tree and neural network for selecting dispatching rules of a semiconductor final testing factory

One of the most challenging production decisions in the semiconductor testing industry is to select the most appropriate dispatching rule which can be employed on the shop floor to achieve high manufacturing performance against a changing environment. Job dispatching in the semiconductor final testing industry is severely constrained by many resources conflicts and has to fulfil a changing performance required by customers and plant managers. In this study we have developed a hybrid knowledge discovery model, using a combination of a decision tree and a back-propagation neural network, to determine an appropriate dispatching rule using production data with noise information, and to predict its performance. We built an object-oriented simulation model to mimic shop floor activities of a semiconductor testing plant and collected system status and resultant performances of several typical dispatching rules, earliest-due-date (EDD) rule, first-come-first-served rule, and a practical dispatching heuristic taking set-up reduction into consideration. Performances such as work-in-process, set-up overhead, completion time, and tardiness are examined. Experiments have shown that the proposed decision tree found the most suitable dispatching rule given a specific performance measure and system status, and the back propagation neural network then predicted precisely the performance of the selected rule.     

一种基于带熵的遗传算法在车间调度中的应用

车间调度问题是现代制造业快速发展的瓶颈因素,因此提高车间调度的效率和有效性就成了生产制造领域大家普遍关注的问题。现行的车间调度问题遗传算法已经不能满足现代制造业快速发展的要求,多因为其静态性或效率差,表现为早熟或收敛停滞,究其根本原因还是GA的最优参数的选取问题,本文引入了信息熵的概念,以动态调整交叉概率和变异概率,从而给出了可以快速获得最优解的自适应遗传算法,并对此改进算法加以实例仿真验证其有效性。     

考虑随机且可控提前期的时基补货发货策略

研究了随机且可控提前期情况下"库存补货与运输排程"(SRSS)的时基补货发货策略,在"允许缺货,缺货不补"的传统假设基础上,结合使用随机过程更新理论和优化方法,建立了扩展模型;使用仿真方法跟踪了优化策略的长期执行效果,以验证模型有效性.