Flow shop scheduling problems with assembly operations: a review and new trends

The past few years have witnessed a resurgence of interest in assembly flow shop scheduling as evidenced by increasing number of published articles in this field. A basic assembly flow shop consists of two types of stages: fabrication or machining stage and assembly stage. Machining and assembly stages are composed of either one or a set of machines that are working in parallel. Final products have hierarchical assembly structure with several components and assembly operation(s). The components need to be processed in the machining stage(s) and then assembled based on hierarchical assembly structure. The goal is to find the sequence of jobs that optimises certain objectives. Assembly flow shop scheduling problem has several interesting derivatives and applications in various manufacturing and service industries. This paper provides a consolidated survey of assembly flow shop models with their solution methodology. Finally, the paper concludes by presenting some problems receiving less attention and proposes several salient research opportunities.     

Job-shop like manufacturing system with variable power threshold and operations with power requirements

This paper addresses an important issue in manufacturing by considering the scheduling of a Job-shop like manufacturing system involving a power threshold that must not be exceeded over time. A power profile is attached to operations that must be scheduled. This power profile presents a consumption peak at the start of process in order to model most of real-world machining operations. These operations must be scheduled according to the instantly available power threshold. A mathematical formulation of the problem is proposed; its main goal is to minimise the total completion time of all operations. A set of instances is built based on classical format of instances for the Job-shop problem. As it is time-consuming to obtain exact solutions on these instances with the CPLEX solver, a Greedy Randomised Adaptive Search Procedure hybridised with an Evolutionary Local Search (GRASP × ELS) metaheuristic is designed. The GRASP × ELS is compared with two other metaheuristics: a Variable Neighbourhood Search and a Memetic Algorithm. The GRASP × ELS is also compared with several algorithms developed in the literature for the classical job-shop problem. Results show the relevancy of the metaheuristic approaches both in terms of computational time and quality of solutions.     

Makespan minimisation for a parallel machine scheduling problem with preemption and job incompatibility

In this paper, an extension of the graph colouring problem is introduced to model a parallel machine scheduling problem with job incompatibility. To get closer to real-world applications, where the number of machines is limited and jobs have different processing times, each vertex of the graph requires multiple colours and the number of vertices with the same colour is bounded. In addition, several objectives related to scheduling are considered: makespan, number of pre-emptions and summation over the jobs’ throughput times. Different solution methods are proposed, namely, two greedy heuristics, two tabu search methods and an adaptive memory algorithm. The latter uses multiple recombination operators, each one being designed for optimising a subset of objectives. The most appropriate operator is selected dynamically at each iteration, depending on its past performance. Experiments show that the proposed algorithm is effective and robust, while providing high-quality solutions on benchmark instances for the graph multi-colouring problem, a simplification of the considered problem.     

Online heuristics for unloading boxes off a gravity conveyor

This paper addresses the problem of minimising the number of moves to unload a set of boxes off a gravity conveyor by a forklift. If the input data are known in advance, the problem is efficiently solvable with a dynamic programming approach. However, this method is rarely applicable in practice for two reasons. First, the problem generally occurs in a real-time environment where the input data are revealed over time. Second, computing devices are in most cases not available in forklifts or gravity conveyors for decision-making. Online approaches that can easily be applied by human operators are therefore sought in practice. With this in mind, we first propose some intuitive approaches and analyse their performance through an extensive experimental study. The results show that these approaches are quite inefficient as they average between 14.7 and 59.3% above the optimum. A less intuitive but still simple approach is then designed that consistently produces good results with an average gap of 6.1% to the optimum.     

Maintenance scheduling for a manufacturing system of machines with adjustable throughput

This paper considers the problem of analyzing and optimizing joint schedules of maintenance and throughput adjustment operations in manufacturing systems. The purpose of joint scheduling of maintenance and throughput changing operations is to maximize the cost benefits of maintenance operations in manufacturing systems in which some or all of the machines can execute their function under different process settings, resulting in different machine and system throughputs. Such a capability enables one to strategically slow down more degraded machines or accelerate freshly maintained machines so that production targets can be met and maintenance operations can be offset to times when they are less intrusive on the manufacturing process. A Monte-Carlo-simulation-based method is proposed for the evaluation of cost effectiveness of any schedule of maintenance and throughput changing operations, and a genetic-algorithm-based method is proposed to enable searching for schedules that would maximize the cost benefits of these operations. A matrix chromosome representation of the joint schedules of maintenance and throughput adjustment operations is introduced and several mechanisms of chromosome evolution and selection are proposed and analyzed in numerical simulations of such manufacturing systems. Results indicate a good ability for the newly proposed methods to achieve a tradeoff between cost benefits of production and losses due to maintenance operations through strategic allocation of maintenance and throughput changing actions.     

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.     

