A polynomial time heuristic for the two-machine flowshop scheduling problem with setup times and random processing times

The two-machine flowshop scheduling problem to minimize makespan is addressed. Jobs have random processing times which are bounded within certain intervals. The distributions of job processing times are not known. This problem has been addressed in the literature with the assumption that setup times are included in processing times or are zero. In this paper, we relax this assumption and treat setup times as separate from processing times. We propose a polynomial time heuristic algorithm. Both Johnson algorithm and Yoshida and Hitomi algorithm, both of which developed for the deterministic problem, are special cases of the proposed algorithm. The heuristic algorithm uses a weighted average of lower and upper bounds for processing times. For different weights, the results of the proposed algorithm are compared based on randomly generated data. The computational analysis has shown that the proposed algorithm, with equal weights given to the lower and upper bounds, performs considerably well with an overall average error of 0.36%. The analysis has also shown that the proposed algorithm can safely be used regardless of processing time distributions and the range between lower and upper bounds.     

Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times

This paper presents an enhanced migrating bird optimization (MBO) algorithm and a new heuristic for solving a scheduling problem. The proposed approaches are applied to a permutation flowshop with sequence dependent setup times and the objective of minimizing the makespan. In order to augment the MBOs intensification capacity, an original problem specific heuristic is introduced. An adapted neighborhood, a tabu list, a restart mechanism and an original process for selecting a new leader also improved the MBO’s behavior. Using benchmarks from the literature, the resulting enhanced MBO (EMBO) gives state-of-the-art results when compared with other algorithms reference. A statistical analysis of the numerical experiments confirms the relative efficiency and effectiveness of both EMBO and the new heuristic.     

Heuristics for the flow line problem with setup costs

This paper presents two new heuristics for the flowshop scheduling problem with sequence-dependent setup times (SDSTs) and makespan minimization objective. The first is an extension of a procedure that has been very successful for the general flowshop scheduling problem. The other is a greedy randomized adaptive search procedure (GRASP) which is a technique that has achieved good results on a variety of combinatorial optimization problems. Both heuristics are compared to a previously proposed algorithm based on the traveling salesman problem (TSP). In addition, local search procedures are developed and adapted to each of the heuristics. A two-phase lower bounding scheme is presented as well. The first phase finds a lower bound based on the assignment relaxation for the asymmetric TSP. In phase two, attempts are made to improve the bound by inserting idle time. All procedures are compared for two different classes of randomly generated instances. In the first case where setup times are an order of magnitude smaller than the processing times, the new approaches prove superior to the TSP-based heuristic; for the case where both processing and setup times are identically distributed, the TSP-based heuristic outperforms the proposed procedures.     

Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint

This paper focuses on the scheduling problem of minimizing makespan for a given set of jobs in a two-stage hybrid flowshop subject to a product-mix ratio constraint. There are identical parallel machines at the first stage of the hybrid flowshop, while there is a single batch-processing machine at the second stage. Ready times of the jobs (at the first stage) may be different, and a given product-mix ratio of job types should be kept in each batch at the second stage. We present three types of heuristic algorithms: forward scheduling algorithms, backward scheduling algorithms, and iterative algorithms. To evaluate performance of the suggested algorithms, a series of computational experiments are performed on randomly generated test problems and results are reported.     

Total completion time with makespan constraint in no-wait flowshops with setup times

The m-machine no-wait flowshop scheduling problem with the objective of minimizing total completion time subject to the constraint that the makespan value is not greater than a certain value is addressed in this paper. Setup times are considered non-zero values, and thus, setup times are treated as separate from processing times. Several recent algorithms, an insertion algorithm, two genetic algorithms, three simulated annealing algorithms, two cloud theory-based simulated annealing algorithms, and a differential evolution algorithm are adapted and proposed for the problem. An extensive computational analysis has been conducted for the evaluation of the proposed algorithms. The computational analysis indicates that one of the nine proposed algorithms, one of the simulated annealing algorithms (ISA-2), performs much better than the others under the same computational time. Moreover, the analysis indicates that the algorithm ISA-2 performs significantly better than the earlier existing best algorithm. Specifically, the best performing algorithm, ISA-2, proposed in this paper reduces the error of the existing best algorithm in the literature by at least 90% under the same computational time. All the results have been statistically tested.     

A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages

In this paper we propose a heuristic for solving the problem of resource constrained preemptive scheduling in the two-stage flowshop with one machine at the first stage and parallel unrelated machines at the second stage, where renewable resources are shared among the stages, so some quantities of the same resource can be used at different stages at the same time. Availability of every resource at any moment is limited and resource requirements of jobs are arbitrary. The objective is minimization of makespan. The problem is NP-hard. The heuristic first sequences jobs on the machine at stage 1 and then solves the preemptive scheduling problem at stage 2. Priority rules which depend on processing times and resource requirements of jobs are proposed for sequencing jobs at stage 1. A column generation algorithm which involves linear programming, a tabu search algorithm and a greedy procedure is proposed to minimize the makespan at stage 2. A lower bound on the optimal makespan in which sharing of the resources between the stages is taken into account is also derived. The performance of the heuristic evaluated experimentally by comparing the solutions to the lower bound is satisfactory.     

Minimizing the total completion time in a two-machine flowshop with sequence-independent setup times

We consider the problem of minimizing the sum of completion times in a two-machine permutation flowshop subject to setup times. We propose a new priority rule, several constructive heuristics, local search procedures, as well as an effective multiple crossover genetic algorithm. Computational experiments carried out on a large set of randomly generated instances provide evidence that a constructive heuristic based on newly derived priority rule dominates all the proposed constructive heuristics. More specifically, we show that one of our proposed constructive heuristics outperforms the best constructive heuristic in the literature in terms of both error and computational time. Furthermore, we show that one of our proposed local search-based heuristics outperforms the best local search heuristic in the literature in terms of again both error and computational time. We also show that, in terms of quality-to-CPU time ratio, the multiple crossover genetic algorithm performs consistently well.     

Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process

We consider a scheduling problem in a factory producing printed circuit boards (PCBs). The PCB assembly process in this factory can be regarded as a flowshop which has two special characteristics: jobs have sequence dependent setup times and each job consists of a lot (batch) of identical PCBs. Because of the latter characteristic, it is possible to start a job on a following machine before the job is entirely completed on a previous machine, that is, there is time-lag between machines. In this paper, we propose several heuristics, including taboo search (TS) and simulated annealing (SA) methods, for this generalized flowshop scheduling problem with the objective of minimizing mean tardiness. We compare suggested heuristics after series of tests to find appropriate values for parameters needed for the two search algorithms, TS and SA. Results of computational tests on randomly generated test problems are reported.     

A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times

This article proposes lower bounds, as well as a divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times (MSPS). The heuristic is tested on randomly generated instances and compared with a previously published tabu search algorithm. Results show that the proposed heuristic is much faster than tabu search while providing similar quality solutions.     

Multi-objective sequence dependent setup times permutation flowshop: A new algorithm and a comprehensive study

The permutation flowshop scheduling problem has been thoroughly studied in recent decades, both from single objective as well as from multi-objective perspectives. To the best of our knowledge, little has been done regarding the multi-objective flowshop with Pareto approach when sequence dependent setup times are considered. As setup times and multi-criteria problems are important in industry, we must focus on this area. We propose a simple, yet powerful algorithm for the sequence dependent setup times flowshop problem with several criteria. The presented method is referred to as Restarted Iterated Pareto Greedy or RIPG and is compared against the best performing approaches from the relevant literature. Comprehensive computational and statistical analyses are carried out in order to demonstrate that the proposed RIPG method clearly outperforms all other algorithms and, as a consequence, it is a state-of-art method for this important and practical scheduling problem.     

Tabu search for graph partitioning

In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.     

An efficient heuristic based on machine workload for the flowshop scheduling problem with setup and removal

We are concerned in this paper with solving ann jobs,M machines flowshop scheduling problem where the objective function is the minimization of the makespan. We take into account setup, processing and removal times separately. After drawing up a synthesis of existing work which addresses this type of problems, we propose a new heuristic algorithm which is based on the machine workload to find an efficient permutation schedule. Computational experiences show that our algorithm yields excellent results, particularly when bottleneck machines are present.     

Constructive and composite heuristic solutions to the P//∑Ci scheduling problem

In this paper, we study the permutation flowshop scheduling problem with the criterion of minimising the total flow time. We propose a new constructive heuristic procedure to solve the problem. This procedure is flexible in the computational effort required, as it can be adjusted to the requirements of the problem. We combine this procedure with local search methods, whose computational requirements can also be varied, to study the efficiency and effectiveness of different ways of forming composite solution methods. Computational experiments on standard benchmark problems are carried out. The results show that the new heuristic performs significantly better than previous ones and that combining constructive and search heuristics not only further improves the solution quality but also saves computation time. Discussions on the results are provided and future research is suggested.     

Single machine scheduling with sequence-dependent family setups to minimize maximum lateness

