Minimizing makespan in a two-machine no-wait flow shop with batch processing machines

Given a set of jobs and two batch processing machines (BPMs) arranged in a flow shop environment, the objective is to batch the jobs and sequence the batches such that the makespan is minimized. The job sizes, ready times, and processing times on the two BPMs are known. The batch processing machines can process a batch of jobs as long as the total size of all the jobs assigned to a batch does not exceed its capacity. Once the jobs are batched, the processing time of the batch on the first machine is equal to the longest processing job in the batch; processing time of the batch on the second machine is equal to the sum of processing times of all the jobs in the batch. The batches cannot wait between two machines (i.e., no-wait). The problem under study is NP-hard. We propose a mathematical formulation and present a particle swarm optimization (PSO) algorithm. The solution quality and run time of PSO is compared with a commercial solver used to solve the mathematical formulation. Experimental study clearly highlights the advantages, in terms of solution quality and run time, of using PSO to solve large-scale problems.     

An improved mixed integer linear formulation and lower bounds for minimizing makespan on a flow shop with batch processing machines

This paper considers a flow shop scheduling problem with batch processing machines. Each batch processing machine has a limited capacity and can process a group of jobs, each of them having a different known capacity requirement, simultaneously. Job processing time on each machine is known and arbitrary. The processing time of a batch on each machine is the longest processing time of all jobs in the batch. We improve the only existing mixed integer linear formulation (MILF) of the problem through significant reduction in size complexity of the model. Results justify that the improved MILF is clearly more efficient in reducing the required time for obtaining optimal makespan of small-size problems, in comparison with the existing MILF. Motivated by relaxing variety of the problem assumptions, several valid lower bounds on the optimal makespan are also proposed that can furtheraccelerate obtaining optimal solution through proposed MILF. Robustness evaluation of each bound under the different problem settings is reported through computations.     

A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines

This research is motivated by our interactions with an electronics manufacturer who assembles and tests printed circuit boards (PCBs) used in consumer products. Environmental stress screening (ESS) chambers are commonly used to test PCBs to detect early failures before they are used in the field. The chambers are capable of testing multiple PCBs simultaneously (i.e., batch processing machines). The minimum testing time of each PCB and their size are known. The objective is to group these PCBs into batches and schedule the batches formed on ESS chambers such that the makespan is minimized. The ESS chambers can process a batch of jobs as long as its capacity is not violated. Each ESS chamber is unique with respect to its capacity. The problem is NP-hard. Consequently, a particle swarm optimization (PSO) algorithm is proposed. The effectiveness of the PSO algorithm is evaluated by comparing its results to a random-key genetic algorithm and a commercial solver used to solve a mixed-integer linear program. A thorough experimental study conducted indicates that the PSO algorithm reports better quality solution in a short time on larger problem instances.     

A constructive heuristic for minimizing makespan in no-wait flow shop scheduling

This paper presents a new constructive heuristic, based on the principle of job insertion, for minimizing makespan in no-wait permutation flow shop scheduling problems. Empirical results demonstrate the superiority of the proposed approach over four of the best-known methods in the literature. Analytical expressions for the total number of partial and complete sequences generated by the algorithms are derived. Statistical tests of significance substantiate the improvement in solution quality.     

Flow shop scheduling with two batch processing machines and nonidentical job sizes

A batch processing machine can process several jobs simultaneously. In this research, we consider the problem of a two-stage flow shop with two batch processing machines to minimize the makespan. We assume that the processing time of a batch is the longest processing time among all the jobs in that batch and the sizes of the jobs are nonidentical. There is a limitation on batch sizes and the sum of job sizes in a batch must be less than or equal to the machine capacity. Since this problem is strongly nondeterministic polynomial time hard, we propose two heuristic algorithms. The first one is knowledge-based and the other is based on the batch first fit heuristic proposed previously. To further enhance the solution quality, two different simulated annealing (SA) algorithms based on the two constructive heuristics is also developed. Since heuristic methods for this problem has not been proposed previously, a lower bound is developed for evaluating the performance of the proposed methods. Several test problems have been solved by SAs and lower bound method and the results are compared. Computational studies show that both algorithms provide good results but the first SA (ARSA) algorithm considerably outperforms the second one (FLSA). In addition, the results of ARSA algorithm, optimal solutions, and lower bounds are compared for several small problems. The comparisons show that except for one instance, the ARSA could find the optimal solutions and the proposed lower bound provides small gaps comparing with the optimal solutions.     

Heuristics to minimize makespan of parallel batch processing machines

Batch-processing machines can process several jobs simultaneously. These machines are commonly used to test Printed Circuit Boards (PCBs). The processing time and the dimensions of the PCB are given. Each batch is formed such that the total size of all the PCBs in the batch does not exceed the machine capacity. The batch processing time is equal to the longest processing time of all the PCBs in the batch. These batch processing machines are expensive and a bottleneck. Scheduling PCBs on these parallel batch processing machines to minimize their makespan is NP-hard. Consequently, we propose several heuristics. The performance of the proposed heuristics is compared to a simulated annealing approach and a commercial solver.     

