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.     

Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes

This paper considers the parallel batch processing machine scheduling problem which involves the constraints of unequal ready times, non-identical job sizes, and batch dependent processing times in order to sequence batches on identical parallel batch processing machines with capacity restrictions. This scheduling problem is a practical generalisation of the classical parallel batch processing machine scheduling problem, which has many real-world applications, particularly, in the aging test operation of the module assembly stage in the manufacture of thin film transistor liquid crystal displays (TFT-LCD). The objective of this paper is to seek a schedule with a minimum total completion time for the parallel batch processing machine scheduling problem. A mixed integer linear programming (MILP) model is proposed to optimise the scheduling problem. In addition, to solve the MILP model more efficiently, an effective compound algorithm is proposed to determine the number of batches and to apply this number as one parameter in the MILP model in order to reduce the complexity of the problem. Finally, three efficient heuristic algorithms for solving the large-scale parallel batch processing machine scheduling problem are also provided.     

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.     

Minimizing makespan on parallel machines with release time and machine eligibility restrictions

Scheduling in the presence of machine eligibility restrictions when not all machines can process all the jobs is a practical problem into which there has been little research. Pinedo demonstrated that the least flexible job (LFJ) rule was optimal for minimizing makespan in a parallel machine environment (with equal processing times) when there are machine eligibility restrictions, the machine eligibility sets are nested, and no release time constraint exists. The results presented in this paper demonstrate that for the more realistic case when the machine eligibility sets are not nested (with unequal processing times known when a job is released), the longest processing time (LPT) rule performs better than the LFJ rule in the presence or absence of release time stipulations. The experimental results show that the order (job selection first or machine selection first) does not matter, which is consistent with Pinedo’s observation. The new heuristics that are evaluated in this paper provide important results for the parallel machine scheduling problem and their applications in the semiconductor industry, which motivated this research.     

Minimizing makespan subject to minimum total absolute deviation of completion time on identical parallel machines

This study addresses the identical parallel machine scheduling problem with the objective of minimizing makespan subject to minimum total absolute deviation of job completion time (TADC). An optimization algorithm is first proposed to solve TADC on an identical parallel machine and an iterative procedure based on a polynomial binary integer programming model is then proposed to minimize makespan. Computational experiments show that the proposed algorithm is efficient. The worst case performance, which refers to the largest average execution for each scenario of the experiments, is 229.10 seconds for the problem with n=200, m=30 and p _j from a uniform [1, 100].     

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.     

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.     

Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families

Motivated by a bottleneck operation in an MLCC (multi-layer ceramic capacitor) production line, we study the scheduling problem of parallel batch processing machines in which a number of jobs can be processed simultaneously in a machine as a batch. Volumes of the jobs are different from each other and each job belongs to the family in which all jobs have the same processing time. In this situation, we analyse three kinds of problems whose performance measures are makespan, total completion time, and total weighted completion time, respectively. Since these problems are known to be NP-hard, we propose a number of heuristics and design genetic algorithms for the problems. Through some computational experiments, we evaluate the performances of the heuristic algorithms proposed, including the genetic algorithms for each of three problems.     

Minimising makespan on parallel machines with precedence constraints and machine eligibility restrictions

The block erection problem is defined as a parallel machine scheduling problem with precedence constraints and machine eligibility restrictions. A heuristic algorithm combined of the largest total amount of processing first rule (LTAP) and the enhanced smallest machine load first rule (ESML) is proposed to minimise makespan for the block erection in a shipyard. Finally, four lower bounds and the percentage of the reduced makespan compared with the current solutions are defined to evaluate the performance of the proposed algorithm. The experiments are performed on data selected from a shipbuilding company, and the results demonstrate that the presented algorithm can effectively find a good solution to minimise the makespan of the block erection problem.     

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.     

Minimizing total tardiness on a batch processing machine with incompatible job families

Motivated by an application in semiconductor manufacturing, we study the problem of minimizing total tardiness on a batch processing machine with incompatibl8e job families, where all jobs of the same family have identical processing times and jobs of different families cannot be processed together. We present a dynamic programming algorithm which has polynomial time complexity when the number of job families and the batch machine capacity are fixed. We also examine various heuristic solution procedures which can provide near optimal solutions in a reasonable amount of computation time.     

Modelling and symmetry breaking in scheduling problems on batch processing machines

