A simulation based approach to analyse the effects of job release on the performance of a multi-stage job-shop with processing flexibility

Workload control concepts are advocated as one of the new production planning and control methods. In its elaborated form, workload control includes three major decision levels: job entry, job release and priority dispatching. In each decision level, several decision points which have significant impact on the effectiveness of the production planning and control are defined (i.e., acceptance/rejection, due date assignment, etc.). Workload control systems should consider all of these decision points simultaneously in order to improve the effectiveness of production planning and control. In addition to these decision levels, flexibility of the shop can also be included as the fourth decision level which allows the shop capacity to be adjusted as new orders enter the system and as they are released to the shop floor. In this study, simulation models which enable the effect of each decision level within a workload control concept to be explored are developed and tested. The results reveal that simultaneous consideration of decision levels is critical and can improve the effectiveness of production planning and control.     

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.     

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.     

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.     

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.     

Workload based order acceptance in job shop environments

In practice, order acceptance and production planning are often functionally separated. As a result, order acceptance decisions are made without considering the actual workload in the production system, or by only regarding the aggregate workload. We investigate the importance of a good workload based order acceptance method in over-demanded job shop environments, and study approaches that integrate order acceptance and resource capacity loading. We present sophisticated methods that consider technological restrictions, such as precedence relations, and release and due dates of orders. We use a simulation model of a generic job shop to compare these methods with straightforward methods, which consider capacity restrictions at an aggregate level and ignore precedence relations. We compare the performance of the approaches based on criteria such as capacity utilisation. The simulation results show that the sophisticated approaches significantly outperform the straightforward approaches in case of tight due dates (little slack). In that case, improvements of up to 30% in utilisation rate can be achieved. In case of much slack, a sophisticated order acceptance method is less important.This complete issue was revised and published online in November 2004. The previous version contained a false date. Correspondence to: E.W. Hans     

Using aggregate estimation models for order acceptance in a decentralized production control structure for batch chemical manufacturing

Aggregate models of detailed scheduling problems are needed to support aggregate decision making such as customer order acceptance. In this paper, we explore the performance of various aggregate models in a decentralized control setting in batch chemical manufacturing (no-wait job shops). Using simulation experiments based on data extracted from an industry application, we conclude that a linear regression based model outperforms a workload based model with regard to capacity utilization and the need for replanning at the decentralized level, specifically in situations with increased capacity utilization and/or a high variety in the job mix.     

Card-based delivery date promising in pure flow shops with order release control

Card-based systems are simple, effective means of controlling production. Yet most systems concentrate on controlling the shop floor. They neglect other planning tasks, like estimating short, feasible due dates during customer enquiry management. A card-based version of the workload control concept for job shops – COBACABANA (COntrol of BAlance by CArd-BAsed Navigation) – was proposed in the literature to overcome this shortcoming. COBACABANA uses cards for due date setting and order release, making it a potentially important solution for small shops with limited resources. But many such firms operate as flow shops rather than job shops. Research demonstrated that COBACABANA’s release mechanism must be adapted if applied to a pure flow shop, but its approach to due date setting has not been evaluated in such an environment. We show COBACABANA has the potential to improve pure flow shop performance, but its due date setting procedure should be adapted compared to job shops. In a flow shop, due date estimation can also be further simplified by considering the load awaiting release to the first (gateway) station only while maintaining most performance benefits. The results are important for all card-based systems that aim to stabilise work-in-process, including kanban and ConWIP (Constant Work-in-Process).     

Aligning workload control theory and practice: lot splitting and operation overlapping issues

This paper addresses the problem of lot splitting in the context of workload control (WLC). Past studies on WLC assumed that jobs released to the shop floor proceed through the different stages of processing without being split. However, in practice, large jobs are often split into smaller transfer sublots so that they can move more quickly and independently through the production process and allow operations overlapping relating to the same job. This paper assesses the performance of different lot splitting policies for job release and dispatching strategies under lot splitting. A new dispatching rule was designed to specifically take advantage of lot splitting and operations overlapping in the context of WLC. Discrete-event simulation is used to assess system performance in relation to the ability to provide shorter delivery times and on time deliveries. Results highlight the importance of releasing the sublots of the same job together and demonstrate that combining an effective lot splitting policy with an appropriate dispatching rule can enhance the performance of production systems.     

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.     

Integrating load-based order release and priority dispatching

