Tabu search heuristic for two-machine flowshop with batch processing machines

Batch processing machines are frequently encountered in many industrial environments. A batch processing machine is one which can process several jobs simultaneously as a batch. The processing time of a batch is equal to the largest processing time of any job in the batch. This study deals with the problem of scheduling jobs in a flowshop with two batch processing machines such that the makespan is minimized. A heuristic based on Tabu search (TS) technique is proposed. The proposed heuristic is compared with a heuristic based on mixed integer linear programming (MILP). Because the complexity of the MILP-based heuristic is depended on the number of job batches, the comparison is under up-to-eight batches problem. In order to measure the proposed TS-based heuristic in larger batch problem, the relative error percentage with the lower bound (REP_LB) is used. The results show that the proposed heuristic is efficient and effective for the problems with relative large job sizes.     

A heuristic procedure for the integrated facility layout design and flow assignment problem

We present an efficient iterative heuristic procedure for solving the integrated layout design and product flow assignment problem. The layout design decisions involve planar location of unequal-area machines with duplicates. The product flows are assigned to machines according to the product processing routes. The integrated decision problem is a nonlinear mixed integer model which cannot be efficiently solved using classical methods for large problems. We propose a novel integrated heuristic procedure based on the alternating heuristic, a perturbation algorithm and sequential location heuristic. Since the alternating heuristic between facility layout design and product-machine assignment sub-problems terminates with local optima, we developed a perturbation algorithm based on assignment decisions. The results of an experimental study show that proposed procedure is both efficient and effective in identifying quality solutions for small to very large-sized problems.     

Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing

This paper aims at minimizing the makespan of two batch-processing machines in a flow shop. The processing times and the sizes of the jobs are known and non-identical. The machines can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time among all the jobs in that batch. The problem under study is NP-hard for makespan objective. Consequently, a heuristic based on Johnson's algorithm and a simulated annealing (SA) algorithm is proposed. Random instances were generated to verify the effectiveness of the proposed approaches. The results obtained from SA were compared with the proposed heuristic and a commercial solver. The SA outperformed both the heuristic and the commercial solver. On larger problem instances, the heuristic outperformed the commercial solver.     

A heuristic method for two-stage hybrid flow shop with dedicated machines

This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines, in which the first stage contains a single common critical machine, and the second stage contains several dedicated machines. Each job must be first processed on the critical machine in stage one and depending on the job type, the job will be further processed on the dedicated machine of its type in stage two. The objective is to minimize the makespan. To solve the problem, a heuristic method based on branch and bound (B&B) algorithm is proposed. Several lower bounds are derived and four constructive heuristics are used to obtain initial upper bounds. Then, three dominance properties are employed to enhance the performance of the proposed heuristic method. Extensive computational experiments on two different problem categories each with various problem configurations are conducted. The results show that the proposed heuristic method can produce very close-to-optimal schedules for problems up to 100 jobs and five dedicated machines within 60 s. The comparisons with solutions of two other meta-heuristic methods also prove the better performance of the proposed heuristic method.     

An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time

We address the two-stage multi-machine assembly scheduling problem. The first stage consists of m independently working machines where each machine produces its own component. The second stage consists of two independent and identical assembly machines. The objective is to come up with a schedule that minimizes total or mean completion time for all jobs. The problem has been addressed in the scheduling literature and several heuristics have been proposed. In this paper, we propose a new heuristic called artificial immune system (AIS). We conduct experimental analysis for comparing the newly proposed heuristic AIS with the best known heuristic in the literature. Experimental results show that our proposed heuristic AIS performs better than the best known existing heuristic. More specifically, our new heuristic AIS reduces the error of the best known heuristic by 60% while the computational times of both AIS and the best known heuristic are almost the same.     

A note: Simple heuristics for scheduling a maintenance activity on unrelated machines

Following several recent papers discussing various problems of scheduling a maintenance activity, we focus here on scheduling a maintenance activity on unrelated parallel machines. The objective is to minimize flow-time. In the basic setting, we assume that all the machines must be maintained simultaneously. The problem is known to be NP-hard, and we introduce and test numerically an efficient heuristic and a lower bound, both based on a solution of a matching problem. We also study the relaxed version, where the machines are not restricted to be maintained at the same time. Similar heuristic and lower bound are proposed and tested.     

公共交货期窗口下提前/拖期问题的多机调度算法