Flow shop scheduling with multiple objective of minimizing makespan and total flow time

This paper deals with the multicriterion approach to flow shop scheduling [FSS] problems by considering makespan time and total flow time. The primary concern of flow shop scheduling is to obtain the best sequence, which minimizes the makespan, flow time, idle time, tardiness, etc. In this work, makespan and total flow time of the jobs are considered for minimization. Three heuristic algorithms namely HAMC1, HAMC2 and HAMC3 have been proposed in this paper. The effectiveness of the heuristics has been analyzed using the problems generated by Taillard [16]. The results of the problems are compared with the solution procedures proposed by Rajendran [15]. The new hybrid algorithms are developed by taking the seed sequences yielded by a method proposed by Rajendran [14] in his work to minimize flow time and improving it using search algorithm. The hybrid algorithm gives better results.     

Heuristics for makespan minimization on parallel batch processing machines with unequal job ready times

This research aims at minimizing the makespan of a set of identical batch processing machines arranged in parallel. Each job is defined by its processing time, ready time, and size. Each machine can process several jobs simultaneously as long as the machine capacity is not exceeded. The batch processing and ready times depend upon the batch composition. The batch processing time is equal to the longest processing job in the batch, and the batch ready time is equal to the largest ready time among those jobs in the batch. The problem under study is NP-hard. Consequently, a constructive heuristic is proposed and its performance with respect to solution quality and computational cost is compared against other solution approaches found in the literature. The computational experiments on a set of randomly generated instances show that the performance of the proposed heuristic is competitive with respect to solution quality and requires little computational cost.     

Lot splitting scheduling procedure for makespan reduction and machine capacity increase in a hybrid flow shop with batch production

The general definition of the hybrid flow shop (HFS) environment is a set of S?≥?2 production stages where at least one of these stages includes more than one machine, which can process one job at a time. A job can be defined as several operations to be performed by none, one, or more machines at each stage. Usually, these jobs are completed in some sequence between the different production stages, and in the case of setup activities, products are grouped in batches with buffers of work in progress between different production stages. Today, flexible production systems permit in some instances to relax job precedence constrains with alternative process cycles and to group together different batches of similar products in order to reduce setup activity incidence. On the other hand, the availability of multiple parallel machines in a single production stage makes it possible to split the lot size between different resources. This paper aims to solve the HFS scheduling problem in a flexible multistage batch production system, offering a heuristic procedure, to minimize the production makespan and increase the productive capacity utilization using a batch aggregation/splitting strategy while introducing the “workload leveling function” concept. The results are compared with other important scheduling rules widely accepted in the industry and made part of an industrial application. The company used as a test sample is an Italian rotor shaft manufacturer. The final result is illustrated to validate the proposed heuristics.     

基于最小完工期的离散型作业车间调度问题的遗传算法设计

针对离散型生产作业中的车间调度问题,以完工期最小为目标,设计了遗传算法,并利用PB语言编程实现该算法.最后,将该算法应用于某一钢铁公司金工车间的车间调度,并与原调度的结果做了比较,证明了本算法在实际应用中的有效性.     

Minimizing makespan in a group shop with fuzzy release dates and processing times

This paper deals with a fuzzy group shop scheduling problem. The group shop scheduling problem is a general formulation that includes the flow shop, the job shop, and the open shop scheduling problems. Job release dates and processing times are considered to be triangular fuzzy numbers. The objective is to find a job schedule that minimizes the maximum completion time or makespan. First, the problem is formulated in a form of fuzzy programming and then prepared in a form of deterministic mixed binary integer linear programming by applying the chance-constrained programming. To solve the problem, an efficient genetic algorithm hybridized with an improvement procedure is developed. Both Lamarckian and Baldwinian versions are then implemented and evaluated through computational experiments.     

一类解决无等待流水车间调度问题的蚁群算法

针对以最大完成时间为目标的无等待流水车间调度问题,提出了一种蚁群算法.首先,基于复杂度为O(n)的最大完成时间算法简化了适应值的计算;其次,基于当前最优解和轨迹密度的新解构造方法提高了求解质量;第三,基于快速插入邻域算法的多重插入移动提高了搜索效率;最后,基于典型算例的仿真试验,表明了所得调度算法的可行性和优越性.     

Flow shop scheduling with deteriorating jobs under dominating machines to minimize makespan

In this paper, we consider an n-job, m-machine flow shop scheduling problem with deteriorating jobs. By deteriorating jobs, we mean jobs whose processing times are an increasing function of their execution starting time. A simple linear deterioration function is assumed. When some dominant relationships between m???1 machines can be satisfied, we show that the makespan minimization problem can be solved in polynomial time.     

Coordinating scheduling with batch deliveries in a two-machine flow shop

