A distributed scheduling method for computer integrated manufacturing: the use of local area networks in cellular systems

This paper describes a distributed scheduling approach that takes into account characteristics of the communication network in the computer-integrated manufacturing environment. The approach is based on a network-wide bidding scheme wherein the scheduling decision is made by collecting the price of each manufacturing cell for taking on the job; different dynamic scheduling heuristics can be incorporated in this scheme and executed in a distributed fashion. This paper also describes the formalism and model for the distributed scheme that can be embedded in a communication protocol. A simulation study has been conducted to evaluate and compare the performance of different strategies or heuristics employed in the scheduling method.     

A comparison of exhaustive and non-exhaustive group scheduling heuristics in a manufacturing cell

Previous group scheduling research has primarily focused on developing exhaustive two-stage heuristics in order to manage product flow through manufacturing cells. The objective of this paper is to present new, non-exhaustive heuristics and compare them with existing exhaustive heuristics in a job shop cell environment. Computer simulation is utilized to examine six non-exhaustive and six exhaustive heuristics under eight experimental conditions. The results indicate that although some non-exhaustive heuristics dominate the exhaustive heuristics on the average tardiness measure, the performance of exhaustive heuristics are generally superior to that of non-exhaustive heuristics. Furthermore, the performance of the exhaustive heuristics is more robust to the experimental factors.     

A comprehensive analysis of group scheduling heuristics in a job shop cell

This paper describes a broad-based simulation study of the performance of two-stage group scheduling heuristics in a job shop cell. The objective of this study was to examine the direct and interactive effects of a variety of shop factors on the performance of the best, previously reported, group scheduling heuristics. A set of traditional single-stage scheduling heuristics were examined as well. Shop factors considered include: setup to runtime ratio, cell load level and variability of inter-arrival times. An assumption common to group scheduling research which provides for an equal division of the part family into subfamilies is also examined. This is accomplished through the creation of an alternative scenario where the majority of the parts are assigned to one subfamily, i.e. one subfamily dominates the part family population. The effects of set up to runtime ratio and cell load have been examined in previous group scheduling research, but not in conjunction with the inter-arrival time variability factor. Further, no study has examined the impact of subfamily dominance on group scheduling heuristics in a full-scale simulation study. The results indicate that performance comparable to that of the two -stage heuristics can be obtained with the easily implementable single-stage heuristics when factors which lessen the impact of setup times are in place. In particular, the tardiness performance of two-stage scheduling heuristics deteriorates when subfamily dominance is in effect while the single-stage heuristics exhibit dramatic improvements in tardiness performance. Low setup to runtime ratio, shop load, and less variable inter-arrivals all induce dramatic performance gains across all measures among the single-stage heuristics, while yielding only marginal improvement in the performance of the two-stage heuristics. As a result, in many instances when combinations of these factors are in effect, the single-stage heuristics yield similar performance to the two-stage heuristics.     

Scheduling learning dependent jobs in customised assembly lines

The large variety of product models required by customised markets implies lot size reduction. This strongly affects manual-based production activities, since workers need to promptly adapt to the specifications of the next model to be produced. Completion times of manual-based activities tend to be highly variable among workers, and are difficult to estimate. This affects the scheduling of those activities since scheduling precision depends on reliable estimates of job completion times. This paper presents a method that combines learning curves and job scheduling heuristics aimed at minimising the total weighted earliness and tardiness. Workers performance data is collected and modelled using learning curves, enabling a better estimation of the completion time of jobs with different size and complexity. Estimated completion times are then inputted in new scheduling heuristics for unrelated parallel workers, equivalent to machines in this study, created by modifying heuristics available in the literature. Performance of the proposed heuristics is assessed analysing the difference between the optimal schedule objective function value and that obtained using the heuristics, as well as the workload imbalance among workers. Some contributions in this paper are: (i) use of learning curves to estimate completion times of jobs with different sizes and complexities from different teams of workers; and (ii) use of a more complex scheduling objective function, namely the total weighted earliness and tardiness, as opposed to most of the developments in the current scheduling literature. A shoe manufacturing application illustrates the developments in the paper.     

Hybrid genetic algorithm for group technology economic lot scheduling problem

The concept of group technology has been successfully applied to many production systems, including flexible manufacturing systems. In this paper we apply group technology principles to the economic lot scheduling problem, which has been studied for over 40 years. We develop a heuristic algorithm and a hybrid genetic algorithm for the group technology economic lot scheduling problem. Numerical experiments show that the developed algorithms outperform the existing heuristics.     

An effective heuristic for adaptive control of job sequences subject to variation in processing times