Integrating a decomposition procedure with problem reduction for factory scheduling with disruptions: a simulation study

Dispatching rules are widely used in industry because schedules obtained from optimization procedures can be difficult to implement in the face of executional uncertainties. Barua et al. (Barua, A., Narasimhan, R., Upasani, A. and Uzsoy, R., Implementing global factory schedules in the face of stochastic disruptions. Int. J. Prod. Res., 2005, 43(4), 793–818) implement global schedules obtained from an optimization-based heuristic using a dispatching rule, and outperform myopic dispatching rules in the face of disruptions. However, the computation of the global schedules is still time-consuming for realistic instances. Upasani et al. (Upasani, A., Uzsoy, R. and Sourirajan, K., A problem reduction approach for scheduling semiconductor wafer fabrication facilities. IEEE Trans. Semicon. Manuf., 2006, 19, 216–225) develop a problem reduction scheme based on load disparity between work centres, and report significant reduction in CPU times with minimal loss of solution quality in deterministic experiments. In this paper we integrate the problem-reduction scheme to obtain global schedules with the dispatching approach of Barua et al. (Barua, A., Narasimhan, R., Upasani, A. and Uzsoy, R., Implementing global factory schedules in the face of stochastic disruptions. Int. J. Prod. Res., 2005, 43(4), 793–818) in a multi-product environment with stochastic machine breakdowns and job arrivals. A simulation model of a scaled-down wafer fabrication facility is used to evaluate the performance of the proposed procedures. Results show that the integrated procedure outperforms the benchmark dispatching rules while significantly reducing computation times.     

Scheduling a tempered glass manufacturing system: a three-stage hybrid flow shop model

Chinese tempered glass has entered a fast and stable growing era. To improve the productivity of tempered glass manufacturers, this paper investigates a scheduling problem in tempered glass production system, originated from a tempered glass manufacturer in China. This problem can be formulated as a three-stage hybrid flow shop (HFS). Single and batch processing machines coexist in this HFS. Besides, a limited buffer, between the first two stages, and machine eligibility requirement are also significant characteristics. To address this complicated scheduling problem, we first establish an integer programming model with the objective of minimising the makespan, i.e. the maximum completion time of jobs in the system. Due to the strong NP-hard nature of the problem, we then propose a constructive heuristic method, a genetic algorithm, as well as a simulated annealing algorithm, to solve practical large-scale problems. Computational results demonstrate the efficiency of the proposed approaches.     

Ant colony optimisation with random selection for block transportation scheduling with heterogeneous transporters in a shipyard

This paper considers a scheduling problem of heterogeneous transporters for pickup and delivery blocks in a shipyard assuming a static environment where all transportation requirements for blocks are predetermined. In the block transportation scheduling problem, the important issue is to determine which transporter delivers the block from one plant to the other plant and when, in order to minimise total logistic times. Therefore, the objective of the problem is to simultaneously determine the allocation policy of blocks and the sequence policy of transporters to minimise the weighted sum of empty transporter travel times, delay times, and tardy times. A mathematical model for the optimal solution is derived and an ant colony optimisation algorithm with random selection (ACO_RS) is proposed. To demonstrate the performance of ACO_RS, computational experiments are implemented in comparing the solution with the optimal solutions obtained by CPLEX in small-sized problems and the solutions obtained by conventional ACO in large-sized problems.     

Modelling and solving algorithm for two-stage scheduling of construction component manufacturing with machining and welding process

This paper focuses on a two-stage machining and welding scheduling problem based on an investigation at a structural metal manufacturing plant, aiming to minimise the total makespan. Several parts processed at Stage one according to classical job-shop scheduling are grouped into a single construction component at the second welding stage. Fabrication of the construction component cannot begin until all comprising parts have been completed at Stage one. This paper establishes a novel mathematic model to minimise the total makespan by mainly considering the dominance relationship between the construction component and the corresponding parts. In order to solve this two-stage problem, we propose an improved harmony search algorithm. A local search method is applied to the best vector at each iteration, so that a more optimal vector can be subsequently realised. The average value, minimum value, relative percentage deviation and standard deviation are discussed in the experimental section, and the proposed local best harmony search algorithm outperforms the genetic algorithm, immune algorithm and harmony search algorithm without local search. Moreover, six optimal solutions are given as Gantt charts, which vividly illustrate that the mathematical model established in this paper can facilitate the development of a better scheduling scheme.     

