Data-mining-based dynamic dispatching rule selection mechanism for shop floor control systems using a support vector machine approach

The purpose of this paper is to develop a data-mining-based dynamic dispatching rule selection mechanism for a shop floor control system to make real-time scheduling decisions. In data mining processes, data transformations (including data normalisation and feature selection) and data mining algorithms greatly influence the predictive accuracy of data mining tasks. Here, the z-scores data normalisation mechanism and genetic-algorithm-based feature selection mechanism are used for data transformation tasks, then support vector machines (SVMs) is applied for the dynamic dispatching rule selection classifier. The simulation experiments demonstrate that the proposed data-mining-based approach is more generalisable than approaches that do not employ a data-mining-based approach, in terms of accurately assigning the best dispatching strategy for the next scheduling period. Moreover, the proposed SVM classifier using the data-mining-based approach yields a better system performance than obtained with a classical SVM-based dynamic dispatching rule selection mechanism and heuristic individual dispatching rules under various performance criteria over a long period.     

Scheduling dynamic block assembly in shipbuilding through hybrid simulation and spatial optimisation

Scheduling block assembly in shipyard production poses great difficulties regarding the accurate prediction of the required spatial resource and effective production control for achieving managerial objectives due to the dynamic spatial layout and the stochastic nature of the production system. In this study, this dynamic space-constrained problem is viewed as two sequential decisions, namely rule-based dispatching and a static spatial configuration. A novel hybrid planning method is developed to employ discrete-event simulation as look-ahead scheduling to evaluate the system performance under various control policies. To rationalise block placement and improve long-term area utilisation, a discrete spatial optimisation problem is formulated and solved using an enumeration-based search algorithm, followed by the application of a series of heuristic positioning strategies. By imitation of the dynamic dispatching and spatial operation, a statistical analysis of the resultant performance can be conducted to select the best-performing priority rules. A case study with an experimental investigation is performed for a local shipyard to demonstrate the applicability of the proposed method.     

An integrated scheduling and material-handling approach for complex job shops: a computational study

We suggest an extension of the shifting bottleneck heuristic for complex job shops that takes the operations of automated material-handling systems (AMHS) into account. The heuristic is used within a rolling horizon approach. The job-shop environment contains parallel batching machines, machines with sequence-dependent setup times, and re-entrant process flows. Jobs are transported by an AMHS. Semiconductor wafer fabrication facilities (wafer fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic (SBH) uses a disjunctive graph to decompose the overall scheduling problem into scheduling problems for single machine groups and for transport operations. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). We consider SSPs based on dispatching rules. In this paper, we are also interested in how much we can gain in terms of TWT if we apply more sophisticated SSPs for scheduling the transport operations. We suggest a Variable Neighbourhood Search (VNS) based SSP for this situation. We conduct simulation experiments in a dynamic job-shop environment in order to assess the performance of the suggested algorithms. The integrated SBH outperforms common dispatching rules in many situations. Using near to optimal SSPs leads to improved results compared with dispatching based SSPs for the transport operations.     

Performance-based dynamic scheduling model for flexible manufacturing systems

A performance-based dynamic scheduling model for random flexible manufacturing systems (FMSs) is presented. The model is built on the mathematical background of supervisory control theory of discrete event systems. The dynamic FMS scheduling is based on the optimization of desired performance measures. A control theory-based system representation is coupled with a goal programming-based multi-criteria dynamic scheduling algorithm. An effectiveness function, representing a performance index, is formulated to enumerate the possible outputs of future schedules. Short-term job scheduling and dispatching decisions are made based on the values obtained by optimizing the effectiveness function. Preventive actions are taken to reduce the difference between actual and desired target values. To analyse the real-time performance of the proposed model, a software environment that included various Visual Basic Application® modules, simulation package Arena®, and Microsoft Access® database was developed. The experimentation was conducted (a) to determine the optimum look-ahead horizons for the proposed model and (b) to compare the model with conventional scheduling decision rules. The results showed that the proposed model outperformed well-known priority rules for most of the common performance measures.     

The study of real time scheduling by an intelligent multi-controller approach

Earlier studies indicated that using multiple dispatching rules (MDRs) for the various zones in the system can enhance the production performance to a greater extent than using a single dispatching rule (SDR) over a given scheduling interval for all the machines in the system, since MDRs employ the multi-pass simulation approach for real-time scheduling (RTS). However, if a classical machine learning approach is used, an RTS knowledge base (KB) can be developed by using the appropriate MDRs strategy (this method is called an intelligent multi-controller in this paper) as obtained from training examples. The main disadvantage of using MDRs is that the classes (scheduling decision variables) to which training examples are assigned must be provided. Hence, developing an RTS KB using the intelligent multi-controller approach becomes an intolerably time-consuming task because MDRs for the next scheduling period must be determined. To address this issue, we proposed an intelligent multi-controller incorporating three main mechanisms: (1) simulation-based training example generation mechanism, (2) data pre-processing mechanism and (3) SOM-based real time MDRs selection mechanism. Under various performance criteria over a long period, the proposed approach yields better system performance than the machine learning-based RTS using the SDR approach and heuristic individual dispatching rules.     

