Analysis of material flow in a job shop with assembly operations

Facing competitive pressure from both domestic and foreign sources, today's manufacturers must strive to keep delivery promises and reduce inventory. This depends largely on a manufacturer's ability to predict job flowtimes reliably, hence allowing the assignment of accurate and attainable due-dates. An approximation method is presented to estimate the mean and standard deviation of job flowtimes in a dynamic job shop with assembly operations. The accuracy of the method for predicting the flowtimes of jobs with varying structural complexities is assessed through computer simulation. While in general it is more accurate for jobs with simpler structure, the simulation results indicate that, over a range of test conditions, the approximation method is both simple and effective for estimating job flowtimes in assembly shops.     

Reactive scheduling in a make-to-order flexible job shop with re-entrant process and assembly: a mathematical programming approach

A mixed-integer linear programming model is presented for the scheduling of flexible job shops, a production mode characteristic of make-to-order industries. Re-entrant process (multiple visits to the same machine group) and a final assembly stage are simultaneously considered in the model. The formulation uses a continuous time representation and optimises an objective function that is a weighted sum of order earliness, order tardiness and in-process inventory. An algorithm for predictive-reactive scheduling is derived from the proposed model to deal with the arrival of new orders. This is illustrated with a realistic example based on data from the mould making industry. Different reactive scheduling scenarios, ranging from unchanged schedule to full re-scheduling, are optimally generated for order insertion in a predictive schedule. Since choosing the most suitable scenario requires balancing criteria of scheduling efficiency and stability, measures of schedule changes were computed for each re-scheduling solution. The short computational times obtained are promising regarding future application of this approach in the manufacturing environment studied.     

Integrated scheduling and self-reconfiguration for assembly job shop in knowledgeable manufacturing

The problems of integrated assembly job shop (AJS) scheduling and self-reconfiguration in knowledgeable manufacturing are studied with the objective of minimising the weighted sum of completion cost of products, the earliness penalty of operations and the training cost of workers. In AJS, each workstation consists of a certain number of teams of workers. A product is assumed to have a tree structure consisting of components and subassemblies. The assembly of components, subassemblies and final products are optimised with the capacity of workstations simultaneously. A heuristic algorithm is developed to solve the problem. Dominance relations of operations are derived and applied in the development of the heuristic. A backward insertion search strategy is designed to locally optimise the operation sequence. Once the optimal schedule is acquired, the teams are reconfigured by transferring them from workstations of lower utilisation to those of higher utilisation. Effectiveness of the proposed algorithm is tested by a number of numerical experiments. The results show that the proposed algorithm promises lower total cost and desirable simultaneous self-reconfiguration in accordance with scheduling.     

Flexible job shop with continuous material flow

A new scheduling problem, the continuous flow flexible job shop (CF-FJS) is proposed. The formulation combines the well-known flexible job shop (FJS) problem and a dedicated continuous material flow model (MFM). In the MFM, operations are represented by material flow functions derived by integration of arbitrarily defined speed patterns. Two main concepts of the MFM formalism, i.e. variable speed of processing and continuous material flow, lead to position-dependent processing times and overlapping in operations which extend standard FJS formulation. Properties of the CF-FJS are investigated. A tabu search sched uling algorithm utilising these properties is proposed. Effective neighbourhood functions are defined based on elimination approaches. Two auxiliary procedures: search intensification level switching and fast feasibility detection are added to improve algorithm efficiency. The algorithm is verified using dedicated benchmark instances which comprise non-trivial representations of the CF-FJS specific features, i.e. machine efficiency patterns and minimum inter-operation buffers. The research is motivated by task scheduling in a fastener factory, but the presented results can be useful in many domains, such as production of granular goods, steel details, glass and fluids. The solution can be used in real-world applications. The published results can be helpful in testing new CF-FJS scheduling algorithms.     

Minimizing makespan in a two-stage flow shop with parallel batch-processing machines and re-entrant jobs

