Heuristic search algorithms for lot streaming in a two-machine flowshop

The objective of this paper is to propose and evaluate heuristic search algorithms for a two-machine flowshop problem with multiple jobs requiring lot streaming that minimizes makespan. A job here implies many identical items. Lot streaming creates sublots to move the completed portion of a production lot to second machine. The three heuristic search algorithms evaluated in this paper are Baker’s approach (Baker), genetic algorithm (GA) and simulated annealing (SA) algorithm. To create neighborhoods for SA, three perturbation schemes, viz., pair-wise exchange, insertion and random insertion are used, and the performance of these on the final schedule is also compared. A wide variety of data sets is randomly generated for comparative evaluation. The parameters for GA and SA are obtained after conducting sensitivity analysis. The genetic algorithm is found to perform well for lot streaming in the two-machine flowshop scheduling.     

Mathematical model and parallel genetic algorithm for hybrid flexible flowshop lot streaming problem

Lot streaming is the technique of splitting a given job into sublots to allow the overlapping of successive operations in multi-stage manufacturing systems thereby reducing production makespan. Several research articles appeared in literature to solve this problem and most of these studies are limited to pure flowshop environments where there is only a single machine in each stage. On the other hand, because of the applicability of hybrid flowshops in different manufacturing settings, the scheduling of these types of shops is also extensively studied by several authors. However, the issue of lot streaming in hybrid flowshop environment is not well studied. In this paper, we aim to contribute in bridging the gap between the research efforts in flowshop lot streaming and hybrid flowshop scheduling. We propose a mathematical model and a genetic algorithm for the lot streaming problem of several jobs in multi-stage flowshops where at each stage there are unrelated parallel machines. The jobs may skip some of the stages, and therefore, the considered system is a complex generalized flowshop. The proposed genetic algorithm is executed on both sequential and parallel computing platforms. Numerical examples showed that the parallel implementation greatly improved the computational performance of the developed heuristic.     

Scheduling in Kanban-Controlled Flowshops to Minimise the Makespan of Containers

In this paper we deal with the problem of scheduling in a kanban-controlled flowshop with material handling and finite input and output buffer storage between workstations. The objective is to minimise the makespan of containers. A heuristic algorithm, based on the simulated annealing (SA) technique, is developed. We present a new perturbation scheme and test the effectiveness of the proposed simulated annealing algorithm for solving the kanban-controlled flowshop scheduling problems. The proposed SA algorithm is evaluated relative to the existing heuristic. The results of the computational evaluation reveal that the proposed SA algorithm performs better than the existing heuristic. ID="A1"Correspondance and offprint requests to: Dr C. Rajendran, Department of Humanities and Social Sciences IIT Madras, Chennai-600 036, India. E-mail: craj@iitm.ac.in     

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.     

APPLYING PARTICLE SWARM OPTIMIZATION TO JOB-SHOPSCHEDULING PROBLEM

A new heuristic algorithm is proposed for the problem of finding the minimum makespan in the job-shop scheduling problem. The new algorithm is based on the principles of particle swarm optimization (PSO). PSO employs a collaborative population-based search, which is inspired by the social behavior of bird flocking. It combines local search (by self experience) and global search (by neighboring experience), possessing high search efficiency. Simulated annealing (SA) employs certain probability to avoid becoming trapped in a local optimum and the search process can be controlled by the cooling schedule. By reasonably combining these two different search algorithms, a general, fast and easily implemented hybrid optimization algorithm, named HPSO, is developed. The effectiveness and efficiency of the proposed PSO-based algorithm are demonstrated by applying it to some benchmark job-shop scheduling problems and comparing results with other algorithms in literature. Comparing results indicate that PSO-based a     

An improved artificial bee colony algorithm for the blocking flowshop scheduling problem

This paper presents an improved artificial bee colony (IABC) algorithm for solving the blocking flowshop problem with the objective of minimizing makespan. The proposed IABC algorithm utilizes discrete job permutations to represent solutions and applies insert and swap operators to generate new solutions for the employed and onlooker bees. The differential evolution algorithm is employed to obtain solutions for the scout bees. An initialization scheme based on the problem-specific heuristics is presented to generate an initial population with a certain level of quality and diversity. A local search based on the insert neighborhood is embedded to improve the algorithm's local exploitation ability. The IABC is compared with the existing hybrid discrete differential evolution and discrete artificial bee colony algorithms based on the well-known flowshop benchmark of Taillard. The computational results and comparison demonstrate the superiority of the proposed IABC algorithm for the blocking flowshop scheduling problems with makespan criterion.     

A particle swarm optimization for multi-objective flowshop scheduling

The academic approach of single-objective flowshop scheduling has been extended to multiple objectives to meet the requirements of realistic manufacturing systems. Many algorithms have been developed to search for optimal or near-optimal solutions due to the computational cost of determining exact solutions. This paper provides a particle swarm optimization-based multi-objective algorithm for flowshop scheduling. The proposed evolutionary algorithm searches the Pareto optimal solution for objectives by considering the makespan, mean flow time, and machine idle time. The algorithm was tested on benchmark problems to evaluate its performance. The results show that the modified particle swarm optimization algorithm performed better in terms of searching quality and efficiency than other traditional heuristics.     