提出了求公共交货期窗口下提前／拖期都有惩罚的单机零件排序问题最优解的新算法,建立了相应多机零件排序问题的数学模型。在证明关于单机问题最优排序和最优公共交货期性质的若干定理的基础上,给出了求解多机问题的一个启发式算法。数值例子表明,该算法有较为理想的优化效果和工程实用价值。     

A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources

In this paper, a heuristic is proposed for solving the problem of scheduling in a two-stage flowshop with parallel unrelated machines and additional renewable resources at the first stage and a single machine at the second stage. Resource requirements are arbitrary integers. The availability of additional resources is limited at every moment. The objective is the minimization of makespan. The problem is NP-hard. The proposed heuristic combines column generation technique with a genetic algorithm (the heuristic algorithm HG) or a simulated annealing algorithm (the heuristic algorithm HS). The performance analysis is performed experimentally by comparing heuristic solutions to the lower bound on the optimal makespan. Results of the computational experiment show that both the heuristic algorithms yield good quality solutions using reasonable computation time and that HS outperforms HG for the most difficult problems.     

Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines

This article addresses a multi-stage flow shop scheduling problem with unrelated parallel machines. Some practical processing restrictions such as independent setup and dependent removal times are taken into account as well. The objective is to minimize total flow time in the system. A simulated annealing (SA)-based heuristic is proposed to solve the addressed problem in a reasonable running time. The heuristic begins on a well-designed initial solution generator; then a simulated annealing procedure is applied for further improvement of the solution. To assure the quality and efficiency of the solution for the proposed SA-based heuristic, certain mechanisms are developed and introduced into the heuristic. The computational experimental results show that the proposed SA-based heuristic performs well with respect to accuracy and efficiency of solution.     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

A new heuristic for scheduling the two-stage flowshop with additional resources

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machine at the second stage. At the first stage, jobs use some additional resources which are available in limited quantities at any time. The resource requirements are of 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which solve to optimality the resource constrained scheduling problem at the first stage of the flowshop, and at the same time, minimize the makespan in the flowshop by selecting appropriate jobs for simultaneous processing. Several rules of job selection are considered. The performance of the proposed heuristic algorithms is analyzed by comparing solutions with the lower bound on the optimal makespan. The extensive computational experiment shows that the proposed heuristic algorithms are able to produce near-optimal solutions in short computational time.     

Shortest path based simulated annealing algorithm for dynamic facility layout problem under dynamic business environment

This paper studies a new kind of dynamic multi-stage facility layout problem under dynamic business environment, in which new machines may be added into, or old machines may be removed from the plant. We define this problem first on the basis of unequal area machines and continual presentation of layouts. Compared with nodes and arcs of the flow chart, we convert this problem into a shortest path problem by studying its cost function and machine adding/removing heuristic rules, and the corresponding mathematical model for this problem is established. An auction algorithm is proposed here to solve the shortest path problem. Finally, a shortest path based simulated annealing algorithm is presented to solve the optimization problem. Parameters of the SP based SA algorithm are discussed to improve the performance of the algorithm. Some cases are used to verify the proposed algorithm.     

Minimizing makespan in a two-stage system with flowshop and open shop

This paper studies two models of two-stage processing with flowshop at the first stage followed by open shop at the second stage. The first model involves multiple machines at the first stage and two machines at the second stage, and the other involves multiple machines at both stages. In both models, the objective is to minimize the makespan. This problem is NP-complete, for which an efficient heuristic solution algorithm is constructed and its worst-case performance guarantee is analyzed for both models. An integer programming model and a branch and bound algorithm are proposed for model 1 and a lower bound is developed for model 2 as benchmarks for the heuristic algorithms. Computational experiences show that the heuristic algorithms consistently generate good schedule and the branch and bound algorithm is much efficient than the integer-programming model.     

一种基于虚拟截止时间制导的改进的Min-Min元任务调度算法

在网格环境下,资源状况和用户行为相当复杂,是一个异构计算环境,元任务（meta—task）调度比传统并行调度更为复杂。如何映射一组任务到一组机器上被证明是NP问题,其目的一般是最小化任务完成时间（makespan）。为解决这一问题,已经提出一些启发式任务调度算法,例如具有代表性的MinMin元任务调度算法。本文在Min-Min元任务调度算法的基础上,通过虚拟截止时间制导的方法来改进Min-Min算法。实验结果表明,本文提出的算法具有更短的任务完成时间。     

An effective heuristic for flexible job-shop scheduling problem with maintenance activities