Generalized preemption models for single-machine dynamic scheduling problems

In the extensive scheduling literature, job preemption, if allowed, implies that the processing of a partly completed job is temporarily halted and later resumed at the same point. However, little attention has been given to problems where job preemption is allowed under the condition that either some startup time delay must be incurred or some fraction of work must be repeated if preemption occurs. We generalize the notion of job preemption by using models representing these conditions. The models are applied to studying the dynamic single-machine scheduling problems of minimizing total flow time, and of minimizing maximum lateness, subject to arbitrary and unknown job ready dates. On-line optimal dispatching rules, which consider only available - as opposed to look-ahead - information, are developed. These rules determine, on arrival or completion of each job, which available job should next be processed by the machine. A special case of our models, the preempt-repeat scenario, where preempted jobs must be totally repeated, is suggested as heuristic for the equivalent non-preemptive static problem where all ready dates are known and given. A computational study is performed to determine the potential benefits of reducing startup time delays or work repetition fractions in the context of continuous improvement of manufacturing systems.     

A real-time scheduling mechanism for a flexible manufacturing system: Using simulation and dispatching rules

This paper presents a real-time scheduling methodology which uses simulation and dispatching rules for flexible manufacturing systems. We develop a scheduling mechanism in which job dispatching rules vary dynamically based on information from discrete event simulation that is used for evaluating candidate dispatching rules. In this paper, we improve and extend a previous research on simulation-based real-time scheduling by suggesting a more systematic framework for the scheduling mechanism through refinement of functions of modules in the mechanism, and by presenting and analysing various scheduling strategies used to operate the mechanism. The strategies are formed by combining two factors that might influence the performance of the mechanism: type of simulation model which is used in the mechanism and points of time when new dispatching rules are selected. In order to compare performance of the scheduling strategies, computational experiments are performed and results are reported.     

Learning dispatching rules using random forest in flexible job shop scheduling problems

In this paper, we address the flexible job-shop scheduling problem (FJSP) with release times for minimising the total weighted tardiness by learning dispatching rules from schedules. We propose a random-forest-based approach called Random Forest for Obtaining Rules for Scheduling (RANFORS) in order to extract dispatching rules from the best schedules. RANFORS consists of three phases: schedule generation, rule learning with data transformation, and rule improvement with discretisation. In the schedule generation phase, we present three solution approaches that are widely used to solve FJSPs. Based on the best schedules among them, the rule learning with data transformation phase converts them into training data with constructed attributes and generates a dispatching rule with inductive learning. Finally, the rule improvement with discretisation improves dispatching rules with a genetic algorithm by discretising continuous attributes and changing parameters for random forest with the aim of minimising the average total weighted tardiness. We conducted experiments to verify the performance of the proposed approach and the results showed that it outperforms the existing dispatching rules. Moreover, compared with the other decision-tree-based algorithms, the proposed algorithm is effective in terms of extracting scheduling insights from a set of rules.     

A study on the performance of scheduling rules in buffer-constrained dynamic flowshops

Most studies on scheduling in manufacturing systems using dispatching rules deal with jobshops, while there are only few reports dealing with dynamic flowshops. It is known that the performance of many dispatching rules in dynamic jobshops is different from that in dynamic flowshops. Moreover, many research reports assume that there are no buffer constraints in the shop, and even those reports dealing with buffer-constrained shops present the evaluation of existing dispatching rules for unconstrained shops in the context of buffer constraints with the consideration of a limited number of objectives of scheduling. In this study, we deal with the problem of scheduling in dynamic flowshops with buffer constraints. With respect to different time-based objectives, the best dispatching rules for scheduling in unconstrained shops have been identified from the existing literature. In addition, two new dispatching rules specially designed for flowshops with buffer constraints are proposed. All dispatching rules under consideration are evaluated in dynamic flowshops with buffer constraints on the basis of an extensive simulation study covering different levels of buffer constraints, shop load or utilization, and missing operations in flowshops. The proposed rules are found to perform better than the existing dispatching rules in buffer-constrained flowshops with respect to many measures of performance.     

复杂型面智能生产单元任务−刀具联合动态调度策略

