Minimising makespan on a single batch processing machine with dynamic job arrivals and non-identical job sizes

Batch scheduling is a prevalent policy in many industries such as burn-in operations in semiconductor manufacturing and heat treatment operations in metalworking. In this paper, we consider the problem of minimising makespan on a single batch processing machine in the presence of dynamic job arrivals and non-identical job sizes. The problem under study is NP-hard. Consequently, we develop a number of efficient construction heuristics. The performance of the proposed heuristics is evaluated by comparing their results to two lower bounds, and other solution approaches published in the literature, namely the first-fit longest processing time-earliest release time (FFLPT-ERT) heuristic, hybrid genetic algorithm (HGA), joint genetic algorithm and dynamic programming (GA+DP) approach and ant colony optimisation (ACO) algorithm. The computational experiments demonstrate the superiority of the proposed heuristics with respect to solution quality, especially for the problems with small size jobs. Moreover, the computational costs of the proposed heuristics are very low.     

Minimising makespan on a batch processing machine using heuristics improved by an enumeration scheme

Batch processing machines can process several job simultaneously and are encountered in many manufacturing environments. Jobs in a batch are processed together and have the same start and end processing time. Since jobs are non-identical in job sizes and job processing times, they should be reasonably scheduled to improve the machine utilisation and processing efficiency. Two well-known heuristics, first fit longest processing time and best fit longest processing time (BFLPT), are improved in this study by considering identical job sizes and then BFLPT is further improved by an enumeration scheme proposed. Computational experiments are conducted to evaluate the performance of the improvement and the results are compared with the existing heuristics.     

Scheduling a batch processing machine with non-identical job sizes: a clustering perspective

Batch processing machines that process a group of jobs simultaneously are often encountered in semiconductor manufacturing and metal heat treatment. This paper considered the problem of scheduling a batch processing machine from a clustering perspective. We first demonstrated that minimising makespan on a single batching machine with non-identical job sizes can be regarded as a special clustering problem, providing a novel insight into scheduling with batching. The definition of WRB (waste ratio of batch) was then presented, and the objective function of minimising makespan was transformed into minimising weighted WRB so as to define the distance measure between batches in a more understandable way. The equivalence of the two objective functions was also proved. In addition, a clustering algorithm CACB (constrained agglomerative clustering of batches) was proposed based on the definition of WRB. To test the effectiveness of the proposed algorithm, the results obtained from CACB were compared with those from the previous methods, including BFLPT (best-fit longest processing time) heuristic and GA (genetic algorithm). CACB outperforms BFLPT and GA especially for large-scale problems.     

Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm

This paper studies the problem of minimising makespan in a no-wait flowshop with two batch processing machines (comprised of a parallel batch processing machine and a serial batch processing machine), non-identical job sizes and unequal ready times. We propose a population-based evolutionary method named estimation of distribution algorithm (EDA). Firstly, the individuals in the population are coded into job sequences. Then, a probabilistic model is built to generate new population and an incremental learning method is developed to update the probabilistic model. Thirdly, the best-fit heuristic is used to group jobs into batches and a least idle/waiting time approach is proposed to sequence the batches on batch processing machines. In addition, some problem-dependent local search heuristics are incorporated into the EDA to further improve the searching quality. Computational simulation and comparisons with some existing algorithms demonstrate the effectiveness and robustness of the proposed algorithm. Furthermore, the effectiveness of embedding the local search method in the EDA is also evaluated.     

Minimising makespan heuristics for scheduling a single batch machine processing machine with non-identical job sizes

In this paper, the problem of minimising maximum completion time on a single batch processing machine is studied. A batch processing is performed on a machine which can simultaneously process several jobs as a batch. The processing time of a batch is determined by the longest processing time of jobs in the batch. The batch processing machine problem is encountered in many manufacturing systems such as burn-in operations in the semiconductor industry and heat treatment operations in the metalworking industries. Heuristics are developed by iterative decomposition of a mixed integer programming model, modified from the successive knapsack problem by Ghazvini and Dupont (1998 Ghazvini, F.J. and Dupont, L. 1998. Minimising mean flow times criteria on a single batch processing machine with non-identical jobs sizes. International Journal of Production Economics, 55: 273–280. [Crossref], [Web of Science ®] , [Google Scholar], Minimising mean flow times criteria on a single batch processing machine with non-identical jobs sizes. International Journal of Production Economics 55: 273–280) and the waste of batch clustering algorithm by Chen, Du, and Huang (2011 Chen, H., Du, B. and Huang, G.Q. 2011. Scheduling a batch processing machine with non-identical job sizes: a clustering perspective. International Journal of Production Research, 49(19): 5755–5778. [Taylor &; Francis Online], [Web of Science ®] , [Google Scholar], Scheduling a batch processing machine with non-identical job sizes: a clustering perspective. International Journal of Production Research 49 (19): 5755–5778). Experimental results show that the suggested heuristics produce high-quality solutions comparable to those of previous heuristics in a reasonable computation time.     