Most production scheduling problems, including the standard flexible job-shop scheduling problem (FJSP), assume that machines are continuously available. However, in most realistic situations, machines may become unavailable during certain periods due to preventive maintenance (PM). In this paper, a flexible job-shop scheduling problem with machine availability constraints is considered. Each machine is subject to preventive maintenance during the planning period and the starting times of maintenance activities are either flexible in a time window or fixed beforehand. Moreover, two cases of maintenance resource constraint are considered: sufficient maintenance resource available or only one maintenance resource available. To deal with this variant FJSP problem with maintenance activities, a filtered beam search (FBS) based heuristic algorithm is proposed. With a modified branching scheme, the machine availability constraint and maintenance resource constraint can be easily incorporated into the proposed algorithm. Simulation experiments are conducted on some representative problems. The results demonstrate that the proposed filtered beam search based heuristic algorithm is a viable and effective approach for the FJSP with maintenance activities.     

Heuristic algorithms for preemptive scheduling in a two-stage hybrid flowshop with additional renewable resources at each stage

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines and renewable resources at both the stages. The resource requirements are of a 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Four heuristic algorithms using linear programming are proposed for solving this problem. Performance of the algorithms is analyzed experimentally by comparing heuristic solutions with the lower bound on the optimal makespan. Statistical comparative analysis of the developed algorithms is carried out. The results of a computational experiment show that the proposed algorithms are able to produce good quality solutions in a small amount of computation time.     

Flowshop scheduling problems with transportation or deterioration between the batching and single machines

In this paper, we consider two new types of the two-machine flowshop scheduling problems where a batching machine is followed by a single machine. The first type is that normal jobs with transportation between machines are scheduled on the batching and single machines. The second type is that normal jobs are processed on the batching machine while deteriorating jobs are scheduled on the single machine. For the first type, we formulate the problem to minimize the makespan as a mixed integer programming model and prove that it is strongly NP-hard. Furthermore, a heuristic algorithm along with a worst case error bound is derived and the computational experiments are also carried out to verify the effectiveness of the proposed heuristic algorithm. For the second type, the two objectives are considered. For the problem with minimizing the makespan, we find an optimal polynomial algorithm. For the problem with minimizing the sum of completion time, we show that it is strongly NP-hard and propose an optimal polynomial algorithm for its special case.     

Heuristic algorithms for preemptive scheduling in a two-stage hybrid flowshop with additional renewable resources at each stage

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines and renewable resources at both the stages. The resource requirements are of a 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Four heuristic algorithms using linear programming are proposed for solving this problem. Performance of the algorithms is analyzed experimentally by comparing heuristic solutions with the lower bound on the optimal makespan. Statistical comparative analysis of the developed algorithms is carried out. The results of a computational experiment show that the proposed algorithms are able to produce good quality solutions in a small amount of computation time.     

Completion time variance minimization in single machine and multi-machine systems

In this paper we consider the problem of minimizing the completion time variance of n jobs on a single machine with deterministic processing times. We propose a new heuristic and compare the results with existing popular heuristics for the problem. We also propose a method based on genetic algorithms to solve the problem. We present the worst case performance analysis of the proposed heuristic. We also consider the problem of minimizing the completion time variance of n jobs on m identical parallel machines in both restricted and unrestricted versions. A heuristic method and a method based on genetic algorithms are presented for both the cases and results of computational testing are provided. It is concluded that the proposed methods provide better results compared to existing methods for the single machine case as well as for the multi-machine case.     

A computational evaluation of constructive and improvement heuristics for the blocking flow shop to minimise total flowtime

This paper focuses on the blocking flow shop scheduling problem with the objective of total flowtime minimisation. This problem assumes that there are no buffers between machines and, due to its application to many manufacturing sectors, it is receiving a growing attention by researchers during the last years. Since the problem is NP-hard, a large number of heuristics have been proposed to provide good solutions with reasonable computational times. In this paper, we conduct a comprehensive evaluation of the available heuristics for the problem and for related problems, resulting in the implementation and testing of a total of 35 heuristics. Furthermore, we propose an efficient constructive heuristic which successfully combines a pool of partial sequences in parallel, using a beam-search-based approach. The computational experiments show the excellent performance of the proposed heuristic as compared to the best-so-far algorithms for the problem, both in terms of quality of the solutions and of computational requirements. In fact, despite being a relative fast constructive heuristic, new best upper bounds have been found for more than 27% of Taillard’s instances.