Flowshop scheduling problem with a batching machine and task compatibilities

This paper deals with the problem of task scheduling in a flowshop with two (discrete and batching) machines. Each task has to be processed by both machines. All tasks visit the machines in the same order. The first machine is a discrete machine that can process no more than one task at a time, and the second machine is a batching machine that can process several tasks per batch with the additional feature that the tasks of the same batch have to be compatible. A compatibility relation is defined between each pair of tasks, so that an undirected compatibility graph is obtained which turns out to be an interval graph. The batch processing time is equal to the maximal processing time of the tasks in this batch and all tasks of the same batch start and finish together. The aim is to make batching and sequencing decisions and minimize the makespan.     

Makespan minimization in a no-wait flow shop problem with two batching machines

This paper deals with the problem of task scheduling in a no-wait flowshop with two batching machines. Each task has to be processed by both machines. All tasks visit the machines in the same order. Batching machines can process several tasks per batch so that all tasks of the same batch start and complete together. The batch processing time for the first machine is equal to the maximal processing time of the tasks in this batch, and for the second machine is equal to the sum of the processing times of the tasks in this batch. We assume that the capacity of any batch on the first machine is bounded, and that when a batch is completed on the first machine it is immediately transferred to the second machine. The aim is to make batching and sequencing decisions that allow the makespan to be minimized.     

Batching and scheduling in a multi-machine flow shop

We study the problem of batching and scheduling n jobs in a flow shop comprising m, m≥2, machines. Each job has to be processed on machines 1,…,m in this order. Batches are formed on each machine. A machine dependent setup time precedes the processing of each batch. Jobs of the same batch are processed on each machine sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs of the same batch formed on machine l become available for a downstream operation on machine l+1 at the same time when the processing of the last job of the batch on machine l has been finished. The objective is to minimize maximum job completion time. We establish several properties of an optimal schedule and develop polynomial time algorithms for important special cases. They are improvements over the existing methods with regard to their generality and time efficiency.     

Scheduling a batching machine with convex resource consumption functions

In various industries jobs undergo a batching, or burn in, process where different tasks are grouped into batches and processed simultaneously. The processing time of each batch is equal to the longest processing time among all jobs contained in the batch. All to date studies dealing with batching machines have considered fixed job processing times. However, in many real life applications job processing times are controllable through the allocation of a limited resource. The most common and realistic model assumes that there exists a non-linear and convex relationship between the amount of resource allocated to a job and its processing time. The scheduler?s task when dealing with controllable processing times is twofold. In addition to solving the sequencing problem, one must establish an optimal resource allocation policy. We combine these two widespread models on a single machine setting, showing that both the makespan and total completion time criteria can be solved in polynomial time. We then show that our proposed approach can be applied to general bi-criteria objective comprising of the makespan and the total completion time.     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure

A batch processing machine can simultaneously process several jobs forming a batch. This paper considers the problem of scheduling jobs with non-identical capacity requirements, on a single-batch processing machine of a given capacity, to minimize the makespan. The processing time of a batch is equal to the largest processing time of any job in the batch. We present some dominance properties for a general enumeration scheme and for the makespan criterion, and provide a branch and bound method. For large-scale problems, we use this enumeration scheme as a heuristic method.Scope and purposeUsually in classical scheduling problems, a machine can perform only one job at a time. Although, one can find machines that can process several jobs simultaneously as a batch. All jobs of a same batch have common starting and ending times. Batch processing machines are encountered in many different environments, such as burn-in operations in semiconductor industries or heat treatment operations in metalworking industries. In the first case, the capacity of the machine is defined by the number of jobs it can hold. In the second case, each job has a certain capacity requirement and the total size of a batch cannot exceed the capacity of the machine. Hence, the number of jobs contained in each batch may be different. In this paper, we consider this second case (which is more difficult) and we provide an exact method for the makespan criterion (minimizing the last ending time).     

Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times

This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.     

An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes

In this paper we consider the problem of scheduling parallel batching machines with jobs of arbitrary sizes. The machines have identical capacity of size and processing velocity. The jobs are processed in batches given that the total size of jobs in a batch cannot exceed the machine capacity. Once a batch starts processing, no interruption is allowed until all the jobs are completed. First we present a mixed integer programming model of the problem. We show the computational complexity of the problem and optimality properties. Then we propose a novel ant colony optimization method where the Metropolis Criterion is used to select the paths of ants to overcome the immature convergence. Finally, we generate different scales of instances to test the performance. The computational results show the effectiveness of the algorithm, especially for large-scale instances.     

极小化最大完工时间的单机连续型批调度问题