Variation in sequential task processing times is common in manufacturing systems. This type of disturbance challenges most scheduling methods since they cannot fundamentally change job sequences to adaptively control production performance as jobs enter the system because actual processing times, are not known in advance. Some research literature indicates that simple rules are more suitable than algorithmic scheduling methods for adaptive control. In this work, a ‘state space – average processing time’ (SS-APT) heuristic is proposed and compared to four most commonly used scheduling rules and two well-established heuristics based on Taillard’s benchmarks. It is shown that the adaptive control is made possible under variation in processing times given the flexibility and strong performance of the SS-APT heuristic, especially for work-in-process inventory control.     

Scheduling unbalanced cellular manufacturing systems with lot splitting

Recently, a large number of studies have addressed lot splitting as a means to reduce flow times as well as improve due date performance. Furthermore, a number of studies have examined scheduling policies in cellular manufacturing systems. These studies have been conducted under a variety of experimental factors, shop structures and operational assumptions. This study examines scheduling cellular manufacturing systems in the presence of lot splitting. In addition, we utilize various scheduling policies to test formally the underlying principles of the synchronous manufacturing philosophy. This is accomplished by utilizing exhaustive and non-exhaustive scheduling heuristics simultaneously at bottleneck and non-bottleneck workcentres. The results indicate that, under certain conditions, performing additional set-ups before the bottleneck can improve due date performance without an adverse effect on average flow time. Furthermore, we show that incurring additional set-ups after the bottleneck does not improve due date performance and may deteriorate flow time performance. These results conflict with some of the tenets of the synchronous manufacturing philosophy.     

抓钩排序问题综述

为提高生产率,先进制造系统中广泛采用自动导向小车、机器人和抓钩（Hoist)等自动化材料搬运装置。这些运送装置的排序直接影响系统的质量、生产率和安全性,因此,在生产中应该得到足够的重视。对抓钩排序问题进行了综述。     

Heuristic algorithms for scheduling heat-treatment furnaces of steel casting industries

This paper addresses a research problem of scheduling parallel, non-identical batch processors in the presence of dynamic job arrivals, incompatible job-families and non-identical job sizes. We were led to this problem through a real-world application involving the scheduling of heat-treatment operations of steel casting. The scheduling of furnaces for heat-treatment of castings is of considerable interest as a large proportion of the total production time is the processing times of these operations. In view of the computational intractability of this type of problem, a few heuristic algorithms have been designed for maximizing the utilization of heat-treatment furnaces of steel casting manufacturing. Extensive computational experiments were carried out to compare the performance of the heuristics with the estimated optimal value (using the Weibull technique) and for relative effectiveness among the heuristics. Further, the computational experiments show that the heuristic algorithms proposed in this paper are capable of obtaining near (statistically estimated) optimal utilization of heat-treatment furnaces and are also capable of solving any large size real-life problems with a relatively low computational effort.     

Intelligent scheduling of discrete automated production line via deep reinforcement learning

The reinforcement learning (RL) is being used for scheduling to improve the adaptability and flexibility of an automated production line. However, the existing methods only consider processing time certain and known and ignore production line layouts and transfer unit, such as robots. This paper introduces deep RL to schedule an automated production line, avoiding manually extracted features and overcoming the lack of structured data sets. Firstly, we present a state modelling method in discrete automated production lines, which is suitable for linear, parallel and re-entrant production lines of multiple processing units. Secondly, we propose an intelligent scheduling algorithm based on deep RL for scheduling automated production lines. The algorithm establishes a discrete-event simulation environment for deep RL, solving the confliction of advancing transferring time and the most recent event time. Finally, we apply the intelligent scheduling algorithm into scheduling linear, parallel and re-entrant automated production lines. The experiment shows that our scheduling strategy can achieve competitive performance to the heuristic scheduling methods and maintains stable convergence and robustness under processing time randomness.     

Multi-criteria optimisation-based dynamic scheduling for controlling FMS

This study deals with controlling flexible manufacturing systems (FMS) operating in volatile production environments. Most studies that address this issue use some sort of adaptive scheduling that enables the FMS to cope with the randomness and variability efficiently. The methods presented in the literature are usually based on heuristics and use simple dispatching rules. They do not consider changing the decision criteria dynamically as the system conditions change. In contrast to previous studies, the present study focuses on developing a control mechanism for dynamic scheduling that is based on incremental optimisation. This means that each time a scheduling decision is made, the local optimisation problem is solved such that the next jobs to be processed on machines are selected. The objective function (dominant decision criterion) for this optimisation problem is selected dynamically based on production order requirements, actual shop-floor status and system priorities. The proposed multi-criteria optimisation-based dynamic scheduling methodology was evaluated and compared with some known scheduling rules/policies. The results obtained demonstrate the superiority of the suggested methodology as well as its capability to cope with a multi-criteria environment.     