Against a background of heat-treatment operations in mould manufacturing, a two-stage flow-shop scheduling problem is described for minimizing makespan with parallel batch-processing machines and re-entrant jobs. The weights and release dates of jobs are non-identical, but job processing times are equal. A mixed-integer linear programming model is developed and tested with small-scale scenarios. Given that the problem is NP hard, three heuristic construction methods with polynomial complexity are proposed. The worst case of the new constructive heuristic is analysed in detail. A method for computing lower bounds is proposed to test heuristic performance. Heuristic efficiency is tested with sets of scenarios. Compared with the two improved heuristics, the performance of the new constructive heuristic is superior.     

Investigating the factors influencing the shop performance in a job shop environment with kanban-based production control

In this paper, we intended to explore three research questions related to applying just-in-time (JIT) manufacturing techniques in a job shop environment with the kanban-based production control. Simulation experiments were performed and the results were analysed using a statistical method, planned comparison. We found that the adoption of cellular layout in a job shop with the kanban system should only be considered if the amount of setup time reduction achievable through cellular manufacturing is medium to large; otherwise, functional layout should be adopted. In addition, moving parts in batches within cells was found to be more advantageous than moving parts one piece at a time. Only minor effects of material handling speed on the shop performance were identified.     

A comparative study of priority dispatching rules in a hybrid assembly/job shop

This paper reports on research conducted on the use of priority dispatching rules in a hybrid assembly/job shop which manufactures both single-component and multiple-component products. A simulation model was constructed and a large stale experiment performed. Statistical analysis of the simulation results indicated significant impact of both the priority rules tested, and the product-mix considered on shop performance.

Among the 12 priority rules tested, the SPT (shortest processing time) rule and the ASMF-SPT (assembly jobs first with SPT as tie-breaker) rule performed very well with respect to measures like lateness, flow time, tardiness, staging time, and percent of jobs tardy. These findings lead to further investigation of a combined priority rule, MIXED, which implements the ASMF-SPT rule at all machine centres that process components of assembly jobs, and the SPT rule at the remaining machine centres which process non-component jobs. The additional research results yielded evidence that the MIXED rule can reduce the staging time of the SPT rule, and yielded betrer results than the ASMF-SPT rule with regard to other performance measures.

The most interesting finding, however, was the small variation in flow time distribution resulting from use of the MIXED rule when there were more assembly jobs. In an MRP environment, it is especially desirable to have a priority dispatching rule resulting in minimum variation in individual flow times which allows the replenishment lead times to be estimated with greater accuracy.     

Setting optimal production lot sizes and planned lead times in a job shop

In this research, we model a job shop that produces a set of discrete parts in a make-to-stock setting. The intent of the research is to develop a planning model to determine the optimal tactical policies that minimise the relevant manufacturing costs subject to workload variability and capacity limits. We consider two tactical decisions, namely the production lot size for each part and the planned lead time for each work station. We model the relevant manufacturing costs, entailing production overtime costs and inventory-related costs, as functions of these tactical decisions. We formulate a non-linear optimisation model and implement it in the Excel spreadsheet. We test the model with actual factory data from our research sponsor. The results are consistent with our intuition and demonstrate the potential value from jointly optimising over these tactical policies.     

An extension of modified-operational-due-date priority rule incorporating job waiting times and application to assembly job shop

The well-known priority dispatching rule MOD (Modified Operational Due Date) in job shop scheduling considers job urgency through ODD (Operational Due Date) and also incorporates SPT (Shortest Processing Time)-effect in prioritising operationally late jobs; leading to robust behaviour in Mean Tardiness (MT) with respect to tightness/looseness of due dates. In the present paper, we study an extension of the MOD rule using job-waiting-time based discrimination among operationally late jobs to protect long jobs from excessive delays by incorporating an ‘acceleration property’ into the scheduling rule. Formally, we employ a weighted-SPT dispatching priority index of the form: (Processing time)/(Waiting time)^α for operationally late jobs, while the priority index is ODD for operationally non-late jobs; and the latter class of jobs has a lower priority than the former class. In the context of Assembly Job Shop scheduling, some existing literature includes considerable focus around the concept of ‘Staging Delay’, i.e., waiting of components or sub-assemblies for their counterparts for assembly. Some existing approaches attempt dynamic anticipation of staging delay problems and re-prioritisation of operations along converging branches. In the present paper, rather than depending on such a centralised and largely backward scheduling approach, we consider a partially decentralised approach, endowing jobs with a priority index yielding an ‘acceleration property’ based on a ‘look-back’ in terms of waiting time, rather than ‘look-ahead’. For the particular case, in our proposed rule, whenα is set at zero and when all jobs at a machine are operationally late, our rule agrees with MOD as both exhibit the SPT effect. In simulation tests of our priority scheme for assembly job shops, in comparison with leading heuristics in literature, we found our rule to be particularly effective in: (1) minimising conditional mean tardiness, (2) minimising 99-percentile-point of the tardiness distribution, through proper choice ofα. We also exploit an interesting duality between the scheduling and queueing control versions of the problem. Based on this, some exact and heuristic analysis is given to guide the choice ofα, which is also supported by numerical evidence.     