Workload control (WLC) is a well-established production control concept for job shops that put primary emphasis on load-based order release. Recent advances in load-based order release research have led to an improved delivery performance at reduced shop floor workloads. But although order release is the primary focus of WLC research, it must be coupled with priority dispatching on the shop floor if order progress is to be regulated. Prior simulation research suggests that load-based order release methods should only be coupled with simple dispatching rules because other, more powerful rules can conflict with the functioning of the release method. Yet, recent empirical research suggests that powerful priority dispatching rules – such as due date-oriented dispatching rules – are in fact needed for a high level of delivery performance to be obtained in practice. This paper focuses on overcoming the conflict between order release and dispatching, so load-based order release can be combined with due date-oriented dispatching. Preliminary analysis reveals that part of the conflict is because existing due date-oriented dispatching rules overcompensate for schedule deviations that occur when orders are either released earlier or later than planned. Two alternative new dispatching rules based on an improved method of determining operation due dates are then developed to better account for schedule deviations and overcome the conflict with load-based order release. Further improvements in delivery performance are obtained, while the large workload reductions achieved by recently developed load-based order release methods are retained.     

Towards an Integrated Workload Control (WLC) Concept: The Performance of Due Date Setting Rules in Job Shops with Contingent Orders

Workload control (WLC) is a production planning and control concept developed for make-to-order companies. Its customer enquiry management methodology supports due date setting, while its order release mechanism determines when to start production. For make-to-order companies, due date setting is a strategically important, complex task where unconfirmed jobs place demands on capacity which are contingent on a quotation being accepted by the customer. Yet most prior WLC research has begun at the order release stage with a set of confirmed orders with predetermined due dates. In contrast, this paper focuses specifically on customer enquiry management and uses simulation to compare and contrast the performance of 11 due date setting rules in a job shop where part of the workload consists of unconfirmed or contingent orders. The best results are achieved by a finite loading rule which explicitly considers the workload of contingent orders when estimating lead times. This enables demand to be levelled over time, allowing due dates to be short and reliable – thereby improving both the competitiveness of a make-to-order company and the customer service level it is able to offer. Future research should focus on integrating customer enquiry management, and its due date setting rule, with order release control.     

Lot streaming multiple jobs with values exponentially deteriorating over time in a job-shop environment

The main issue in lot streaming (LS) is determining the means by which to split jobs into sub-jobs to improve the makespan (or some other criterion). However, LS has been overlooked in most studies dealing with scheduling problems associated with specific kinds of job shops, where the job value exponentially deteriorates over time. The current study attempts to determine whether the expected benefits of LS would be evident in the job-shop scheduling problem (JSP) with the objective of maximising the total value of jobs. This study comprised two stages. In the first stage, we studied the influence of a fixed number of sub-jobs on the performance of the LS by systematically varying this parameter using the fixed number job splitting (FNJS) approach. We considered a total of 12 dispatching rules for the analysis of relative performance. Simulation results suggest that dividing each job into several sub-jobs increases the total value of jobs. In addition, dispatching rules incorporating information related to job value perform better than those without this information. In the second stage of the study, we proposed a genetic algorithm-based job splitting (GAJS) approach. The simulation results led us to conclude that the GAJS approach is superior to the FNJS approach in terms of the total value of the jobs and the average number of sub-jobs generated.     

The application of workload control in assembly job shops: an assessment by simulation

Workload control (WLC) is a production planning and control concept developed to meet the needs of small- and medium-sized make-to-order companies, where a job shop configuration is common. Although simulation has shown WLC can improve job shop performance, field researchers have encountered significant implementation challenges. One of the most notable challenges is the presence of ‘assembly job shops’ where product structures are more complex than typically modelled in simulation and where the final product consists of several sub-assemblies (or work orders) which have to be co-ordinated. WLC theory has not been developed sufficiently to handle such contexts, and the available literature on assembly job shops is limited. In response, this paper extends the applicability of WLC to assembly job shops by determining the best combination of: (i) WLC due date (DD) setting policy, (ii) release method and (iii) policy for coordinating the progress of work orders. When DDs are predominantly set by the company, the DD setting policy should play the leading role while the role of order release should be limited and the progress of work orders should not be co-ordinated in accordance with the DD of the final product. But when DDs are predominantly specified by customers, the importance of order release as a second workload balancing mechanism increases and work orders should be coordinated by backward scheduling from the DD of the final product. Results indicate that WLC can improve performance in assembly job shops and outperform alternative control policies. Future research should implement these findings in practice.     

Distributed policy search reinforcement learning for job-shop scheduling tasks

We interpret job-shop scheduling problems as sequential decision problems that are handled by independent learning agents. These agents act completely decoupled from one another and employ probabilistic dispatching policies for which we propose a compact representation using a small set of real-valued parameters. During ongoing learning, the agents adapt these parameters using policy gradient reinforcement learning, with the aim of improving the performance of the joint policy measured in terms of a standard scheduling objective function. Moreover, we suggest a lightweight communication mechanism that enhances the agents' capabilities beyond purely reactive job dispatching. We evaluate the effectiveness of our learning approach using various deterministic as well as stochastic job-shop scheduling benchmark problems, demonstrating that the utilisation of policy gradient methods can be effective and beneficial for scheduling problems.     

