A beam-search-based constructive heuristic for the PFSP to minimise total flowtime

In this paper we present a beam-search-based constructive heuristic to solve the permutation flowshop scheduling problem with total flowtime minimisation as objective. This well-known problem is NP-hard, and several heuristics have been developed in the literature. The proposed algorithm is inspired in the logic of the beam search, although it remains a fast constructive heuristic.The results obtained by the proposed algorithm outperform those obtained by other constructive heuristics in the literature for the problem, thus modifying substantially the state-of-the-art of efficient approximate procedures for the problem. In addition, the proposed algorithm even outperforms two of the best metaheuristics for many instances of the problem, using much lesser computation effort. The excellent performance of the proposal is also proved by the fact that the new heuristic found new best upper bounds for 35 of the 120 instances in Taillard’s benchmark.     

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.     

Production scheduling for blocking flowshop in distributed environment using effective heuristics and iterated greedy algorithm

Production scheduling plays an important role in the intelligent decision support system and intelligent optimization decision technology. In the context of the globalization trend, the current production and management may extend from a single factory to a distributed production network. In this paper, we study the distributed blocking flowshop scheduling problem (DBFSP) that is an important generalization of the traditional blocking flowshop scheduling problem in the distributed environment. Six constructive heuristics and an iterated greedy (IG) algorithm are proposed to minimize the makespan, which provides procedures for obtaining efficient and effective solutions to make decision-making sounder. The first five heuristics are developed based on the well-known NEH2 heuristic [B. Naderi, R. Ruiz, The distributed permutation flowshop scheduling problem, Computers & Operations Research, 37 (4) (2010) 754–768.] and the last heuristic is presented by extending the PW heuristic [Q.K. Pan, L. Wang, Effective heuristics for the blocking flowshop scheduling problem with makespan minimization, Omega, 40 (2) (2012) 218–229.] to DBFSP in an effective way. The composite heuristics that combining constructive heuristics and local searches are also studied. The proposed composite heuristics are chosen to generate an initial solution with a high level of quality. Keeping the simplicity of the IG algorithm, three local search procedures, two destruction procedures, an improved reconstruction procedure, and a simulated annealing-like acceptance criterion are well designed based on the problem-specific knowledge to enhance the IG algorithm. The computational experiments are carried out based on the 720 benchmark instances from the literature. The results show that the proposed heuristics are very effective for solving the problem under consideration and the presented IG algorithm performs significantly better than the other state-of-the-art metaheuristics from the literature.     

Improvement of constructive heuristics using variable neighbourhood descent for scheduling a flow shop with sequence dependent setup time

This paper deals with the problem of scheduling a flow shop operating in a sequence dependent setup time environment. The objective is to determine the sequence that minimises the makespan. Two efficient neighbourhood search-based heuristics have been developed and tested using 960 problems, and the results obtained reveal their usefulness. The algorithms make use of two existing constructive heuristics. A neighbourhood search known as variable neighbourhood descent is used to improve the two constructive heuristics. Experimentation is carried out on the 96 groups of problems with 10 problem instances in each group. Performance analysis is carried out using the relative performance improvement of each heuristic. The analysis shows a consistently better performance of the neighbourhood-based improvement heuristics. A paired comparison test is used for validating the superiority of the proposed heuristics. The statistical analysis reveals that the performance of the neighbourhood-based heuristics is very much dependent on the initial constructive heuristics used.     

A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop

In this paper we address a hybrid flow shop scheduling problem considering the minimization of the sum of the total earliness and tardiness penalties. This problem is proven to be NP-hard, and consequently the development of heuristic and meta-heuristic approaches to solve it is well justified. So, we propose an ant colony optimization method to deal with this problem. Our proposed method has several features, including some heuristics that specifically take into account both earliness and tardiness penalties to compute the heuristic information values. The performance of our algorithm is tested by numerical experiments on a large number of randomly generated problems. A comparison with solutions performance obtained by some constructive heuristics is presented. The results show that the proposed approach performs well for this problem.     

Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization

This paper proposes two constructive heuristics, i.e. HPF1 and HPF2, for the blocking flow shop problem in order to minimize the total flow time. They differ mainly in the criterion used to select the first job in the sequence since, as it is shown, its contribution to the total flow time is not negligible. Both procedures were combined with the insertion phase of NEH to improve the sequence. However, as the insertion procedure does not always improve the solution, in the resulting heuristics, named NHPF1 and NHPF2, the sequence was evaluated before and after the insertion to keep the best of both solutions. The structure of these heuristics was used in Greedy Randomized Adaptive Search Procedures (GRASP) with variable neighborhood search in the improvement phase to generate greedy randomized solutions. The performance of the constructive heuristics and of the proposed GRASPs was evaluated against other heuristics from the literature. Our computational analysis showed that the presented heuristics are very competitive and able to improve 68 out of 120 best known solutions of Taillard’s instances for the blocking flow shop scheduling problem with the total flow time criterion.     

NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness

Since Johnson׳s seminal paper in 1954, scheduling jobs in a permutation flowshop has been receiving the attention of hundreds of practitioners and researchers, being one of the most studied topics in the Operations Research literature. Among the different objectives that can be considered, minimising the total tardiness (i.e. the sum of the surplus of the completion time of each job over its due date) is regarded as a key objective for manufacturing companies, as it entails the fulfilment of the due dates committed to customers. Since this problem is known to be NP-hard, most research has focused on proposing approximate procedures to solve it in reasonable computation times. Particularly, several constructive heuristics have been proposed, with NEHedd being the most efficient one, serving also to provide an initial solution for more elaborate approximate procedures. In this paper, we first analyse in detail the decision problem depending on the generation of the due dates of the jobs, and discuss the similarities with different related decision problems. In addition, for the most characteristic tardiness scenario, the analysis shows that a huge number of ties appear during the construction of the solutions done by the NEHedd heuristic, and that wisely breaking the ties greatly influences the quality of the final solution. Since no tie-breaking mechanism has been designed for this heuristic up to now, we propose several mechanisms that are exhaustively tested. The results show that some of them outperform the original NEHedd by about 25% while keeping the same computational requirements.     

A constructive heuristic for total flowtime minimization in a no-wait flowshop with sequence-dependent setup times

In this paper, we addressed the problem of scheduling jobs in a no-wait flow shop with sequence-dependent setup times with the objective of minimizing the total flow time. As this problem is well-known for being NP-hard, we present a new constructive heuristic, named QUARTS, in order to obtain good approximate solutions in a short CPU time. QUARTS breaks the problem in quartets in order to minimize the total flow time. The method was tested with other literature methods: BAH and BIH by Bianco et al. (1999) [6], TRIPS, by Brown et al. (2004) [7] and the metaheuristic Iterated Greedy with Local Search proposed by Ruiz and Stützle (2007) [25]. The computational results showed that IG_LS obtained the best results and QUARTS presented the best performance regarding other constructive heuristics.     

The 2-stage assembly flowshop scheduling problem with total completion time: Efficient constructive heuristic and metaheuristic

In this paper, we address the 2-stage assembly scheduling problem where there are m machines in the first stage to manufacture the components of a product and one assembly station (machine) in the second stage. The objective considered is the minimisation of the total completion time. Since the NP-hard nature of this problem is well-established, most previous research has focused on finding approximate solutions in reasonable computation time. In our paper, we first review and derive a number of problem properties and, based on these ideas, we develop a constructive heuristic that outperforms the existing constructive heuristics for the problem, providing solutions almost in real-time. Finally, for the cases where extremely high-quality solutions are required, a variable local search algorithm is proposed. The computational experience carried out shows that the algorithm outperforms the best existing metaheuristic for the problem. As a summary, the heuristics presented in the paper substantially modify the state-of-the-art of the approximate methods for the 2-stage assembly scheduling problem with total completion time objective.     

Heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties

In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose several dispatching heuristics, and analyse their performance on a wide range of instances. The heuristics include simple and widely used scheduling rules, as well as adaptations of those rules to a quadratic objective function. We also propose heuristic procedures that specifically address both the earliness and the tardiness penalties, as well as the quadratic cost function. Several improvement procedures were also analysed. These procedures are applied as an improvement step, once the heuristics have generated a schedule.     

Flow shop scheduling with blocking using modified harmony search algorithm with neighboring heuristics methods