Simultaneous scheduling of production and maintenance tasks in the job shop

This paper deals with the job shop problem of simultaneous scheduling of production operations and preventive maintenance tasks. To solve this problem, we develop an elitist multi-objective genetic algorithm that provides a set of Pareto optimal solutions minimising the makespan and the total maintenance cost. A deep study was made to choose the best encoding, operators, and the different probabilities. Some lower bounds of the adopted criteria are developed. The computational experiments carried out on a set of published instances validate the efficiency of the proposed algorithm.     

An integrative heuristic method for detailed operations scheduling in assembly job shop systems

In this paper, we describe a new heuristic method for simulating and supporting the operations scheduling process in assembly job shop systems. The method is based on the assumption that the improvement in operations synchronisation at fabrication and assembly stations brings forth better achievement of due dates. The method implements two scheduling approaches: a backward approach satisfying due date completely and a forward approach satisfying capacity restrictions completely. The two approaches work iteratively within two different simulation models of the production system – one deterministic and the other probabilistic – in searching for operations synchronisation improvement and due date achievement. The method intends to be integrative, i.e., to be able to integrate effectively three fundamental enterprise systems: order processing, production scheduling, and manufacturing activity control. An experimental study was conceived to evaluate the suitability of the method to support scheduling decision making. As results demonstrate, the method proves to be suitable for this objective. As a co-product, results show the method is better than the single-pass procedure/rules tested on average and is as good as the best single-pass procedure/rule tested.     

Impact of sequence-dependent setup time on job shop scheduling performance

In a production system using multi-purpose and flexible machines, reducing setup time is an important task for better shop performance. Numerous cases were reported about successful reduction of setup times by standardization of setup procedures. However, setup times have not been eliminated and remain an important element of real production problems for production systems such as commercial printing, plastics manufacturing, metal processing, etc. It is especially critical when the setup time is sequence dependent. In this situation, shop performance cannot be effectively improved without the aid of an appropriate scheduling procedure. Review of the past studies shows that there has not been a significant amount of research done on the scheduling procedure for a dynamic job shop with sequence dependent setup times. This paper investigates the job shop scheduling problems that are complicated by sequence-dependent setup times. The study classifies and tests scheduling rules by considering whether setup time and/or due date information is employed. These scheduling rules are evaluated in dynamic scheduling environments defined by due date tightness, setup times and cost structure. A simulation model of a nine machine job shop is used for the experiment. A hypothetical, asymmetric, setup time matrix is applied to the nine machines.     

Bad-scenario-set robust scheduling for a job shop to hedge against processing time uncertainty

This paper proposed two robust scheduling formulations in real manufacturing systems based on the concept of bad scenario set to hedge against processing time uncertainty, which is described by discrete scenarios. Two proposed robust scheduling formulations are applied to an uncertain job-shop scheduling problem with the makespan as the performance criterion. The united-scenario neighbourhood (UN) structure is constructed based on bad scenario set for the scenario job-shop scheduling problem. A tabu search (TS) algorithm with the UN structure is developed to solve the proposed robust scheduling problem. An extensive experiment was conducted. The computational results show that the first robust scheduling formulation could be preferred to the second one for the discussed problem. It is also verified that the obtained robust solutions could hedge against the processing time uncertainty through decreasing the number of bad scenarios and the degree of performance degradation on bad scenarios. Moreover, the computational results demonstrate that the developed TS algorithm is competitive for the proposed robust scheduling formulations.     

Approximations for the time spent in a dynamic job shop with applications to due-date assignment