Maintenance scheduling of a manufacturing system subject to deterioration

This paper presents an integrated model for the joint determination of both optimal inspection strategy and optimal repair policy for a manufacturing system whose resulting output is subject to system state. An appropriate maintenance strategy is essential to optimize revenue from a manufacturing system which is in continuous operation and subject to deterioration. The optimum policy balances the amount of maintenance required to increase availability against the loss of revenue arising from the down time: insufficient maintenance leads to an increase in the number of defective items, low profit and low maintenance cost; excessive maintenance results in a reduction in the proportion of defective items, high profit and high maintenance cost. In this paper, an intensity control model adapted to partial information provides an optimal inspection intensity and repair degree of the system as an optimal control process to yield maximum revenue. The solution is obtained through formulating an equivalent deterministic Hamilton-Jacobi equation. A numerical example is provided to illustrate the behavior of the optimal control process. The optimal control process determines a solution to both optimum inspection frequency and optimal replacement policy which results in an optimal production run length of the system.     

Studying the effect of different combinations of timetabling with sequencing algorithms to solve the no-wait job shop scheduling problem

This paper considers the no-wait job shop (NWJS) problem with makespan minimisation criteria. It is well known that this problem is strongly NP-hard. Most of the previous studies decompose the problem into a timetabling sub-problem and a sequencing sub-problem. Each study proposes a different sequencing and timetabling algorithm to solve the problem. In this research, this important question is aimed to be answered: is the timetabling or the sequencing algorithm more important to the effectiveness of the developed algorithm? In order to find the answer, three different sequencing algorithms are developed; a tabu search (TS), a hybrid of tabu search with variable neighbourhood search (TSVNS), and a hybrid of tabu search with particle swarm optimisation (TSPSO). Afterwards, the sequencing algorithms are combined with four different timetabling methods. All the approaches are applied to a large number of test problems available in the literature. Statistical analysis reveals that although some of the sequencing and timetabling algorithms are more complicated than the others, they are not necessarily superior to simpler algorithms. In fact, some of the simpler algorithms prove to be more effective than complicated and time-consuming methods.     

Managing information and supplies inventory operations in a manufacturing environment. Part 2: An order-timing and sizing algorithm

We develop a new, flexible independent demand forecasting-optimisation algorithm, and apply it to nine difficult-to-manage maintenance and repair products at the AREVA nuclear fuel rod manufacturing facility. The algorithm results in a 27% reduction in inventory holding and ordering costs relative to AREVA's baseline ERP method. This is in addition to improving the line item fill rates from 96 to 98%. This new algorithm is more flexible than the baseline method in that (1) our forecast error distribution is not assumed to be normal—we automatically find the best-fitting distribution from a large family of distributions, (2) we jointly optimise the order quantity and reorder point by using an optimisation routine that is embedded in a simulation methodology. Our algorithm can therefore handle a non-stationary demand process during the planning horizon, and (3) we dynamically select the best time series forecaster for demand based on the most recent history. This flexibility drove the performance improvements. Our algorithm can be easily adapted to any independent demand situation across any industry's supply chain.     

Minimising general setup costs in a two-stage production system

This paper addresses a problem arising in the coordination between two consecutive stages of a production system. Production is organised in batches of identical jobs. Each job is characterised by two distinct attributes, and all jobs sharing the same attributes are processed together as a single batch. Due to the structural and organisational characteristics of the production system, the two stages have to process the same batch sequence. When two consecutive batches with different attributes are processed, at least one stage must pay a setup, in order to reconfigure its own devices. Each stage incurs a setup cost that is a general non-decreasing function of the number of its own setups, and the problem consists of finding a batch sequence minimising the total setup costs of the production system. We present an original solution approach for the considered problem that is shown to be very effective using an extensive experimental campaign.     

A two-stage three-machine assembly scheduling problem with a position-based learning effect