Cost modelling in polymer composite applications: Case study – Analysis of existing and automated manufacturing processes for a large wind turbine blade

Cost modelling is typically one of the first steps in the design and development of a new or existing product and can show clear avenues for effective manufacturing. This paper provides an overview of existing cost modelling techniques and details the process term technical cost modelling (TCM), which is a combined parametric and process flow simulation method used widely throughout the manufacturing industry where historical data is either not available or does not exist. A focus is drawn on the manufacture of a 40 m wind turbine blade with the effects of part size, production volume, materials costs and tooling being detailed. A case study is presented which investigates the cost effectiveness of a range of existing manual production methods (hand-lay prepreg, VI, LRTM) and compares this to automated manufacturing (ATL, AFP, overlay braiding). ATL and AFP are shown to reduce manufacturing costs by up to 8% despite the high capital costs associated with automated equipment. The cost centres are isolated and clearly indicate the dominance of materials and labour. Material deposition in the tool is only one of a string of labour intensive processes in the manufacture of a large wind turbine blades and a holistic automated blade manufacturing approach is perhaps required to see the true labour saving benefits.     

An adaptive scheduling algorithm for a parallel machine problem with rework processes

The development of a scheduling methodology for a parallel machine problem with rework processes is presented in this paper. The problem is to make a schedule for parallel machines with rework probabilities, due-dates, and sequence dependent setup times. Two heuristics are developed based on a dispatching algorithm and problem-space-based search method. In order to evaluate the efficacy of the proposed algorithms, six performance indicators are considered: total tardiness, maximum lateness, mean flow-time, mean lateness, the number of tardy jobs, and the number of reworks. This paper shows how these algorithms can adaptively capture the characteristics of manufacturing facilities for enhancing the performance under changing production environments. Extensive experimental results show that the proposed algorithms give very efficient performance in terms of computational time and each objective value.     

Scheduling manufacturing systems for delayed product differentiation in agile manufacturing

Production of customized products to respond to changing markets in a short time and at a low cost for agile manufacturing can be implemented with delayed product differentiation in a manufacturing system. The successful implementation of delayed product differentiation lies in efficient scheduling of the manufacturing system. Scheduling problems in implementing delayed product differentiation in a general flexible manufacturing system are defined, formulated and solved here. The manufacturing system consists of two stages: machining and assembly. At the machining stage, a single machine is used to produce standard component parts for assembly products. These parts are then assembled at the assembly stage by multiple identical assembly stations to form customized products. The products to be produced in the system are characterized by their assembly sequences represented by digraphs. The scheduling problem is to determine the sequence of products to be produced in the system so that the maximum completion time (makespan) is minimized for any given number of assembly stations at the assembly stage. Based on the representation of assembly sequence of the products, three production modes are defined: production of a single product with a simple assembly sequence ; production of a single product with a complex assembly sequence ; and production of N products . According to the three defined production modes, the associated scheduling problems are defined as G s scheduling problems, G c scheduling problems and N-product scheduling problems, respectively. Optimal and heuristic methods for solving the scheduling problems are developed. The computational experiment shows that the heuristics provide good solutions to the scheduling problems.     

Knowledge-based scheduling in flexible manufacturing systems: An integration of pattern-directed inference and heuristic search

This paper presents a knowledge-based scheduling approach based on the problem-solving techniques developed in artificial intelligence. The approach is based on three key techniques. The first is the pattern-directed inference technique to capture the dynamic nature of the scheduling environment. The second is the non-linear planning technique to coordinate manufacturing processes and resource assignments. The third technique is the A? search algorithm to expedite the searching procedure. It models the scheduling process by state-space transitions; the job routing is obtained through selecting a sequence of scheduling operators guided by heuristics. Keeping track of the manufacturing system by a symbolic world model, this approach is adaptive to such environmental changes as new job arrivals and machine breakdowns, suitable for making real-time scheduling decisions.     

A random-key encoded harmony search approach for energy-efficient production scheduling with shared resources