The flow shop scheduling with blocking is considered an important scheduling problem which has many real-world applications. This paper proposes a new algorithm which applies heuristic techniques in harmony search algorithm (HSA) to minimize the total flow time. The proposed method is called modified harmony search algorithm with neighboring heuristics methods (MHSNH). To improve the initial harmony memory, we apply two heuristic techniques: nearest neighbor (NN) and constructive modified NEH (MNEH). A modified version of harmony search algorithm evolves to explore and generates a new solution. The newly generated solution is then enhanced by using neighboring heuristics. Lastly, another neighboring heuristic is applied to improve the obtained solution. The proposed algorithm is evaluated using 12 real-world problem instances each with 10 samples. The experimental evaluation is accomplished using two factors: CPU computational time and the number of iterations. For the first factor, comparative evaluation against six well-established methods shows that the proposed method achieves almost the best overall results in six problem instances out of the twelve and yields fruitful results for others. For the second factor, comparative evaluation against twelve well-regarded methods shows that the proposed method achieves the best overall results in three problem instances and obtains very good results in other instances. In a nutshell, the proposed MHSNH is an effective strategy for solving the job shop scheduling problem.     

Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem

In this paper, we consider the single machine scheduling problem with weighted quadratic tardiness costs. Several efficient dispatching rules are proposed. These include existing heuristics for the linear problem, as well as procedures suitably adapted to the quadratic objective function. Also, both forward and backward scheduling procedures are considered.The computational results show that the heuristics that specifically take into account the quadratic objective significantly outperform their linear counterparts. Also, the backward scheduling approach proves to be superior, and the difference in performance is even more noticeable for the harder instances.The best of the backward scheduling heuristics is both quite efficient and effective. Indeed, this procedure can quickly generate a schedule even for large instances. Also, its relative deviation from the optimum is usually rather low, and it performs adequately even for the more difficult instances.     

Scheduling algorithms for heterogeneous batch processors with incompatible job-families

We consider the problem of scheduling heterogeneous batch processors (i.e., batch processors with different capacity) with incompatible job-families and non-identical job sizes to maximize the utilization of the batch processors. We analyzed the computational complexity of this problem and showed that it is NP-hard and proposed eight variants of a fast greedy heuristic. A series of computational experiments were carried out to compare the performance of the heuristics and showed that the heuristics are capable of consistently obtaining near (estimated) optimal solutions with very low-computational burden for large-scale problems. We also carried out a study to find the effect of family processing time changes on the performance of the heuristics. This sensitivity analysis indicated that the processing time set of job-families influences the performance of the heuristic algorithms.     

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.     

Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan

This paper presents an efficient meta-heuristic algorithm based on electromagnetism-like mechanism (EM), in which has been successfully implemented in a few combinatorial problems. We propose the EM for scheduling the flow shop problem that minimizes the makespan and total weighted tardiness and considers transportation times between machines and stage skipping (i.e., some jobs may not need to be processed on all the machines). To show the efficiency of this proposed algorithm, we also apply simulated annealing (SA) and some other well-recognized constructive heuristics, such as SPT, NEH, (g/2, g/2) Johnson’ rule, EWDD, SLACK, and NEH_EWDD for the given problems. To evaluate the performance and robustness of our proposed EM, we experiment a number of test problems. Our computational results show that our proposed EM in almost all cases outperforms SA and other foregoing heuristics applied to this paper.     

A generalized constructive algorithm using insertion-based heuristics

In this paper, a generalized constructive algorithm referred to as GCA is presented which makes it possible to select a wide variety of heuristics just by the selection of its arguments values. A general framework for generating permutations of integers is presented. This framework, referred to as PERMGEN, forms a link between the numbering of permutations and steps in the insertion-based heuristics. A number of arguments controlling the operation of GCA are identified. Features and benefits of the generalized algorithm are presented through the extension of the NEH heuristic, a successful heuristic solution approach of Nawaz, Enscore, and Ham for the permutation flowshop problem (PFSP). The goal of the experimental study is to improve the performance of the NEH heuristic on the PFSP. To achieve this goal, the space of algorithmic control arguments is searched for a combination of values that define an algorithm providing lower makespan solutions than NEH, in a linear increase of CPU time. Computational experiments on a set of 120 benchmark problem instances, originally proposed by Taillard, are performed to establish a more robust version of the original NEH constructive heuristic. The proposed procedures outperform NEH, preserving its efficiency and simplicity.     