从钢铁工业中加热炉对管坯的加热过程,提出一种新的连续型批处理机调度问题,与传统批处理机调度问题的批进批出方式不同,其主要特征为批中工件的进入、处理和离开都连续进行,批B_i的处理时间与该批的大小|B_i|、批中工件T_j的处理时间p_j及机器的容量C都有关,表示为p^{(i)}=\dmax_{T_j\in B_i}\{p_j\}(1+\displaystyle\frac{|B_i|-1}{C}).对于极小化最大完工时间问题,给出了一个复杂性为O(n^2)的动态规划算法,并证明了这个算法的最优性.     

Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times

This research is motivated by a scheduling problem found in the diffusion and oxidation areas of semiconductor wafer fabrication, where the machines can be modeled as parallel batch processors. We attempt to minimize total weighted tardiness on parallel batch machines with incompatible job families and unequal ready times of the jobs. Given that the problem is NP-hard, we propose two different decomposition approaches. The first approach forms fixed batches, then assigns these batches to the machines using a genetic algorithm (GA), and finally sequences the batches on individual machines. The second approach first assigns jobs to machines using a GA, then forms batches on each machine for the jobs assigned to it, and finally sequences these batches. Dispatching and scheduling rules are used for the batching phase and the sequencing phase of the two approaches. In addition, as part of the second decomposition approach, we develop variations of a time window heuristic based on a decision theory approach for forming and sequencing the batches on a single machine.     

A simultaneous and iterative approach for parallel machine scheduling with sequence-dependent family setups

In this paper, we address a parallel machine scheduling problem to minimize the total weighted completion time, where product families are involved. Major setups occur when processing jobs of different families, and sequence dependencies are also taken into account. Considering its high practical relevance, we focus on the special case where all jobs of the same family have identical processing times. In order to avoid redundant setups, batching jobs of the same family can be performed. We first develop a variable neighborhood search algorithm (VNS) to solve the interrelated subproblems in a simultaneous manner. To further reduce computing time, we also propose an iterative scheme which alternates between a specific heuristic to form batches and a VNS scheme to schedule entire batches. Computational experiments are conducted which confirm the benefits of batching. Test results also show that both simultaneous and iterative approach outperform heuristics based on a fixed batch size and list scheduling. Furthermore, the iterative procedure succeeds in balancing solution quality and computing time.     

An Enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes

This paper addresses a sequence- and machine-dependent batch scheduling problem on a set of unrelated-parallel machines where the objective is to minimize a linear combination of total weighted completion time and total weighted tardiness. In particular, batch scheduling disregards the group technology assumptions by allowing for the possibility of splitting pre-determined groups of jobs into batches with respect to desired lower bounds on batch sizes. With regard to bounds on batch sizes, the MILP model is developed as two integrated batching and scheduling phases to present the problem. A benchmark of small-size instances on group scheduling shows the superior performance of batch scheduling up to 37% reduction in the objective function value. An efficient meta-heuristic algorithm based on tabu search with multi-level diversification and multi-tabu structure is developed at three levels, which moves back and forth between batching and scheduling phases. To eliminate searching in ineffective neighborhoods and thus enhance computational efficiency of search algorithms, several lemmas are proposed and proven. The results of applying lemmas reflect up to 40% reduction in computational times. Comparing the optimal solutions found by CPLEX and tabu search shows that the tabu search algorithm could find solutions, at least as good as CPLEX but in incredibly shorter computational time. In order to trigger the search algorithm, two different initial solution finding mechanisms have been developed and implemented. Also, due to lack of a qualified benchmark for unrelated-parallel machines, a comprehensive data generation mechanism has been developed in a way that it fairly reflects the real world situations encountered in practice. The machine availability times and job release times are considered to be dynamic and the run time of each job differs on different machines based upon the capability of the machines.     

A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.     

批处理机上具有两类释放时间的工件集竞争调度问题

研究了两个工件集合竞争在一台批处理机上加工的调度问题,其中每个集合的工件具有一个共同的释放时间.批处理机可以同时加工多个工件作为一批,每批的加工时间为该批工件中加工时间的最大值.基于两类释放时间的大小,针对无界批处理机上最小化一个集合工件的最大完工时间、最大延迟以及总完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,分别给出了最优求解方法.针对有界批处理机上最小化一个集合工件的最大完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,证明为一般意义NP-难问题,并给出伪多项式时间最优求解方法.     

A GRASP approach for makespan minimization on parallel batch processing machines

In this paper we consider the problem of scheduling a set of identical batch processing machines arranged in parallel. A Greedy Randomized Adaptive Search Procedure (GRASP) approach is proposed to minimize the makespan under the assumption of non-zero job ready times, arbitrary job sizes and arbitrary processing times. Each machine can process simultaneously several jobs as a batch as long as the machine capacity is not violated. The batch processing time is equal to the largest processing time among those jobs in the batch. Similarly, the batch ready time is equal to the largest ready time among those jobs in the batch. The performance of the proposed GRASP approach was evaluated by comparing its results to a lower bound and heuristics published in the literature. Experimental study suggests that the solution obtained from the GRASP approach is superior compared to other heuristics.     

Mean value analysis of re-entrant line with batch machines and multi-class jobs