Minimizing makespan on parallel machines with batch arrivals

Most studies in the scheduling literature assume that jobs arrive at time zero, while some studies assume that jobs arrive individually at non-zero times. However, both assumptions may not be valid in practice because jobs usually arrive in batches. In this article, a scheduling model for an identical parallel machine problem with batch arrivals is formulated. Because of the NP-hardness of the problem, a heuristic based on a simplified version of lexicographical search is proposed. To verify the heuristic, two lower bounding schemes are developed, where one lower bound is tight, and the list scheduling heuristic is compared. Extensive computational experiments demonstrate that the proposed heuristic is quite efficient in obtaining near optimal solution with an average error of less than 1.58%. The percentage improvement (from the lower bound) of the heuristic solution on the solution by the list scheduling is as large as 31.68.     

A hybrid differential evolution algorithm for a two-stage flow shop on batch processing machines with arbitrary release times and blocking

Batch processing machines (BPMs) have important applications in a variety of industrial systems. This paper considers the problem of scheduling two BPMs in a flow shop with arbitrary release times and blocking such that the makespan is minimised. The problem is formulated as a mixed integer programming model. Subsequently, a hybrid discrete differential evolution (HDDE) algorithm is proposed. In the algorithm, individuals in the population are first represented as discrete job sequences, and mutation and crossover operators are applied based on the representation. Second, after using the first-fit rule to form batches, a novel least idle/blocking time heuristic is developed to schedule the batches in the flow shop. Furthermore, an effective local search technique is embedded in the algorithm to enhance the exploitation ability. The performance of the proposed algorithm is evaluated by comparing its results to a commercial solver (CPLEX), a genetic algorithm and a simulated annealing algorithm. Computational experiments demonstrate the superiority of the HDDE algorithm in terms of solution quality, robustness and run time.     

Quantum-inspired ant colony optimisation algorithm for a two-stage permutation flow shop with batch processing machines

This paper studied two-stage permutation flow shop problems with batch processing machines, considering different job sizes and arbitrary arrival times, with the optimisation objective of minimising the makespan. The quantum-inspired ant colony optimisation (QIACO) algorithm was proposed to solve the problem. In the QIACO algorithm, the ants are divided into two groups: one group selects the largest job in terms of job size as the initial job for each batch and the other group selects the smallest job as the initial job for each batch. Each group of ants has its own pheromone matrix. In the computational experiment, our novel algorithm was compared with the hybrid discrete differential evolution (HDDE) algorithm and the batch-based hybrid ant colony optimisation (BHACO) algorithm. Although the HDDE algorithm has a shorter run time, the quality of the solution for large-scale jobs is not good, while the BHACO algorithm always obtains a better solution but requires a longer run time. The computational results show that the QIACO algorithm embedded in the quantum information has advantages in terms of both solution quality and running time.     

A genetic algorithm approach for production scheduling with mould maintenance consideration

The traditional approach for maintenance scheduling concerns single-resource (machine) maintenance during production which may not be sufficient to improve production system reliability as a whole. Besides, in the literature many researchers schedule maintenance activities periodically with fixed maintenance duration. However, in a real manufacturing system maintenance activities can be executed earlier and the maintenance duration will become shorter since less time and effort are required. A practical example is that in a plastic production system, the proportion of machine-related downtime is even lower than mould-related downtime. The planned production operations are usually interrupted seriously because of the mismatch among the maintenance periods between injection machine and mould. In this connection, this paper proposes to jointly schedule production and maintenance tasks of multi-resources in order to improve production system reliability by reducing the mismatch among various processes. To integrate machine and mould maintenance tasks in production, this paper attempts to model the production scheduling with mould scheduling (PS-MS) problem with time-dependent deteriorating maintenance schemes. The objective of this paper is to propose a genetic algorithm approach to schedule maintenance tasks jointly with production jobs for the PS-MS problem, so as to minimise the makespan of production jobs.     

Bi-objective optimisation for integrated scheduling of single machine with setup times and preventive maintenance planning