以复杂型面智能生产单元为背景,针对多机器的任务?刀具联合动态调度问题展开研究。通过分析复杂型面智能生产单元的作业流程和特征,建立任务?刀具联合调度问题的数学模型。结合通过对问题进行过程分解的方式构建一种组合规则调度算法生产框架,并通过在框架中嵌入启发式规则的方式生成72种组合规则算法。设计大量的算例测试集,通过对比、分析72种算法在差异化环境配置下的仿真结果,对比不同系统指标下算法的表现情况,发现基于FNOP规则构建的算法在75%的场景中均能取得较优的求解质量。研究成果为车间生产管理人员制定任务?刀具调度策略提供一定指导作用。     

A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles

To achieve a significant improvement in the overall performance of a flexible manufacturing system, the scheduling process must consider the interdependencies that exist between the machining and transport systems. However, most works have addressed the scheduling problem as two independent decision making problems, assuming sufficient capacity in the transport system. In this paper, we study the simultaneous scheduling (SS) problem of machines and automated guided vehicles using a timed coloured Petri net (TCPN) approach under two performance objectives; makespan and exit time of the last job. The modelling approach allows the evaluation of all the feasible vehicle assignments as opposed to the traditional dispatching rules and demonstrates the benefits of vehicle-controlled assignments over machine-controlled for certain production scenarios. In contrast with the hierarchical decomposition technique of existing approaches, TCPN is capable of describing the dynamics and evaluating the performance of the SS problem in a single model. Based on TCPN modelling, SS is performed using a hybrid heuristic search algorithm to find optimal or near-optimal schedules by searching through the reachability graph of the TCPN with heuristic functions. Large-sized instances are solved in relatively short computation times, which were a priori unsolvable with conventional search algorithms. The algorithm’s performance is evaluated on a benchmark of 82 test problems. Experimental results indicate that the proposed algorithm performs better than the conventional ones and compares favourably with other approaches.     

A learning-based methodology for dynamic scheduling in distributed manufacturing systems

To enhance productivity in a distributed manufacturing system under hierarchical control, we develop a framework of dynamic scheduling scheme that explores routeing flexibility and handles uncertainties. We propose a learning-based methodology to extract scheduling knowledge for dispatching parts to machines. The proposed methodology includes three modules: discrete-event simulation, instance generation, and incremental induction. First, a sophisticated simulation module is developed to implement a dynamic scheduling scheme, to generate training examples, and to evaluate the methodology. Second, the search for training examples (good schedules) is successfully fulfilled by the genetic algorithm. Finally, we propose a tolerance-based learning algorithm that does not only acquire general scheduling rules from the training examples, but also adapts to any newly observed examples and thus facilitates knowledge modification. The experimental results show that the dynamic scheduling scheme significantly outperforms the static scheduling scheme with a single dispatching rule in a distributed manufacturing system.     

Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation

We study resource allocation in cellular systems and consider the problem of finding a power efficient scheduling in an uplink single carrier frequency division multiple access system. Due to the discrete nature of this problem and its computational difficulty, particularly in a real-time setting, the use of suboptimal algorithms is common practice. We aim at an effective way of gauging the performance of suboptimal algorithms by finding tight bounds on the global optimum. Toward this end, we first provide a basic integer linear programming formulation. Then we propose a significantly stronger column-oriented formulation and a corresponding column generation method, as well as an enhanced column generation scheme. The latter extends the first scheme through the inclusion of a stabilization technique, an approximate column generation principle, and a tailored heuristic that is embedded in the column generation scheme to find high-quality though not necessarily global optimal solutions. The computational evaluation demonstrates that compared with a poor performance by the integer linear programming formulation, the column generation method can produce near-optimal schedules that enable a sharp bounding interval. The enhanced column generation method significantly sharpens the bounding interval. Hence the column generation approach serves well for the purpose of benchmarking results for large-scale instances.     

Novel slack-based robust scheduling rule for a semiconductor manufacturing system with uncertain processing time

The NP-hard scheduling problems of semiconductor manufacturing systems (SMSs) are further complicated by stochastic uncertainties. Reactive scheduling is a common dynamic scheduling approach where the scheduling scheme is refreshed in response to real-time uncertainties. The scheduling scheme is overly sensitive to the emergence of uncertainties because the optimization of performance (such as minimum make-span) and the system robustness cannot be achieved simultaneously by conventional reactive scheduling methods. To improve the robustness of the scheduling scheme, we propose a novel slack-based robust scheduling rule (SR) based on the analysis of robustness measurement for SMS with uncertain processing time. The decision in the SR is made in real time given the robustness. The proposed SR is verified under different scenarios, and the results are compared with the existing heuristic rules. Simulation results show that the proposed SR can effectively improve the robustness of the scheduling scheme with a slight performance loss.     

Dynamic adjustment of dispatching rule parameters in flow shops with sequence-dependent set-up times

