A neural network decision-making model for job-shop scheduling

Scheduling in a job-shop system is a challenging task. Simulation modelling is a well-known approach for evaluating the scheduling plans of a job-shop system; however, it is costly and time-consuming, and developing a model and interpreting the results requires expertise. As an alternative, we have developed a neural network (NN) model focused on detailed scheduling that provides a versatile job-shop scheduling analysis framework for management to easily evaluate different possible scheduling scenarios based on internal or external constraints. A new approach is also proposed to enhance the quality of training data for better performance. Previous NN models in scheduling focus mainly on job sequencing and simple operations flow, and may not consider the complexities of real-world operations. The proposed model’s output proved statistically equivalent to the results of the simulation model. The study was accomplished using sensitivity analysis to measure the effectiveness of the input variables of the NN model and their impact on the output, revealing that the batch size variable had a significant impact on the scheduling results in comparison with other variables.     

A filtered-beam-search-based heuristic algorithm for flexible job-shop scheduling problem

Scheduling for the flexible job-shop is a very important issue in both fields of combinatorial optimization and production operations. However, due to combination of the routing and sequencing problems, flexible job-shop scheduling problem (FJSP) presents additional difficulty than the classical job-shop scheduling problem and requires more effective algorithms. This paper developed a filtered-beam-search-based heuristic algorithm (named as HFBS) to find sub-optimal schedules within a reasonable computational time for the FJSP with multiple objectives of minimising makespan, the total workload of machines and the workload of the most loaded machine. The proposed algorithm incorporates dispatching rules based heuristics and explores intelligently the search space to avoid useless paths, which makes it possible to improve the search speed. Through computational experiments, the performance of the presented algorithm is evaluated and compared with those of existing literature and those of commonly used dispatching rules, and the results demonstrate that the proposed algorithm is an effective and practical approach for the FJSP.     

A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs

It is shown that the job-shop problem with two machines and a fixed number ofk jobs with makespan criterionJ2¦n=k¦C ^max is polynomially solvable. Sotskov and Shakhlevich (1993) have shown that problemJ3¦n=3¦C _maxisNP-hard. Furthermore it is well known that J¦n=2¦C _maxin polynomially solvable. Thus, our result settles the remaining open question concerning the complexity status of job-shop problems with fixed numbers of jobs and machines.Supported by Deutsche Forschungsgemeinschaft, Project Jop-TAG     

A variable neighbourhood search algorithm for the flexible job-shop scheduling problem

The flexible job-shop scheduling problem (FJSP) is a generalisation of the classical job-shop scheduling problem which allows an operation of each job to be executed by any machine out of a set of available machines. FJSP consists of two sub-problems which are assigning each operation to a machine out of a set of capable machines (routing sub-problem) and sequencing the assigned operations on the machines (sequencing sub-problem). This paper proposes a variable neighbourhood search (VNS) algorithm that solves the FJSP to minimise makespan. In the process of the presented algorithm, various neighbourhood structures related to assignment and sequencing problems are used for generating neighbouring solutions. To compare our algorithm with previous ones, an extensive computational study on 181 benchmark problems has been conducted. The results obtained from the presented algorithm are quite comparable to those obtained by the best-known algorithms for FJSP.     

A GRASP algorithm for flexible job-shop scheduling problem with limited resource constraints

A greedy randomised adaptive search procedure (GRASP) is an iterative multi-start metaheuristic for difficult combinatorial optimisation. The GRASP iteration consists of two phases: a construction phase, in which a feasible solution is found and a local search phase, in which a local optimum in the neighbourhood of the constructed solution is sought. In this paper, a GRASP algorithm is presented to solve the flexible job-shop scheduling problem (FJSSP) with limited resource constraints. The main constraint of this scheduling problem is that each operation of a job must follow an appointed process order and each operation must be processed on an appointed machine. These constraints are used to balance between the resource limitation and machine flexibility. The model objectives are the minimisation of makespan, maximum workload and total workload. Representative benchmark problems are solved in order to test the effectiveness and efficiency of the GRASP algorithm. The computational result shows that the proposed algorithm produced better results than other authors’ algorithms.     

Auction-based approach for a flexible job-shop scheduling problem with multiple process plans

This study addresses the flexible job-shop scheduling problem with multiple process plans with the objective of minimizing the overall makespan. A nonlinear programming model is formulated to allocate machines and schedule jobs. An auction-based approach is proposed to address the integrated production route selection and resource allocation problem and focus on improving resource utilization and productive efficiency to reduce the makespan. The approach consists of an auction for process plans and an auction for machines. The auctions are evaluated to select a more suitable route for production and allocate resources to a more desirable job. Numerical experiments are conducted by testing new large benchmark instances. A comparison of Lingo and other existing algorithms demonstrates the effectiveness and stability of the proposed auction-based approach. Furthermore, SPSS is used to prove that the proposed method exhibits an absolute advantage, particularly for medium-scale or large-scale instances.     