This paper deals with an integrated bi-objective optimisation problem for production scheduling and preventive maintenance in a single-machine context with sequence-dependent setup times. To model its increasing failure rate, the time to failure of the machine is subject to Weibull distribution. The two objectives are to minimise the total expected completion time of jobs and to minimise the maximum of expected times of failure of the machine at the same time. During the setup times, preventive maintenance activities are supposed to be performed simultaneously. Due to the assumption of non-preemptive job processing, three resolution policies are adapted to deal with the conflicts arising between job processing and maintenance activities. Two decisions are to be taken at the same time: find the permutation of jobs and determine when to perform the preventive maintenance. To solve this integrated problem, two well-known evolutionary genetic algorithms are compared to find an approximation of the Pareto-optimal front, in terms of standard multi-objective metrics. The results of extensive computational experiments show the promising performance of the adapted algorithms.     

A new multi-objective optimization model for preventive maintenance and replacement scheduling of multi-component systems

In this article, a new multi-objective optimization model is developed to determine the optimal preventive maintenance and replacement schedules in a repairable and maintainable multi-component system. In this model, the planning horizon is divided into discrete and equally-sized periods in which three possible actions must be planned for each component, namely maintenance, replacement, or do nothing. The objective is to determine a plan of actions for each component in the system while minimizing the total cost and maximizing overall system reliability simultaneously over the planning horizon. Because of the complexity, combinatorial and highly nonlinear structure of the mathematical model, two metaheuristic solution methods, generational genetic algorithm, and a simulated annealing are applied to tackle the problem. The Pareto optimal solutions that provide good tradeoffs between the total cost and the overall reliability of the system can be obtained by the solution approach. Such a modeling approach should be useful for maintenance planners and engineers tasked with the problem of developing recommended maintenance plans for complex systems of components.     

Single-machine group scheduling problem considering learning,forgetting effects and preventive maintenance

An integrated single-machine group scheduling model is proposed, which incorporates both learning and forgetting effects and preventive maintenance (PM) planning. The objective is to minimise the expected makespan by optimising job sequence and PM decisions. This model contains sequence-dependent set-up time, actual processing time, planned PM time and expected minimal repair time simultaneously. Based on the properties of group production, three learning functions under different circumstances are proposed to deduce the variable processing time of each part, considering the learning effect when consecutively producing identical or similar parts, together with the forgetting effect when transferring jobs interrupts the production process and makes retrogress in learning. Both run-based maintenance and minimal repair policies are specified to handle the uncertainty of machine breakdowns. The search algorithm for the model is developed, and the numerical example is studied. The computational results and sensitivity analysis show that this improved group scheduling model can well balance the machine resource requirements from different practical manufacturing-related activities.     

Ant colony optimisation algorithms for two-stage permutation flow shop with batch processing machines and nonidentical job sizes

This paper focuses on minimising the maximum completion time for the two-stage permutation flow shop scheduling problem with batch processing machines and nonidentical job sizes by considering blocking, arbitrary release times, and fixed setup and cleaning times. Two hybrid ant colony optimisation algorithms, one based on job sequencing (JHACO) and the other based on batch sequencing (BHACO), are proposed to solve this problem. First, max-min pheromone restriction rules and a local optimisation rule are embedded into JHACO and BHACO, respectively, to avoid trapping in local optima. Then, an effective lower bound is estimated to evaluate the performances of the different algorithms. Finally, the Taguchi method is adopted to investigate and optimise the parameters for JHACO and BHACO. The performances of the proposed algorithms are compared with that of CPLEX on small-scale instances and those of a hybrid genetic algorithm (HGA) and a hybrid discrete differential evolution (HDDE) algorithm on full-scale instances. The computational results demonstrate that BHACO outperforms JHACO, HDDE and HGA in terms of solution quality. Besides, JHACO strikes a balance between solution quality and run time.     

Improved evolutionary algorithm for parallel batch processing machine scheduling in additive manufacturing

With the increasing prosperity of additive manufacturing, the 3D-printing shop scheduling problem has presented growing importance. The scheduling of such a shop is imperative for saving time and cost, but the problem is hard to solve, especially for simultaneous multi-part assignment and placement. This paper develops an improved evolutionary algorithm for application to additive manufacturing, by combining a genetic algorithm with a heuristic placement strategy to take into account the allocation and placement of parts integrally. The algorithm is designed also to enhance the optimisation efficiency by introducing an initialisation method based on the characteristics of the 3D printing process through the development of corresponding time calculation model. Experiments show that the developed algorithm can find better solutions compared with state-of-the-art algorithms such as simple genetic algorithm, particle swarm optimisation and heuristic algorithms.     

Single machine scheduling with preventive maintenances