Problems of scheduling batch-processing machines to minimise the makespan are widely exploited in the literature, mainly motivated by real-world applications, such as burn-in tests in the semiconductor industry. These problems consist of grouping jobs in batches and scheduling them on machines. We consider problems where jobs have non-identical sizes and processing times, and the total size of each batch cannot exceed the machine capacity. The processing time of a batch is defined as the longest processing time among all jobs assigned to it. Jobs can also have non-identical release times, and in this case, a batch can only be processed when all jobs assigned to it are available. This paper discusses four different versions of batch scheduling problems, considering a single processing machine or parallel processing machines and considering jobs with or without release times. New mixed integer linear programming formulations are proposed as enhancements of formulations proposed in the literature, and symmetry breaking constraints are investigated to reduce the size of the feasible sets. Computational results show that the proposed formulations have a better performance than other models in the literature, being able to solve to optimality instances only considered before to be solved by heuristic procedures.     

A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan

In this paper, we present a branch and bound algorithm for the parallel batch scheduling of jobs having different processing times, release dates and unit sizes. There are identical machines with a fixed capacity and the number of jobs in a batch cannot exceed the machine capacity. All batched jobs are processed together and the processing time of a batch is given by the greatest processing time of jobs in that batch. We compare our method to a mixed integer program as well as a method from the literature that is capable of optimally solving instances with a single machine. Computational experiments show that our method is much more efficient than the other two methods in terms of solution time for finding the optimal solution.     

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 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.     

Variable neighbourhood search for minimising tardiness objectives on flow shop with batch processing machines

This paper presents the scheduling problem on flow shop with many batch processing machines (BPM) to minimise total tardiness, maximum tardiness and number of tardy jobs, respectively. We propose an efficient variable neighbourhood search (VNS) for the problem, in which job permutation is the only optimisation object and the solutions of batch formation and batch scheduling can be directly obtained by using the permutation. To obtain the promising results, an initial solution of VNS is first produced and then one insertion operation and two swap operations are applied to improve the solution. The proposed VNS is finally tested and the computational results show its good performance on many-BPM flow shop scheduling.     

A method combining rules with genetic algorithm for minimizing makespan on a batch processing machine with preventive maintenance

This paper considers the problem of minimising makespan on a single batch processing machine with flexible periodic preventive maintenance. This problem combines two sub-problems, scheduling on a batch processing machine with jobs’ release dates considered and arranging the preventive maintenance activities on a batch processing machine. The preventive maintenance activities are flexible but the maximum continuous working time of the machine, which is allowed, is determined. A mathematical model for integrating flexible periodic preventive maintenance into batch processing machine problem is proposed, in which the grouping of jobs with incompatible job families, the starting time of batches and the preventive maintenance activities are optimised simultaneously. A method combining rules with the genetic algorithm is proposed to solve this model, in which a batching rule is proposed to group jobs with incompatible job families into batches and a modified genetic algorithm is proposed to schedule batches and arrange preventive maintenance activities. The computational results indicate the method is effective under practical problem sizes. In addition, the influences of jobs’ parameters on the performance of the method are analyzed, such as the number of jobs, the number of job families, jobs’ processing time and jobs’ release time.     

Minimizing makespan for a no-wait flowshop using genetic algorithm

This paper explains minimization of makespan or total completion time for n-jobs, m-machine, no-wait flowshop problem (NW-FSSP). A spread sheet based general purpose genetic algorithm is proposed for the NW-FSSP. The example analysis shows that the proposed approach produces results are comparable to the previous approaches cited in the literature. Additionally, it is demonstrated that the current application is a general purpose approach whereby the objective function can be tailored without any change in the logic of the GA routine.     

Closed loop control-based real-time dispatching heuristic on parallel batch machines with incompatible job families and dynamic arrivals

In this paper, a real-time closed loop control dispatching heuristic (RCLC) algorithm is proposed to address the scheduling problem of parallel batch machines with incompatible job families, limited waiting time constraints, re-entrant flow and dynamic arrivals in the diffusion and oxidation areas of a semiconductor wafer fabrication system (SWFS), which is known to be strongly NP-hard. The basis of this algorithm is the information of lots in the buffer when the parallel batch machines are idle and available. In RCLC, if the number of any family lots is less than the maximum batch size, the dispatching heuristic can be seen as a pull–pull–push–push (P⁴) strategy; otherwise, a genetic algorithm (GA). A look-itself strategy, P⁴ strategy and GA can build a closed loop control system. The experiments are implemented on the Petri nets-based real-time scheduling simulation platform of SWFS, and demonstrate the effectiveness of our proposed method.