A multi-attribute dispatching rule for automated guided vehicle systems

This paper considers the dispatching problem associated with operations of automated guided vehicles (AGVs). A multi-attribute dispatching rule for dispatching of an AGV is developed and evaluated. The multi-attribute rule, using the additive weighting method, considers three system attributes concurrently: the remaining space in the outgoing buffer of a workstation, the distance between an idle AGV and a workstation with a job waiting for the vehicle to be serviced, and the remaining space in the input buffer of the destination workstation of a job. A neural network approach is used to obtain dynamically adjusting attribute weights based on the current status of the manufacturing system. Simulation analysis of a job shop is used to compare the multi-attribute dispatching rule with dynamically adjusting attribute weights to the same dispatching rule with fixed attribute weights and to several single attribute rules. Results show that the multi-attribute dispatching rule with the ability to adapt attribute weights to job shop operational conditions provides a better balance among the performance measures used in the study.     

Dynamic job shop scheduling for missed due date performance

In this research, missed due date in terms of mean absolute lateness (MAL) and mean square lateness (MSL) has been considered as a performance criterion and a scheduling study has been performed to improve the missed due date performance in dynamic, stochastic, multi machine job shop environments. In the study, a new due date assignment model was proposed and a new dynamic dispatching rule was developed. The results indicate that the proposed due date assignment model is very successful for improving the missed due date performance and the developed dispatching rule is also very successful for meeting the assigned due dates.     

Scheduling in dynamic assembly job-shops with jobs having different holding and tardiness costs

Most studies on scheduling in dynamic job-shops assume that the holding cost of a job is given by the flowtime of the job and that the tardiness cost of a job is given by the tardiness of the job. In other words, unit holding and unit tardiness costs of a job are assumed. However, in reality, such an assumption need not hold, and it is quite possible that there are different costs for holding and tardiness for different jobs. In addition, most studies on job-shop scheduling assume that jobs are independent and that no assembly operations exist. The current study addresses the problem of scheduling in dynamic assembly job-shops (manufacturing multilevel jobs) with the consideration of different holding and tardiness costs for different jobs. An attempt is made to develop efficient dispatching rules by incorporating the relative costs of holding and tardiness of jobs in the form of scalar weights. The primary objective of scheduling considered here is the minimization of the total scheduling cost consisting of the sum of holding and tardiness costs. The performance of the scheduling rules in minimizing the individual components of total scheduling cost is also observed. The results of an extensive simulation study on the performance of different dispatching rules show that the proposed rules are effective in minimizing the means and maximums of the primary measure, and are quite robust with respect to different job structures and experimental settings.     

Job-shop scheduling: limits of the binary disjunctive formulation

The deterministic job-shop scheduling problem exhibits the fundamental computational difficulty implicit in determining an optimal timetable for sharing production resources among competing production activities. While adaptation of the formal model to industrial practice is fraught with difficulties, we show that the underlying binary-disjunctive formulation itself is more robust than might be immediately apparent. Straightforward extensions of the underlying model are sufficient to capture such practical problem features as assembly and disassembly sequences, due-dates and out-processing operations, scheduled maintenance, nonzero release times and dispatch operations, certain sequence-dependent set-ups and materials handling delays, and a great range of operational side-constraints. Technological sequences need not be total orders, job priorities can be assigned explicitly or implicitly, and any regular measure of performance can be represented. The principal structural limitation is that machining sequences must represent total orders over component operations to preserve the model form. For this reason, concurrent or parallel processing (as in machining centres or cells) and indefinite cyclical process flows (as are sometimes required for rework) cannot be modelled directly. An example problem is provided which illustrates these extensions and an industrial application employing the extended model is briefly considered.     

Labour flexibility and assignment policies in a job shop having incommensurable objectives

This study evaluates operating policies for offering a near-perfect delivery performance for vital customers in dual resource-constrained (DRC) job shop environments. Prior studies have considered this problem in machine-limited settings, and shown that dispatching rules that help realise a near-perfect delivery performance for vital customers necessarily deteriorate delivery performance for other customers served by the shop. This study extends prior work, and considers additional tools that can be used by managers in DRC shops such as labour flexibility, and assignment rules that incorporate customer-based information to deploy workers to departments containing high-priority jobs. Results show that labour flexibility in conjunction with appropriate decision rules allows for enhanced delivery performance for both vital and normal priority customers. These results hold even under conditions where 80% of the shop's workload is compromised of high-priority orders.