Metaheuristics for scheduling a no-wait flowshop manufacturing cell with sequence-dependent family setups

This paper examines the no-wait flowshop manufacturing cell scheduling problem (FMCSP) with sequence-dependent family setup times. To the best of our knowledge, the present study is among the first to investigate FMSCPs with no-wait consideration, though it is a necessary production constraint in many real-world applications. In view of the strongly NP-hard nature of this problem, three metaheuristic-based algorithms were proposed and empirically evaluated for effectively finding optimal schedules. The experimental results demonstrate that the proposed algorithms are effective and efficient at finding good quality solutions for the FMCSP with makespan criterion.     

JIT柔性混合流水车间生产调度问题研究

针对混合柔性流水车间多种工艺路线的生产调度问题,分析了生产工艺计划与车问调度系统的集成原理,建立目标模型,通过将简单遗传算法加以改进,在建立集成模型的基础上,对算法进行研究,把进化后的遗传算法（SGA）和改进的模拟退火算法（SA）有机结合,使算法优化机制融合和优化结构互补,形成较为高效的混合优化算法,并对问题进行求解。最后给出了一个具体算例,验证算法的有效性和先进性。     

A multi-objective electromagnetism algorithm for a bi-objective hybrid no-wait flowshop scheduling problem

This article studies multi-objective hybrid no-wait flowshop scheduling problems to minimize both makespan and total tardiness. This article mathematically formulates the problem using an effective multi-objective mixed integer linear programming models. Since the problem is NP-hard and it is difficult to find an optimal solution in a reasonable computational time, an efficient multi-objective electromagnetism algorithm (MOEA) is presented as the solution procedure. Electromagnetism algorithm is known as a flexible and effective population-based algorithm utilizing an attraction/repulsion mechanism to move the particles towards optimality. MOEA is carefully evaluated for its performance against multi-objective immune algorithms and the adaptation of a well-known multi-objective simulated annealing in the relevant literature by means of multi-objective performance measures and statistical tools. The results show that the proposed solution method outperforms the others.     

A hybrid genetic algorithm for solving no-wait flowshop scheduling problems

A hybrid genetic algorithm is proposed in this paper to minimize the makespan and the total flowtime in the no-wait flowshop scheduling problem, which is known to be NP-hard for more than two machines. The Variable Neighborhood Search is used as an improvement procedure in the last step of the genetic algorithm. First, comparisons are provided with respect to several techniques that are representative of the previous works in the area. Then, we compare the results given by three proposed algorithms. For the makespan criterion as well as for the total flowtime, the computational results show that our algorithms are able to provide competitive results and new best upper bounds.     

An effective hybrid particle swarm optimization for no-wait flow shop scheduling

The no-wait flow shop scheduling that requires jobs to be processed without interruption between consecutive machines is a typical NP-hard combinatorial optimization problem, and represents an important area in production scheduling. This paper proposes an effective hybrid algorithm based on particle swarm optimization (PSO) for no-wait flow shop scheduling with the criterion to minimize the maximum completion time (makespan). In the algorithm, a novel encoding scheme based on random key representation is developed, and an efficient population initialization, an effective local search based on the Nawaz-Enscore-Ham (NEH) heuristic, as well as a local search based on simulated annealing (SA) with an adaptive meta-Lamarckian learning strategy are proposed and incorporated into PSO. Simulation results based on well-known benchmarks and comparisons with some existing algorithms demonstrate the effectiveness of the proposed hybrid algorithm.     

Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria

In textile industries, production facilities are established as multi-stage production flow shop facilities, where a production stage may be made up of parallel machines. This known as a flexible or hybrid flow shop environment. This paper considers the problem of scheduling n independent jobs in such an environment. In addition, we also consider the general case in which parallel machines at each stage may be unrelated. Each job is processed in ordered operations on a machine at each stage. Its release date and due date are given. The preemption of jobs is not permitted. We consider both sequence- and machine-dependent setup times. The problem is to determine a schedule that minimizes a convex combination of makespan and the number of tardy jobs. A 0–1 mixed integer program of the problem is formulated. Since this problem is NP-hard in the strong sense, we develop heuristic algorithms to solve it approximately. Firstly, several basic dispatching rules and well-known constructive heuristics for flow shop makespan scheduling problems are generalized to the problem under consideration. We sketch how, from a job sequence, a complete schedule for the flexible flow shop problem with unrelated parallel machines can be constructed. To improve the solutions, polynomial heuristic improvement methods based on shift moves of jobs are applied. Then, genetic algorithms are suggested. We discuss the components of these algorithms and test their parameters. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages.     

An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs

The problem of scheduling in flowshops with sequence-dependent setup times of jobs is considered and solved by making use of ant colony optimization (ACO) algorithms. ACO is an algorithmic approach, inspired by the foraging behavior of real ants, that can be applied to the solution of combinatorial optimization problems. A new ant colony algorithm has been developed in this paper to solve the flowshop scheduling problem with the consideration of sequence-dependent setup times of jobs. The objective is to minimize the makespan. Artificial ants are used to construct solutions for flowshop scheduling problems, and the solutions are subsequently improved by a local search procedure. An existing ant colony algorithm and the proposed ant colony algorithm were compared with two existing heuristics. It was found after extensive computational investigation that the proposed ant colony algorithm gives promising and better results, as compared to those solutions given by the existing ant colony algorithm and the existing heuristics, for the flowshop scheduling problem under study.     

The tricriteria flowshop scheduling problem

Multicriteria flowshop scheduling problems have been one of the most attractive subjects in recent years. In the multicriteria flowshop scheduling literature, a very limited number of studies have been performed on problems which include a tardiness criterion. In this paper a multicriteria (tricriteria) two-machine flowshop scheduling problem with a tardiness criterion is tackled. The objective is to minimise a weighted sum of total completion time, total tardiness and makespan. An integer programming model is proposed for the problem which belongs to NP-hard class. The modified NEH (Nawaz, Enscore and Ham) algorithm, a tabu search-based heuristic method, random search and the EDD rule (the earliest due date rule) are used to solve problems with up to 2,500 jobs. A computational analysis is conducted to evaluate the performance of the heuristics. The analysis shows that the heuristics are quite efficient, and the performance of the tabu search based heuristic is the best of all in terms of solution quality.     

Scheduling and worker assignment problems on hybrid flowshop with cost-related objective function

This paper proposes a colonial competitive algorithm which is improved by variable neighborhood search algorithm for the simultaneous effects of learning and deterioration on hybrid flowshop scheduling with sequence-dependent setup times. By the effects of learning and deterioration, the processing time of a job is determined by position in the sequence and its execution start time. In addition, it is assumed that the processing time of any job depends on the number of workers assigned to the job on a particular stage, and the more workers assigned to a stage, the shorter the job processing time. These additional traits that are added to the scheduling problem coexist in many realistic scheduling situations. This problem consists of two basic questions of job scheduling and worker assignment. Minimization of the earliness, tardiness, makespan, and total worker employing costs is considered as the objective function. To evaluate the performance of the hybrid colonial competitive algorithm, the random key genetic algorithm, immune algorithm, variable neighborhood search, and hybrid simulated annealing metaheuristic presented previously are investigated for comparison purposes, and computational experiments are performed on standard test problems. Results show that our proposed algorithm performs better than the other algorithms for various test problems.     

Designing integrated cellular manufacturing systems with scheduling considering stochastic processing time

This paper addresses a new mathematical model for cellular manufacturing problem integrated with group scheduling in an uncertain space. This model optimizes cell formation and scheduling decisions, concurrently. It is assumed that processing time of parts on machines is stochastic and described by discrete scenarios enhances application of real assumptions in analytical process. This model aims to minimize total expected cost consisting maximum tardiness cost among all parts, cost of subcontracting for exceptional elements and the cost of resource underutilization. Scheduling problem in a cellular manufacturing environment is treated as group scheduling problem, which assumes that all parts in a part family are processed in the same cell and no inter-cellular transfer is needed. Finally, the nonlinear model will be transformed to a linear form in order to solve it for optimality. To solve such a stochastic model, an efficient hybrid method based on new combination of genetic algorithm (GA), simulated annealing (SA) algorithm, and an optimization rule will be proposed where SA and optimization rule are subordinate parts of GA under a self-learning rule criterion. Also, performance and robustness of the algorithm will be verified through some test problems against branch and bound and a heuristic procedure.     

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.     

Ant colony optimization technique for the sequence-dependent flowshop scheduling problem

In the real world, production scheduling systems, usually optimal job scheduling, requires an explicit consideration of sequence-dependent setup times. One of the most important scheduling criteria in practical systems is makespan. In this paper, the author presents an ant colony optimization (ACO) algorithm for the sequence-dependent permutation flowshop scheduling problem. The proposed ACO algorithm benefits from a new approach for computing the initial pheromone values and a local search. The proposed algorithm is tested on randomly generated problem instances and results indicate that it is very competitive with the existing best metaheuristics.     

The two-stage assembly flowshop scheduling problem with bicriteria of makespan and mean completion time

In this paper, we address the two-stage assembly flowshop scheduling problem with a weighted sum of makespan and mean completion time criteria, known as bicriteria. Since the problem is NP-hard, we propose heuristics to solve the problem. Specifically, we propose three heuristics; simulated annealing (SA), ant colony optimization (ACO), and self-adaptive differential evolution (SDE). We have conducted computational experiments to compare the performance of the proposed heuristics. It is statistically shown that both SA and SDE perform better than ACO. Moreover, the experiments reveal that SA, in general, performs better than SDE, while SA consumes less CPU time than both SDE and ACO. Therefore, SA is shown to be the best heuristic for the problem.