Motivated by a real-life scheduling problem in a steel wire factory in China,this paper considers the single machine scheduling problem with sequence-dependent family setup times to minimize maximum lateness. In view of the NP-hard nature of the problem, structural (dominance and neighbourhood)properties of the problem are described and used in the tabu search algorithms to find optimal or near-optimal schedules. These proposed structural properties quickly exclude unpromising and/or non-improving neighbours from further search.Empirical results on the randomly generated and real-life problem instances from a factory in China show that the proposed heuristic algorithms utilizing the structural properties can obtain optimal or near optimal solutions with a reasonable computational effort.     

A bicriteria m-machine flowshop scheduling with sequence-dependent setup times

In this study, a bicriteria m-machine flowshop scheduling with sequence-dependent setup times is considered. The objective function of the problem is minimization of the weighted sum of total completion time and makespan. Only small size problems with up to 6 machines and 18 jobs can be solved by the proposed integer programming model. Also the model is tested on an example. We also proposed three heuristic approaches for solving large jobs problems. To solve the large sizes problems up to 100 jobs and 10 machines, special heuristics methods is used. Results of computational tests show that the proposed model is effective in solving problems.     

A hybrid two-stage transportation and batch scheduling problem

We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.     

Scheduling multi-stage parallel-processor services to minimize average response time

The problem of scheduling on a multi-stage parallel-processor architecture in computer centres is addressed with the objective of minimizing average completion time of a set of requests. The problem is modelled as a flexible flowshop problem for which few heuristics exist in the flowshop scheduling literature. A new three-phase heuristic is proposed in this paper. An extensive computational experiment has been conducted to compare the performance of the existing heuristics and the proposed heuristic. The results indicate that the proposed heuristic significantly outperforms the existing ones. More specifically, the overall average error of the best existing heuristic is about five times that of the proposed heuristic while the overall average CPU time of the proposed heuristic is about half of the best existing one. More importantly, as the number of requests increases, the CPU time of the proposed heuristic decreases considerably (compared to the best existing heuristic) while the ratio of the error (of the best existing to the proposed heuristic) of about five times remains almost the same.     

Single Machine Scheduling with Major and Minor Setup Times: A Tabu Search Approach

The paper deals with a single machine scheduling problem in which jobs are grouped into families that require major setup times, and where jobs within families require for processing minor setup times. The former are sequence independent and the latter have special triangular structure. The problem is to find a partition of families into batches, sequences of jobs in particular batches and a sequence of batches which minimize a general regular cost function. The tabu search algorithm for finding near-optimal schedules is proposed and results of computational experiments are presented.     

Carryover sequence-dependent group scheduling with the integration of internal and external setup times

This paper addresses a group scheduling problem in a two-machine flow shop with a bicriteria objective and carryover sequence-dependent setup times. This special type of group scheduling problem typically arises in the assembly of printed circuit boards (PCBs). The objective is to sequence all board types in a board group as well as board groups themselves in a way that the objective function is minimized. We introduce the carryover sequence-dependent setup on machines, and call it internal setup. As an opportunity for manufacturers to decrease the costs, the focus is to completely eliminate the role of the kitting staff. Thus, we introduce the external setup (kitting) time for the next board group and require it to be performed by the machine operator during the time he is idle. Consequently, the internal and external setup times are integrated in this research, and to the best of our knowledge it is for the first time a research on PCB group scheduling is performed by integrating both setups. In order to solve this problem, first a mathematical model is developed. Then a heuristic together with two other meta-heuristic algorithms (one based on tabu search and the other based on genetic algorithm) are proposed and their efficiency and effectiveness on several problems are tested. Also a statistical experimental design is performed in order to evaluate the impact of different factors on the performance of the algorithms.     

Meta-heuristic approaches with memory and evolution for a multi-product production/distribution system design problem

We consider a multi-product two-stage production/distribution system design problem (PDSD) where a fixed number of capacitated distribution centers are to be located with respect to capacitated suppliers (plants) and retail locations (customers) while minimizing the total costs in the system. We present a mixed-integer problem formulation that facilitates the development of efficient heuristic procedures. We provide meta-heuristic procedures, including a population-based scatter search with path relinking and trajectory-based local and tabu search, for the solution of the problem. We also develop efficient construction heuristics and transshipment heuristics that are incorporated into the heuristic procedures for the solution of subproblems. We present extensive computational results that show the high performance of the solution approaches. We obtain smaller than 1.0% average optimality gaps with acceptable runtimes, even for relatively large problems. The computational results also demonstrate the effectiveness of the construction and transshipment heuristics that impact the solution quality and overall runtimes.