Single machine scheduling problem with interval processing times to minimize mean weighted completion time

The single resource scheduling problem is commonly applicable in practice not only when there is a single resource but also in some multiple-resource production systems where only one of the resources is bottle neck. Thus, the single resource (machine) scheduling problem has been widely addressed in the scheduling literature. In this paper, the single machine scheduling problem with uncertain and interval processing times is addressed. The objective is to minimize mean weighted completion time. The problem has been addressed in the literature and efficient heuristics have been presented. In this paper, some new polynomial time heuristics, utilizing the bounds of processing times, are proposed. The proposed and existing heuristics are compared by extensive computational experiments. The conducted experiments include a generalized simulation environment and several additional representative distributions in addition to the restricted experiments used in the literature. The results indicate that the proposed heuristics perform significantly better than the existing heuristics. Specifically, the best performing proposed heuristic reduces the error of the best existing heuristic in the literature by more than 75% while the computational time of the best performing proposed heuristic is less than that of the best existing heuristic. Moreover, the absolute error of the best performing heuristic is only about 1% of the optimal solution. Having a very small absolute error along with a negligible computational time indicates the superiority of the proposed heuristics.     

A biased random key genetic algorithm for the field technician scheduling problem

This paper addresses a problem that service companies often face: the field technician scheduling problem. The problem considers the assignment of a set of jobs or service tasks to a group of technicians. The tasks are in different locations within a city, with different time windows, priorities, and processing times. Technicians have different skills and working hours. The main objective is to maximize the sum of priority values associated with the tasks performed each day. Due to the complexity of this problem, constructive heuristics that explore specific characteristics of the problem are developed. A customized Biased Random Key Genetic Algorithm (BRKGA) is also proposed. Computational tests with 1040 instances are presented. The constructive heuristics outperformed a heuristic of the literature in 90% of the instances. In a comparative study with optimal solutions obtained for small-sized problems, the BRKGA reached 99% of the optimal values; for medium- and large-sized problems, the BRKGA provided solutions that are on average 3.6% below the upper bounds.     

Single machine scheduling with controllable processing times to minimize total tardiness and earliness

In most deterministic scheduling problems job processing times are considered as invariable and known in advance. Single machine scheduling problem with controllable processing times with no inserted idle time is presented in this study. Job processing times are controllable to some extent that they can be reduced or increased, up to a certain limit, at a cost proportional to the reduction or increase. In this study, our objective is determining a set of compression/expansion of processing times in addition to a sequence of jobs simultaneously, so that total tardiness and earliness are minimized. A mathematical model is proposed firstly and afterward a net benefit compression–net benefit expansion (NBC–NBE) heuristic is presented so as to acquire a set of amounts of compression and expansion of jobs processing times in a given sequence. Three heuristic techniques in small problems and in medium-to-large instances two meta-heuristic approaches, as effective local search methods, as well as these heuristics are employed to solve test examples. The single machine total tardiness problem (SMTTP) is already NP-hard, so the considered problem is NP-hard obviously. The computational experiments demonstrate that our proposed heuristic is efficient approach for such just-in-time (JIT) problem, especially equipped with competent heuristics.     

New approximate algorithms for the customer order scheduling problem with total completion time objective

In this paper, we study a customer order scheduling problem where a number of orders, composed of several product types, have to be scheduled on a set of parallel machines, each one capable to process a single product type. The objective is to minimise the sum of the completion times of the orders, which is related to the lead time perceived by the customer, and also to the minimisation of the work-in-process. This problem has been previously studied in the literature, and it is known to be NP-hard even for two product types. As a consequence, the interest lies on devising approximate procedures to obtain fast, good performing schedules. Among the different heuristics proposed for the problem, the ECT (Earliest Completion Time) heuristic by Leung et al. [6] has turned to be the most efficient constructive heuristic, yielding excellent results in a wide variety of settings. These authors also propose a tabu search procedure that constitutes the state-of-the-art metaheuristic for the problem. We propose a new constructive heuristic based on a look-ahead mechanism. The computational experience conducted shows that it clearly outperforms ECT, while having both heuristics the same computational complexity. Furthermore, we propose a greedy search algorithm using a specific neighbourhood that outperforms the existing tabu search procedure for different stopping criteria, both in terms of quality of solutions and of required CPU effort.