Comparison between rule- and optimization-based workload control concepts: a simulation optimization approach

An important goal of Production Planning and Control systems is to achieve short and predictable flow times, especially where high flexibility in meeting customer demand is required, while maintaining high output and due-date performance. One approach to this problem is the workload control (WLC) concept. Within WLC research two directions have been developed, largely separately, over time: Rule based and optimisation-based models. If a company intends to introduce an order release concept based on WLC it first has to decide which of these two approaches should be applied. Therefore, this paper compares two of the most widely used and considered best performing periodic order release models out of both streams: the LUMS (rule based) and the clearing function model (optimisation based). The parameters of both approaches are set using simulation optimisation. The performance is compared using a simulation study of a hypothetical job shop in a rolling horizon setting. The results show that the optimisation model outperforms the rule-based mechanism in all instances with stochastic demand (exponential inter-arrival times), but is outperformed in aggregate cost of backorders and inventory holding and balancing measures by the LUMS approach for scenarios with high utilisation and seasonal demand.     

A large-scale distributed decision-making procedure for a single-machine scheduling problem

This paper presents a distributed scheduling procedure for a large-scale single-machine problem with precedence constraints, and identifies phenomena using large-scale distributed decision-making for a decomposable and distributed situation. The approach proposed exhibits efficient computational performance over a large-sized work load (23,000 jobs and 2,209,536 precedence constraints) in a distributed computing environment. We highlight three findings: (1) the communication burden originating from the large-scale problem can lead to performance loss while distributed agents collaborate to solve the problem, but after a threshold the computational gain by distribution offsets the loss; (2) when the problem size is sufficiently large, the real computation gain outperforms the expected gain by the number of agents (super-linear effect); and (3) when the number of precedence constraints of each agent differs, the slowest agent processing the largest number of precedence constraints restrains the computational performance (load imbalance). We believe that our research is the first distributed decision-making model that meets the requirements of distributed information, distributed decision authority, and distributed computation in a large-scale single-machine scheduling situation with precedence constraints.     

Performance evaluation and capacity planning in a metallurgical job-shop system using open queueing network models

In this paper, we apply performance evaluation and capacity allocation models to support decisions in the design (or redesign) and planning of a job-shop queueing network of a metallurgical plant. Approximate parametric decomposition methods are used to evaluate system performance measures, such as the expected work-in-process (WIP) and production leadtimes. Based on these methods, optimisation models are then applied for the allocation (or reallocation) of capacity to the stations of the job-shop network. These models are also used to generate approximate trade-off curves between capacity investment and WIP or leadtime, which are valuable for a production manager to estimate how much capacity should be allocated to the stations to reach some targeted performance measures. These curves are also useful for the sensitivity analysis of the solutions to changes in the input parameters, such as the variability of the product demands, the mix of the production and the throughput rate of the network.     

Methods for activating the decision-making process that is used for controlling flexible manufacturing systems

This paper deals with controlling flexible manufacturing systems (FMS) operating in volatile production environments. Shnits et al. (Shnits, B., Rubinovitz, J., and Sinreich, D., 2004. Multicriteria dynamic scheduling methodology for controlling a flexible manufacturing system. International Journal of Production Research, 42 (17), 3457–3472.) and Shnits and Sinreich (Shnits, B. and Sinreich, D., 2006. Controlling flexible manufacturing systems based on a dynamic selection of an appropriate operational criteria and scheduling policy. International Journal of Flexible Manufacturing Systems, 18 (1), 1–27.) developed a multi-criteria dynamic scheduling mechanism for controlling an FMS that can cope with such environments. An important part of this mechanism functioning, which impinges directly on its performance, is the activation of its decision-making process. This study continues the research presented in the above-mentioned papers and proposes different triggering methods for activating the control system decision-making process. The operational conditions for each suggested triggering method were analysed and a comparative analysis between these methods was performed. It was revealed that the highly dynamic triggering method, which activates the decision-making process right before a resource becomes available, outperformed the triggering methods that use a predefined scheduling period.     

Job sequencing and selection within workload control order release: an assessment by simulation