In this paper we develop approximations for the distribution of the total time spent in a dynamic job shop. In particular, using an exponential limit theorem and an heuristic decomposition of open queueing networks, we show that for a large class of dynamic job shops, the total time spent in a dynamic job shop can be approximated by an exponential random variable with an appropriate mean. Approximations for job shops that do not belong to this class are also developed. Numerical results show that the proposed approximations are in general very good. Application of these approximations in the assignment of due-dates is also illustrated.     

Using the Kanban in a job shop environment

Japanese industrial management techniques have been applied in a large number of large Western enterprises. In particular, the Kanban method has been used to control materials, production rate and volume, and to adjust production to requirements. The authors show how the Kanban method may be adapted to the job shop. This adaptation was extensively tested through simulation and then implemented. Actual performance is consistent with the simulation results, and shows marked improvement over previous practice.     

Optimal due-date assignment in a job shop†

This paper presents an analytical model for determining the optimal processing-time and number of operations multiples for the TWK and TWK + NOP due-date assignment methods in a dynamic job shop subject to restrictive assumptions on queue discipline and processing time distribution. The analytical results are compared with the experimental results obtained from simulation of a hypothetical job shop under various shop conditions. The close agreement of the results reveals the validity of the analytical model. In addition, the results show that the TWK + NOP method is more effective in minimizing the missed due-date cost in a job shop.     

An energy-efficient two-stage hybrid flow shop scheduling problem in a glass production

Energy-efficient scheduling is highly necessary for energy-intensive industries, such as glass, mould or chemical production. Inspired by a real-world glass-ceramics production process, this paper investigates a bi-criteria energy-efficient two-stage hybrid flow shop scheduling problem, in which parallel machines with eligibility are at stage 1 and a batch machine is at stage 2. The performance measures considered are makespan and total energy consumption. Time-of-use (TOU) electricity prices and different states of machines (working, idle and turnoff) are integrated. To tackle this problem, a mixed integer programming (MIP) is formulated, based on which an augmented ε-constraint (AUGMECON) method is adopted to obtain the exact Pareto front. A problem-tailored constructive heuristic method with local search strategy, a bi-objective tabu search algorithm and a bi-objective ant colony optimisation algorithm are developed to deal with medium- and large-scale problems. Extensive computational experiments are conducted, and a real-world case is solved. The results show effectiveness of the proposed methods, in particular the bi-objective tabu search.     

On the equivalence of small batch assembly line balancing and lot streaming in a flow shop

In this article we compare two apparently dissimilar scheduling problems. The Small Batch Assembly Line Balancing problem is the process of dividing operations over multiple stations so as to produce a series of parts whose processing times are characterized by learning. The Lot Streaming in a Flow Shop problem is the process of splitting a given lot or job to allow overlap of successive operations in multi-stage production systems, thereby reducing the makespan of the corresponding schedule. We show that the two problems are formally equivalent. By exploring the mathematical equivalence of the two problems, a number of unexpected new results have been obtained.     

Information and scheduling in a dual resource constrained job shop

In today's job shop, computers make information readily available, but there is limited research about which information to use and how to use it controlling a dual resource constrained (DRC) job shop. We develop and test new order review/ release (ORR) job dispatching and labour assignment rules that use different types of information. We compare the performance of a naive ORR rule (i.e., releasing all jobs immediately upon receipt) and other rules in the literature which use little information to a new ORR rule, modified load conversion (MLC), which uses all the available information. Our tests demonstrate that MLC performs better than the other ORR rules we tested. But the new job dispatching and labour assignment rules developed to use different types of information do not significantly improve performance. A sensitivity analysis demonstrates that although the shop performance is sensitive to the cost structure for every policy tested, the new MLC ORR rule performs well over a wide range of cost structures.     

A genetic algorithm for flexible job shop scheduling with fuzzy processing time

This paper presents a flexible job shop scheduling problem with fuzzy processing time. An efficient decomposition-integration genetic algorithm (DIGA) is developed for the problem to minimise the maximum fuzzy completion time. DIGA uses a two-string representation, an effective decoding method and a main population. In each generation, DIGA decomposes the chromosomes of the main population into a job sequencing part and a machine assigning part and independently evolves the populations of these parts. Some instances are designed and DIGA is tested and compared with other algorithms. Computational results show the effectiveness of DIGA.