Decentralised scheduling with dispatching rules is applied in many fields of production and logistics, especially in highly complex manufacturing systems. Since dispatching rules are restricted to their local information horizon, there is no rule that outperforms other rules across various objectives, scenarios and system conditions. In this paper, we present an approach to dynamically adjust the parameters of a dispatching rule depending on the current system conditions. The influence of different parameter settings of the chosen rule on the system performance is estimated by a machine learning method, whose learning data is generated by preliminary simulation runs. Using a dynamic flow shop scenario with sequence-dependent set-up times, we demonstrate that our approach is capable of significantly reducing the mean tardiness of jobs.     

Learning effective dispatching rules for batch processor scheduling

Batch processor scheduling, where machines can process multiple jobs simultaneously, is frequently harder than its unit-capacity counterpart because an effective scheduling procedure must not only decide how to group the individual jobs into batches, but also determine the sequence in which the batches are to be processed. We extend a previously developed genetic learning approach to automatically discover effective dispatching policies for several batch scheduling environments, and show that these rules yield good system performance. Computational results show the competitiveness of the learned rules with existing rules for different performance measures. The autonomous learning approach addresses a growing practical need for rapidly developing effective dispatching rules for these environments by automating the discovery of effective job dispatching procedures.     

A constraint-based perspective in resource constrained project scheduling

In this study, a new heuristic approach to the resource constrained project scheduling problem is introduced. This approach, which is called local constraint based analysis (LCBA), is more robust than the dispatching rules found in the literature, since it does not depend on an a priori insight as do the dispatching rules. LCBA consists of the application of local essential conditions which respect the current temporal and resource constraints to generate a necessary sequence of activities at a scheduling decision time point in a single-pass parallel scheduling algorithm. LCBA is a time efficient procedure due to the localized aspect with which the activities are handled. Only the activities which are schedulable at the current scheduling time are considered for the application of the essential conditions. LCBA is tested against well-known rules from the literature and some recently developed rules. This testing is done using a set of problems of a special design and also a set of optimally solved problems from a recent benchmark in the literature. It is observed that near optimal time efficient solutions are obtained by LCBA and the procedure's performance is considerably better than that of the dispatching rules.     

Dynamic state-dependent dispatching for wafer fabrication

A dynamic state-dependent dispatching (DSDD) heuristic for a wafer fabrication plant is presented. The DSDD heuristic dynamically uses different dispatching rules according to the state of a production system. Rather than developing new rules, the DSDD heuristic combines and modifies existing rules. This heuristic first classifies workstations into dynamic bottlenecks and non-dynamic bottlenecks. Dynamic bottleneck workstations apply a revised two-boundary dispatching rule when their queue length exceeds the average obtained from simulation using constant lot-release policy and first-in, first-out dispatching rule. Otherwise, the shortest expected processing time until next visit dispatching rule is used. A revised FGCA (FGCA+) dispatching rule is used for all non-dynamic bottlenecks workstations. Simulation results demonstrate that the DSDD heuristic obtains the best performance among the compared six dispatching rules in terms of average and standard deviation of cycle time and work-in-process.     

On-line scheduling of multi-server batch operations

The batching of jobs in a manufacturing system is a very common policy in many industries. The main reasons for batching are the avoidance of setups and/or facilitation of material handling. Good examples of batch-wise production systems are the ovens that are found in the aircraft industry and in the manufacture of semiconductors. These systems often consist of multiple machines of different types for the range and volumes of products that have to be handled. Building on earlier research in the aircraft industry, where the process of hardening synthetic aircraft parts was studied, we propose a new heuristic for the dynamic scheduling of these types of systems. Our so-called look-ahead strategy bases its decision to schedule a job on a certain machine on the availability of information on a limited number of near future arrivals. The new control strategy distinguishes itself from existing heuristics by an integrated approach that involves all machines in the scheduling decision, instead of only considering idle machines. It is shown by an extensive series of simulation experiments that the new heuristic outperforms existing heuristics for most system configurations. Especially in the case of complex systems, where multiple products have to be handled by non-identical machines, the new heuristic proves its value as a practical scheduling tool. Important insight is obtained with regard to the relation between the system is configuration and its performance.     

A new paradigm for rule-based scheduling in the wafer probe centre

This paper addresses the scheduling problem in the wafer probe centre. The proposed approach is based on the dispatching rule, which is popularly used in the semiconductor manufacturing industry. Instead of designing new rules, this paper proposes a new paradigm to utilize these rules. The proposed paradigm formulates the dispatching process as a 2-D assignment problem with the consideration of information from multiple lots and multiple pieces of equipment in an integrated manner. Then, the dispatching decisions are made by maximizing the gains of multiple possible decisions simultaneously. Besides, we develop a genetic algorithm (GA) for generating good dispatching rules through combining multiple rules with linear weighted summation. The benefits of the proposed paradigm and GA are verified with a comprehensive simulation study on three due-date-based performance measures. The experimental results show that under the proposed paradigm, the dispatching rules and GA can perform much better than under the traditional paradigm.