Recent research has highlighted the potential impact of pool sequencing on order release performance but it suffered from two shortcomings. First, arguably the best release solution for workload control in practice combines periodic with continuous release. Although the two types of releases serve different functions, recent work assumed the same sequencing rule should be used for both. Here, the use of different sequencing rules for periodic and continuous releases is evaluated. Using a job-shop simulation, we demonstrate that the rule applied during continuous releases has only a negligible impact on performance. Therefore, jobs can be pulled intermediately from the pool by workers using a more straightforward sequencing rule than the one applied for periodic release. Second, it was assumed that all jobs in the pool are sequenced and then a subset is selected for release. But for some load-oriented sequencing rules, the priority value used for sequencing jobs should be updated after each job selection from the pool. Our simulation results show that although this may improve load balancing at release, it does not in fact improve overall shop performance. Therefore, the greedy heuristic of first sequencing and then selecting jobs can be maintained, which allows the release decision-making process to retain its simplicity. The work has important implications for the use of sequencing rules in practice.     

Handling the complexities of real-life job shops when implementing workload control: a decision framework and case study

The workload control literature highlights the importance of balancing the shop floor workload, but also acknowledges that this can conflict with processing the most urgent orders – hence, there is a trade-off. In practice, shops contain many complexities, e.g. simultaneous batching and sequence-dependent set-up times that may conflict with processing the most urgent orders and require other solutions than workload balancing to avoid capacity losses. This adds to the trade-off dilemma, which traditionally only considers timing and balancing. This paper develops a framework that determines whether to address a complexity through order release or dispatching. It comprises two dimensions: (i) the typical position of a complexity in the routing of an order and (ii) the criticality of the complexity. A case study is presented, which demonstrates the framework’s utility and illustrates the development of specific solutions designed to handle the complexities. Most complexities present in the case require handling at the order release stage. The challenges of handling multiple complexities at this decision level are evaluated. Finally, the implications for managers and future research are outlined.     

Continuous workload control order release revisited: an assessment by simulation

Order release is a key component of the Workload Control concept. Jobs do not enter the shop floor directly – they are retained in a pre-shop pool and released in time to meet due dates while keeping work-in-process within limits or norms. There are two important groups of release methods: continuous methods, for which the workload falling to a specified level can trigger a release at any moment in time; and, periodic release methods, for which releases take place at fixed intervals. Continuous release methods in general have been shown to outperform periodic release methods. Yet, there is incongruence in the results presented in the literature on the relative performance of the various continuous release methods. We use a job shop simulation model to examine the performance of continuous release methods from the literature and find that the contradictory results are explained by the different rules applied to sequence jobs in the pool – a factor neglected in previous work. Finally, a new breed of continuous release methods has recently emerged, but these have not been compared with prior approaches. Therefore, we also examine these methods and show that they significantly improve overall performance, although this is to the detriment of jobs with large processing times.     

A Pareto-based estimation of distribution algorithm for the multi-objective flexible job-shop scheduling problem

To solve the multi-objective flexible job-shop problem (MFJSP), an effective Pareto-based estimation of distribution algorithm (P-EDA) is proposed. The fitness evaluation based on Pareto optimality is employed and a probability model is built with the Pareto superior individuals for estimating the probability distribution of the solution space. In addition, a mechanism to update the probability model is proposed, and the new individuals are generated by sampling the promising searching region based on the probability model. To avoid premature convergence and enhance local exploitation, the population is divided into two sub-populations at certain generations according to a splitting criterion, and different operators are designed for the two sub-populations to generate the promising neighbour individuals. Moreover, multiple strategies are utilised in a combination way to generate the initial solutions, and a local search strategy based on critical path is proposed to enhance the exploitation ability. Furthermore, the influence of parameters is investigated based on the Taguchi method of design of experiment, and a suitable parameter setting is suggested. Finally, numerical simulation based on some well-known benchmark instances and comparisons with some existing algorithms are carried out. The comparative results demonstrate the effectiveness of the proposed P-EDA in solving the MFJSP.     

Order release in a workload controlled flow-shop with sequence-dependent set-up times

In this paper, we report a simulation study on the role of sequence-dependent set-up times in decision making at the order release level of a workload controlled make-to-order flow-shop. The study evaluates the potential for set-ups savings, dependent on the level of workload in the shop, for two alternative strategies, namely considering set-up times centrally, within the release decision or locally, within the dispatching decision. These strategies are compared and assessed on the basis of two main performance measures namely time in system and standard deviation of the job lateness. Results indicate that the local strategy, which has been traditionally adopted in practice and in most of the studies dealing with sequence-dependent set-up times, does not always give the best results. The release frequency and the shop workload appear critical to the selection of the strategy to adopt, strongly influencing system performance.     

Flexible job-shop scheduling/rescheduling in dynamic environment: a hybrid MAS/ACO approach