The two-stage assembly scheduling problem has attracted increasing research attention. In many such problems, job processing times are commonly assumed to be fixed. However, this assumption does not hold in many real production situations. In fact, processing times usually decrease steadily when the same task is performed repeatedly. Therefore, in this study, we investigated a two-stage assembly position-based learning scheduling problem with two machines in the first stage and an assembly machine in the second stage. The objective was to complete all jobs as soon as possible (or to minimise the makespan, implying that the system can perform better and efficient task planning with limited resources). Because this problem is NP-hard, we derived some dominance relations and a lower bound for the branch-and-bound method for finding the optimal solution. We also propose three heuristics, three versions of the simulated annealing (SA) algorithm, and three versions of cloud theory-based simulated annealing algorithm for determining near-optimal solutions. Finally, we report the performance levels of the proposed algorithms.     

Divergent production scheduling with multi-process routes and common inventory

This research considers a scheduling problem in a divergent production system (DPS) where a single input item is converted into multiple output items. Therefore, the number of finished products is much larger than the number of input items. This paper addresses two important challenges in a real-life DPS problem faced by an aluminium manufacturing company. One challenge is that one product can be produced following different process routes that may have slightly different capabilities and capacities. The other is that the total inventory capacity is very limited in the company in the sense that a fixed number of inventory spaces are commonly shared by raw materials, WIP (work-in-process) items and finished products. This paper proposes a two-step approach to solving this problem. In the first step, an integer programming (IP) model is developed to plan the type and quantity of operations. In the second step, a particle swarm optimisation (PSO) is proposed to schedule the operations determined in the first step. The computational results based on actual production data have shown that the proposed two-step solution is appropriate and advantageous for the DPS scheduling problem in the company.     

Effective dynamic dispatching rule and constructive heuristic for solving single-machine scheduling problems with a common due window

This study addresses the single-machine scheduling problem with a common due window (CDW) that has a constant size and position. The objective is to minimise the total weighted earliness–tardiness penalties for jobs completed out of the CDW. To determine a schedule as close to optimum as possible, this study develops a dynamic dispatching rule and an effective constructive heuristic. The better performance of the proposed heuristic is demonstrated by comparing the results of it with those of a state-of-the-art greedy heuristic on a well-known benchmark problem set. In addition, we incorporate the constructive heuristic into a best-so-far meta-heuristic to examine the benefit of the proposed heuristic. The results show that the best known solutions in 144 out of the 250 benchmark instances are improved.     

Real-time scheduling of semi-urgent patients under waiting time targets

Semi-urgent patients arrive at an emergency department and visit the physician after triage. Patients right after triage should be served within a maximum allowable waiting time; whereas in-process patients need to be served as soon as possible to avoid adverse events. The physician must determine which one to be served next. To deal with this problem, a Markov decision process (MDP) is proposed for real-time scheduling. The wait of patients right after triage incurs a non-decreasing marginal waiting cost in their lateness, whereas the wait of in-process patients incurs linear cost function. The objective is to minimise the total weighted waiting cost. The properties of the MDP model are analysed. In the special case of long examination time and common treatment rate for all patients, we prove the multimodularity of the value function and the optimality of state-dependent threshold policies. Based on these properties, efficient heuristic policies and an approximate dynamic programming (ADP) policy are proposed. A threshold policy, which is defined by the function of expected tardiness of patients right after triage, is found to excel in all experiments, with average gaps less than 0.7% from the optimal control in small-size instances and 0.18% from ADP in real application.     

Intelligent decision support system for the adaptive control of a flexible manufacturing system with machine and tool flexibility

This paper describes an intelligent decision support system (IDSS) for real time control of a flexible manufacturing system (FMS). The controller is capable of classifying symptoms in developing the control policies on FMSs with flexibility in operation assignment and scheduling of multi-purpose machining centres which have different tools with their own efficiency. The proposed system is implemented by coupling of rule-based IDSS, simulation block and centralised simulation optimiser for elicitation of shop floor control knowledge. This posteriori adaptive controller uses a new bilateral mechanism in simulation optimiser block for offline training of IDSS based on multi-performance criteria simulation optimisation. The proposed intelligent controller receives online information of the FMS current state and trigger appropriate control rule within real-time simulation data exchange. Finally the FMS intelligent controller is validated by a benchmark test problem. Application of this adaptive controller showed that it could be an effective approach for real time control of various flexible manufacturing systems.     

Minimising schedule cost via simulation optimisation: an application in pipe manufacturing

We present a method to minimise the cost of batch schedules for a pipe manufacturing facility. The method determines the sequence of production and start date of the batch considering raw material and finished goods holding cost, late delivery cost, and changeover. Our approach is designed to interface to the company's manufacturing execution system, and uses a simplified model of the production line for speed of execution. We demonstrate that methodology results in significant cost savings when compared to existing schedules.