When seeking near-optimal solutions for complex scheduling problems, meta-heuristics demonstrate good performance with affordable computational effort. This has resulted in a gravitation towards these approaches when researching industrial use-cases such as energy-efficient production planning. However, much of the previous research makes assumptions about softer constraints that affect planning strategies and about how human planners interact with the algorithm in a live production environment. This article describes a job-shop problem that focuses on minimizing energy consumption across a production facility of shared resources. The application scenario is based on real facilities made available by the Irish Center for Manufacturing Research. The formulated problem is tackled via harmony search heuristics with random keys encoding. Simulation results are compared to a genetic algorithm, a simulated annealing approach and a first-come-first-served scheduling. The superior performance obtained by the proposed scheduler paves the way towards its practical implementation over industrial production chains.     

Adaptive scheduling and tool flow control in flexible job shops

The recent manufacturing environment is characterized as having diverse products due to mass customization, short production lead-time, and ever-changing customer demand. Today, the need for flexibility, quick responsiveness, and robustness to system uncertainties in production scheduling decisions has dramatically increased. In traditional job shops, tooling is usually assumed as a fixed resource. However, when a tooling resource is shared among different machines, a greater product variety, routing flexibility with a smaller tool inventory can be realized. Such a strategy is usually enabled by an automatic tool changing mechanism and tool delivery system to reduce the time for tooling set-up, hence it allows parts to be processed in small batches. In this paper, a dynamic scheduling problem under flexible tooling resource constraints is studied and presented. An integrated approach is proposed to allow two levels of hierarchical, dynamic decision making for job scheduling and tool flow control in flexible job shops. It decomposes the overall problem into a series of static sub-problems for each scheduling horizon, handles random disruptions by updating job ready time, completion time, and machine status on a rolling horizon basis, and considers the machine availability explicitly in generating schedules. The effectiveness of the proposed dynamic scheduling approach is tested in simulation studies under a flexible job shop environment, where parts have alternative routings. The study results show that the proposed scheduling approach significantly outperforms other dispatching heuristics, including cost over time (COVERT), apparent tardiness cost (ATC), and bottleneck dynamics (BD), on due-date related performance measures. It is also found that the performance difference between the proposed scheduling approach and other heuristics tend to become more significant when the number of machines is increased. The more operation steps a system has, the better the proposed method performs, relative to the other heuristics.     

Performance comparison of virtual cellular manufacturing with functional and cellular layouts in DRC settings

This study investigates the performance of virtual cellular manufacturing (VCM) systems, comparing them with functional layouts (FL) and traditional, physical cellular layout (CL), in a dual-resource-constrained (DRC) system context. VCM systems employ logical cells, retaining the process layouts of job shops. Part family-based scheduling rules are applied to exploit the benefits of group technology while retaining the flexibility and functional synergies of the job shop. Past studies of VCM have been based entirely on single-resource-constrained (SRC) systems, i.e. as purely machine-limited systems, assuming that resources such as labour and tooling do not restrict the output. However, given the fact that labour forms a second major constraining resource, and many of the advantages associated with cellular manufacturing are derived from labour flexibility, it becomes necessary to extend the research to DRC systems. In this study, we assume several levels of labour flexibility in all three systems, in addition to other relevant factors such as lot size, set-up reduction, and labour assignment rules. It is shown that VCM can outperform efficiently operated FL and CL in certain parameter ranges, as preliminary research has shown so far. However, it is shown that CL tends to outperform both VCM and FL in the parameter ranges customarily advocated for CL, namely, low lot sizes, adequate levels of set-up reduction, cross training of workers, and worker mobility within cells.     

Capacitated single machine scheduling and its on-line heuristics

The capacitated single machine scheduling problem arises from a manufacturing system. The machine works periodically and is capacitated in each period. This is a variant of the bin packing problem. We theoretically compare two types of production settings: in the first type, the machine processes each demand without splitting and in the second, splitting is allowed but a setup time occurs. From the worst case viewpoint, we show that the optimal schedule length of the production without splitting may be nearly twice as long as that of the production with splitting. The ratio of two is asymptotically tight. Then we adapt the well-known bin packing heuristics for the on-line version of the capacitated single machine scheduling problem and give their worst case analysis.     

A general framework for scheduling equipment and manpower at container terminals

In this paper, we propose a general model for various scheduling problems that occur in container terminal logistics. The scheduling model consists of the assignment of jobs to resources and the temporal arrangement of the jobs subject to precedence constraints and sequence-dependent setup times. We demonstrate how the model can be applied to solve several different real-world problems from container terminals in the port of Hamburg (Germany). We consider scheduling problems for straddle carriers, automated guided vehicles (AGVs), stacking cranes, and workers who handle reefer containers. Subsequently, we discuss priority rule based heuristics as well as a genetic algorithm for the general model. Based on a tailored generator for experimental data, we examine the performance of the heuristics in a computational study. We obtain promising results that suggest that the genetic algorithm is well suited for application in practice.