In real-world manufacturing, disruptions are often encountered during the execution of a predetermined schedule, leading to the degradation of its optimality and feasibility. This study presents a hybrid approach for flexible job-shop scheduling/rescheduling problems under dynamic environment. The approach, coined as ‘HMA’ is a combination of multi-agent system (MAS) negotiation and ant colony optimisation (ACO). A fully distributed MAS structure has been constructed to support the solution-finding process by negotiation among the agents. The features of ACO are introduced into the negotiation mechanism in order to improve the performance of the schedule. Experimental studies have been carried out to evaluate the performance of the approach for scheduling and rescheduling under different types of disruptions. Different rescheduling policies are compared and discussed. The results have shown that the proposed approach is a competitive method for flexible job-shop scheduling/rescheduling for both schedule optimality and computation efficiency.     

Design for manufacturing: application of collaborative multidisciplinary decision-making methodology

Design for manufacturing is often difficult for mechanical parts, since significant manufacturing knowledge is required to adjust part designs for manufacturability. The traditional trial-and-error approach usually leads to expensive iterations and compromises the quality of the final design. The authors believe the appropriate way to handle product design for manufacturing problems is not to formulate a large design problem that exhaustively incorporates design and manufacturing issues, but to separate the design and manufacturing activities and provide support for collaboration between engineering teams. In this article, the Collaborative Multidisciplinary Decision-making Methodology is used to solve a product design and manufacturing problem. First, the compromise Decision Support Problem is used as a mathematical model of each engineering teams’ design decisions and as a medium for information exchange. Second, game-theoretic principles are employed to resolve couplings or interactions between the teams’ decisions. Third, design-capability indices are used to maintain design freedom at the early stages of product realization in order to accommodate unexpected downstream design changes. A plastic robot-arm design and manufacturing scenario is presented to demonstrate the application of this methodology and its effectiveness for solving a complex design for manufacturing problem in a streamlined manner, with minimal expensive iterations.     

Improving the applicability of workload control (WLC): the influence of sequence-dependent set-up times on workload controlled job shops

Simulation has demonstrated that the workload control (WLC) concept can improve performance in job shops, but positive empirical results are scarce. A key reason for this is that the concept has not been developed to handle a number of practical considerations, including sequence-dependent set-up times. This paper investigates the influence of sequence-dependent set-up times on the performance of a workload-controlled job shop. It introduces new set-up-oriented dispatching rules and assesses the performance impact of controlled order release. Simulation results demonstrate that combining an effective WLC order release rule with an appropriate dispatching rule improves performance over use of a dispatching rule in isolation when set-up times are sequence dependent. The findings improve our understanding of how this key implementation challenge can be overcome. Future research should investigate whether the results hold if set-up time parameters are dynamic and set-up times are not evenly distributed across resources.     

Successful implementation of an order release mechanism based on workload control: a case study of a make-to-stock manufacturer

This paper deals with improving the lead-time performance of a large crystal manufacturer that uses a state-of-the-art commercial Enterprise Resource Planning system. Since the company encountered some limitations of the standard production planning and control (PPC) system it sought for improvements by implementing an order release mechanism based on workload control (WLC). WLC employs certain rules for releasing orders in order to maintain a certain level of work in process to achieve a certain utilisation of the production system and thus control the flow times in order to meet the required due dates of the orders. We describe the successful implementation of an order release mechanism based on the WLC concept in this make-to-stock company. The paper describes the implemented order release mechanism, the implementation process and its impact on the company’s performance. We show that the core function of WLC – the order release mechanism – can be integrated successfully into an existing PPC system. Furthermore, this study highlights the applicability of WLC to a wider range of companies, especially to make-to-stock manufacturers.     

Three decades of workload control research: a systematic review of the literature

The workload control (WLC) concept has received much attention in the past three decades; however, a comprehensive literature review has not been presented. In response, this article provides a systematic review of the conceptual, analytical, empirical and simulation-based WLC literature. It explores the evolution of WLC research, determines the current state-of-the-art and identifies key areas for further study. The research finds that the field has evolved substantially. Early research focused on theoretical development and experimental testing of order release strategies; order release was then integrated with other planning stages, e.g., the customer enquiry stage, making the concept more suitable for customised manufacturing and leading to a comprehensive concept which combines input and output control effectively; recent attention has focused on implementing the resulting concept in practice and refining theory. While WLC is well placed to meet the needs of producers of customised products, future research should include: conducting further action research into how WLC can be effectively implemented in practice; studying human factors that affect WLC; and feeding back empirical findings to simulation-based WLC research to improve the applicability of WLC theory to real-life job shops.