In the demanding world of supply chain management, traditional scheduling models which only address the optimization of production sequence at certain stage are often not globally optimized. Rather, the extension, including the distribution stage following the production, can bring a more holistic view to the decision makers. This research focuses mainly on a class of two-machine flow shop problem in which jobs need to be delivered to customers by vehicles after their production stages. Two performance measures—the sum of job completion times (∑C _j ) and the makespan (C _max)—are investigated separately. For the objective of ∑C _j , this study shows that it is strongly NP-hard whether the job sizes are assumed to be equal or not. On the other hand, with regard to the C _max objective, this paper concentrates only on the problem of different job sizes and provides a proof of its NP-hardness. A heuristic method that guarantees to contain a worst-case performance ratio of 2 is developed for the C _max problem.     

Scheduling algorithms for two-stage reentrant hybrid flow shops: minimizing makespan under the maximum allowable due dates

We consider the scheduling problem in hybrid flow shops that consist of two stages in series, each of which has multiple identical parallel machines. Each job has reentrant flow, i.e., the job visits each production stage several times. The problem is to determine the allocation of jobs to machines as well as the sequence of the jobs assigned to each machine for the objective of minimizing makespan subject to the maximum allowable due dates in the form of a constraint set with a certain allowance. To solve the problem, two types of algorithms are suggested: (a) a branch and bound algorithm that gives optimal semi-permutation schedules; and (b) heuristic algorithms that give non-permutation schedules. To show their performances, computational experiments were done on a number of test problems and the results are reported. In particular, one of the heuristics is competitive to the branch and bound algorithm with respect to the solution quality while requiring much shorter computation times.     

A class of hypothesis-test-based genetic algorithms for flow shop scheduling with stochastic processing time

As an important optimisation problem with a strong engineering background, stochastic flow shop scheduling with uncertain processing time is difficult because of inaccurate objective estimation, huge search space, and multiple local minima, especially NP-hardness. As an effective meta-heuristic, genetic algorithms (GAs) have been widely studied and applied in scheduling fields, but so far seldom for stochastic cases. In this paper, a hypothesis-test method, an effective methodology in statistics, is employed and incorporated into a GA to solve the stochastic flow shop scheduling problem and to avoid premature convergence of the GA. The proposed approach is based on statistical performance and a hypothesis test. It not only preserves the global search ability of a GA, but it can also reduce repeated searches for those solutions with similar performance in a statistical sense so as to enhance population diversity and achieve better results. Simulation results based on some benchmarks demonstrate the feasibility and effectiveness of the proposed method by comparison with traditional GAs. The effects of some parameters on the performance of the proposed algorithms are also discussed .     

GRASP to minimize makespan for a capacitated batch-processing machine

This paper presents a Greedy Randomized Adaptive Search Procedure (GRASP) to minimize the makespan of a capacitated batch-processing machine. Given a set of jobs and their processing times and sizes, the objective is to group these jobs into batches and schedule the batches on a single batch-processing machine such that the time taken to complete the last batch of jobs (or makespan) is minimized. The batch-processing machine can process a batch of jobs simultaneously as long as the total size of all the jobs in that batch does not exceed the machine capacity. The batch-processing time is equal to the longest processing time for a job in the batch. It has been shown that the problem under study is non-deterministic polynomial-time hard. Consequently, a GRASP approach was developed. The solution quality of GRASP was compared to other solution approaches such as simulated annealing, genetic algorithm, and a commercial solver through an experimental study. The study helps to conclude that GRASP outperforms other solution approaches, especially on larger problem instances.     

An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling

This paper considers the permutation flow shop scheduling problem with the objective of minimizing the makespan. A new hybrid heuristic, based on simulated annealing and an improvement heuristic, is presented. The proposed hybrid heuristic uses simulated annealing in conjunction with the constructive heuristic of Nawaz et al. (Omega 11:91–95, 1983). Computational experiments carried out with the benchmark problems of Taillard (Eur J Oper Res 64:278–285, 1993) show that the proposed method produces solutions that are mostly superior to those obtained with five state-of-the-art approaches. Statistical tests of significance are used to verify the improvement in solution quality.     

A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan

This paper studies a hybrid flow shop scheduling problem (hybrid FSSP) with multiprocessor tasks, in which a set of independent jobs with distinct processor requirements and processing times must be processed in a k-stage flow shop to minimize the makespan criterion. This problem is known to be strongly nondeterministic polynomial time (NP)-hard, thus providing a challenging area for meta-heuristic approaches. This paper develops a simulated annealing (SA) algorithm in which three decode methods (list scheduling, permutation scheduling, and first-fit method) are used to obtain the objective function value for the problem. Additionally, a new neighborhood mechanism is combined with the proposed SA for generating neighbor solutions. The proposed SA is tested on two benchmark problems from the literature. The results show that the proposed SA is an efficient approach in solving hybrid FSSP with multiprocessor tasks, especially for large problems.