We consider the single machine total flow time problem in which the jobs are non-resumable and the machine is subject to preventive maintenance activities of known starting times and durations. We propose a branch-and-bound algorithm that employs powerful optimality properties and bounding procedures. Our extensive computational studies show that our algorithm can solve large-sized problem instances with up to 80 jobs in reasonable times. We also study a two-alternative maintenance planning problem with minor and major maintenances. We give a polynomial-time algorithm to find the optimal maintenance times when the job sequence is fixed.     

Makespan minimisation on parallel batch processing machines with non-identical job sizes and release dates

The problem we study in this paper arises from the washing step of hospital sterilisation services. Washers in the washing step are capable of handling more than one medical device set as long as their capacity is not exceeded. The medical device set sizes and arrival times to the sterilisation service may be different, but they all have the same washing duration. Thus, we model the washing step as a batch scheduling problem where medical device sets are treated as jobs with non-identical sizes and release dates, but equal processing times. The main findings we present in this paper are the following. First, we study two special cases for which polynomial algorithms are presented. We then develop a 2-approximation algorithm for the general problem. Finally, we develop a MILP model and compare it with another MILP model from the literature. Computational results show that our MILP model outperforms the model from the literature.     

Joint optimization of preventive maintenance and flexible flowshop sequence-dependent group scheduling considering multiple setups

This study focuses on a joint optimization problem regarding preventive maintenance (PM) and non-permutation group scheduling for a flexible flowshop manufacturing cell in order to minimize makespan. A mixed-integer linear programming model for the investigated problem is developed, which features the consideration of multiple setups, the relaxation of group technology assumptions, and the integration of group scheduling and PM. Based on the model, a lower bounding technique is presented to evaluate the quality of solutions. Furthermore, a genetic algorithm (GA) is proposed to improve computational efficiency. In the GA, a threshold-oriented PM policy, a hybrid crossover and a group swap mutation operator are applied. Numerical experiments are conducted on 45 test problems with various scales. The results show that the proposed model can remarkably reduce makespan. Comparative experiments reveal that the GA outperforms CPLEX, particle swarm optimization and cuckoo search with respect to effectiveness and efficiency.     

Rescheduling strategies for integrating rush orders with preventive maintenance in a two-machine flow shop

Preventive maintenance and rush orders are related. Although preventive maintenance is essential for maximising equipment reliability, it can substantially slow the manufacturing process. Rush order rescheduling involves similar conflicts. Scheduling maintains the robustness of the production schedule, but rush orders require rescheduling. Although preventive maintenance and rush orders are essential manufacturing processes, research on the integration of these functions is insufficient. Unlike recent work that analyses preventive maintenance or rush orders as separate functions, this study proposes an integrated model that analyses both preventive maintenance and rush orders in a two-machine flow shop. The model is then evaluated using two different rescheduling methods. Non-parametric analysis of the models revealed that these two rescheduling methods differ significantly under integrated maintenance and rush order situations.     

Preventive maintenance of a batch production system under time-varying operational condition

This paper proposes a dynamic opportunistic preventive maintenance (PM) strategy for a production system with a time-varying batch production pattern. The operation of such a system is generic in that the operational condition (OC) varies from batch to batch and the information about the next batch can be confirmed only upon the completion of the current batch. To accommodate time-varying OC, a modified imperfect maintenance model is developed to optimise the performance of maintenance actions that can only be performed at batch-shift points. The first study presents a PM policy for a single machine with short-term production plans. Then, a multi-machine system is studied with a goal of developing an optimum dynamic opportunistic PM strategy for a group of machines at batch-shift points. Numerical examples are proceeded to illustrate the proposed maintenance strategy in practice. The result reveals that more cost will be incurred if OC is ignored. Moreover, the proposed opportunistic PM strategy achieves the lowest total cost comparing with other strategies as the system downtime cost and maintenance cost has been jointly minimised.     

A full history proportional hazards model for preventive maintenance scheduling

This paper is concerned with the development of a realistic preventive maintenance (PM) scheduling model. A heuristic approach for implementing the semi-parametric proportional-hazards model (PHM) to schedule the next preventive maintenance interval on the basis of the equipment's full condition history is introduced. This heuristic can be used with repairable systems and does not require the unrealistic assumption of renewal during repair, or even during PM. Two PHMs are fitted, for the life of equipment following corrective work and the life of equipment following PM, using appropriate explanatory variables. These models are then used within a simulation framework to schedule the next preventive maintenance interval. Optimal PM schedules are estimated using two different criteria, namely maximizing availability over a single PM interval and over a fixed horizon. History data from a set of four pumps operating in a continuous process industry is also used to demonstrate the proposed approach. The results indicate a higher availability for the recommended schedule than the availability resulting from applying the optimal PM intervals as suggested by using the conventional stationary models. © 1997 John Wiley & Sons, Ltd.