We propose an approximate approach for estimating the performance measures of the re-entrant line with single-job machines and batch machines based on the mean value analysis (MVA) technique. Multi-class jobs are assumed to be processed in predetermined routings, in which some processes may utilize the same machines in the re-entrant fashion. The performance measures of interest are the steady-state averages of the cycle time of each job class, the queue length of each buffer, and the throughput of the system. The system may not be modeled by a product form queueing network due to the inclusion of the batch machines and the multi-class jobs with different processing times. Thus, we present a methodology for approximately analyzing such a re-entrant line using the iterative procedures based upon the MVA and some heuristic adjustments. Numerical experiments show that the relative errors of the proposed method are within 5% as compared against the simulation results.Scope and purposeWe consider a re-entrant shop with multi-class jobs, in which jobs may visit some machines more than once at different stages of processing, as observed in the wafer fabrication process of semiconductor manufacturing. The re-entrant line also consists of both the single-job machine and the batch machine. The former refers to the ordinary machine processing one job at a time, and the latter means the machine processing several jobs together as a batch at a time. In this paper, we propose an approximation method based on the mean value analysis for estimating the mean cycle time of each class of jobs, the mean queue length of each buffer, and the throughput of the system.     

An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes

This paper addresses the problem of scheduling jobs with non-identical sizes on a single batch processing machine. A batch processing machine is one which can process multiple jobs simultaneously as a batch as long as the total size of jobs being processed does not exceed the machine capacity. The batch processing time is equal to the longest processing time among all jobs in the batch. For the simultaneous minimization of the bi-criteria of makespan and maximum tardiness, we propose two different multi-objective genetic algorithms based on different representation schemes. While the first algorithm do search via generating sequences of jobs using genetic operators and then batching jobs keeping their order in the sequence, the second algorithm uses the idea of generating batches of jobs directly using genetic operators and ensures feasibility through using heuristic procedures. The type of representation used in the second algorithm allows introducing heuristics with the ability of biasing the search towards each objective and also allows hybridization with a local search heuristic that gives the ability of finding Pareto-optimal or locally efficient Pareto-solutions. Computational results show that the non-dominated solutions obtained by the latter algorithm are very superior in closeness to the true Pareto-optimal solutions and to keep diversity in the obtained Pareto-set, as the problem size increases.     

The impact of OPT and TPM on the economic production quantity

In manufacturing systems, the material flow is influenced by a number of factors, such as batching policies, capacity of machines, machine breakdowns, etc. Realizing the role of batching policies and reliability of machines in production systems, a mathematical model is presented here for determining optimal batching policies with the objective of improving the speed of material flow considering machine breakdowns and batch splitting and forming. This model is employed for studying (i) the significance of total preventive maintenance (TPM); (ii) the use of the optimized production technology (OPT) concept in batching policies; and (iii) the influence of a set-up cost reduction programme on the performance of manufacturing systems. The basic criterion considered for optimizing the batch sizes is the minimization of total system cost (TSC). An example problem is solved to explain the application of the model.     

Using genetic algorithm for lot sizing and scheduling problem with arbitrary job volumes and distinct job due date considerations

This paper considers an integrated lot sizing and scheduling problem for a production–distribution environment with arbitrary job volumes and distinct due dates considerations. In the problem, jobs are firstly batch processed on a batching machine at production stage and then delivered to a pre-specified customer at the subsequent delivery stage by a capacitated vehicle. Each job is associated with a distinct due date and a distinct volume, and has to be delivered to the customer before its due date, i.e. delay is not allowed. The processing time of a batch is a constant independent of the jobs it contains. In production, a constant set-up time as well as a constant set-up cost is required before the first job of this batch is processed. In delivery, a constant delivery time as well as a constant delivery cost is needed for each round-trip delivery between the factory and the customer. Moreover, it is supposed that a job that arrives at the customer before its due date will incur a customer inventory cost. The objective is to find a coordinated lot sizing and scheduling scheme such that the total cost is minimised while guaranteeing a certain customer service level. A mixed integer formulation is proposed for this problem, and then a genetic algorithm is developed to solve it. To evaluate the performance of the proposed genetic algorithm, a lower bound on the objective value is established. Computational experiments show that the proposed genetic algorithm performs well on randomly generated problem instances.     

Scheduling unrelated parallel batch processing machines with non-identical job sizes

Scheduling unrelated parallel batch processing machines to minimize makespan is studied in this paper. Jobs with non-identical sizes are scheduled on batch processing machines that can process several jobs as a batch as long as the machine capacity is not violated. Several heuristics based on best fit longest processing time (BFLPT) in two groups are proposed to solve the problem. A lower bound is also proved to evaluate the quality of the heuristics. Computational experiments were undertaken. These showed that J_SC-BFLPT, considering both load balance of machines and job processing times, was robust and outperformed other heuristics for most of the problem categories.