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.     

Two-stage hybrid flowshop scheduling with simultaneous processing machines

Simultaneous processing machines, common in processing industries such as steel and food production, can process several jobs simultaneously in the first-in, first-out manner. However, they are often highly energy-consuming. In this paper, we study a new two-stage hybrid flowshop scheduling problem, with simultaneous processing machines at the first stage and a single no-idle machine with predetermined job sequence at the second stage. A mixed integer programming model is proposed with the objective of minimizing the total processing time to reduce energy consumption and improve production efficiency. We give a sufficient and necessary condition to construct feasible sequencing solutions and present an effective approach to calculate the time variables for a feasible sequencing solution. Based on these results, we design a list scheduling heuristic algorithm and its improvement. Both heuristics can find an optimal solution under certain conditions with complexity O(nlogn), where n is the number of jobs. Our experiments verify the efficiency of these heuristics compared with classical heuristics in the literature and investigate the impacts of problem size and processing times.     

Heuristics for scheduling in flowshops and flowline-based manufacturing cells to minimize the sum of weighted flowtime and weighted tardiness of jobs

The problem of scheduling in two different types of flowshops (all jobs available at time zero, different job availability times known a priori) and in flowline-based manufacturing cells is considered with the objective of minimizing the sum of weighted flowtime and weighted tardiness of jobs. First, heuristic preference relations are developed by the consideration of lower bounds on the completion times, operation due-dates, and weights for holding and tardiness of jobs. A heuristic algorithm for scheduling is then proposed by making use of the heuristic preference relations. Two more heuristic algorithms are developed by implementing an improvement scheme to enhance the quality of the solution given by the first heuristic algorithm. The proposed and the existing heuristics are evaluated with respect to the three problem classes under consideration by solving a large number of randomly generated problems. The results of an extensive computational investigation for various problem sizes are presented. It has been observed that all three proposed heuristics perform better than the existing heuristics in giving a solution of superior quality and that the first proposed heuristic yields a good solution by requiring a negligible CPU time. In addition, an experimental investigation is carried out to evaluate the effectiveness of the improvement scheme when implemented in the existing heuristics, and also the effectiveness of heuristics based on simulated annealing. The results are discussed in detail.     

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.     

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.     

Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates

In this paper, we consider a single-machine scheduling problem with release dates. The aim is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose two new lower bounds that can be, respectively, computed in O(n²) and in O(nlogn) time where n is the number of jobs. We prove a sufficient and necessary condition for local optimality, which can also be considered as a priority rule. We present an efficient heuristic using such a condition. We also propose some dominance properties. A branch-and-bound algorithm incorporating the heuristic, the lower bounds and the dominance properties is proposed and tested on a large set of instances.     

Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times

This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.     

Modeling realistic hybrid flexible flowshop scheduling problems

This paper aims to contribute to the recent research efforts to bridge the gap between the theory and the practice of scheduling by modelizing a realistic manufacturing environment and analyzing the effect of the inclusion of several characteristics in the problem formulation. There are several constraints and characteristics that affect the scheduling operations at companies. While these constraints are many times tackled in the literature, they are seldom considered together inside the same problem formulation. We propose a formulation along with a mixed integer modelization and some heuristics for the problem of scheduling n jobs on m stages where at each stage we have a known number of unrelated machines. The jobs might skip stages and, therefore, we have what we call a hybrid flexible flowshop problem. We also consider per machine sequence-dependent setup times which can be anticipatory and non-anticipatory along with machine lags, release dates for machines, machine eligibility and precedence relationships among jobs. Manufacturing environments like this appear in sectors like food processing, ceramic tile manufacturing and several others. The optimization criterion considered is the minimization of the makespan. The MIP model and the heuristics proposed are tested against a comprehensive benchmark and the results evaluated by advanced statistical tools that make use of decision trees and experimental designs. The results allow us to identify the constraints that increase the difficulty.     

Hierarchical minimization of completion time variance and makespan in jobshops

This paper addresses the problem of minimizing makespan for a given set of n jobs to be processed on each of m machines in a static jobshop, subject to the minimum completion time variance (CTV). A lower bound on CTV is developed for the static jobshop problem. A backward scheduling approach is proposed using the observations on the development of lower bound for hierarchical minimization of CTV and makespan. A lower bound on makespan subject to minimum CTV is also presented for this problem. Finally, we present two simulated annealing heuristic approaches using the concepts of forward and backward scheduling. Their performances are compared against each other through the use of the lower bounds established in this work. The simulated annealing heuristic based on backward scheduling is shown to perform well by evaluating the developed heuristics on 82 jobshop problems taken from literature.     

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

An improved heuristic to minimize total flow time for scheduling in the m-machine no-wait flow shop

In this paper, we present a constructive heuristic to minimize total flow time criterion for the well-known NP-hard no-wait flow shop scheduling problem. It is based on the assumption that the priority of a job in the initial sequence is given by the sum of its processing times on the bottleneck machines. The initial sequence of jobs thus generated is further improved using a new job insertion technique. We show, through computational experimentation, that the proposed method significantly outperforms the best-known heuristics while retaining its time complexity of O(n²). Statistical tests of significance are used to confirm the improvement in solution quality.     

No-wait and separate setup three-machine flowshop with total completion time criterion

This paper considers the three-machine no-wait flowshop problem with the objective of minimizing total completion time where setup times are considered as separate from processing times and sequence independent. We present optimal solutions for certain cases, and a dominance relation for the general case. We also develop and evaluate five heuristic algorithms for small and large number of jobs. Computational experience for up to 100 jobs shows that the proposed heuristics are quite effective and their performance do not depend on the number of jobs. The computational experience has been conducted for the uniform processing time distributions of U (1, 10) and U (1, 100). The best heuristic gives an overall average error of 0.47% for U (1, 10) and it gives an overall average error of 1.23% for U (1, 100).     

A new set of high-performing heuristics to minimise flowtime in permutation flowshops

This paper addresses the problem of scheduling jobs in a permutation flowshop with the objective of total completion time minimisation. Since this problem is known to be NP-hard, most research has focussed on obtaining procedures – heuristics – able to provide good, but not necessarily optimal, solutions with a reasonable computational effort. Therefore, a full set of heuristics efficiently balancing both aspects (quality of solutions and computational effort) has been developed. 12 out of these 14 efficient procedures are composite heuristics based on the LR heuristic by Liu and Reeves (2001), which is of complexity $n^{3}m$. In our paper, we propose a new heuristic of complexity $n^{2}m$ for the problem, which turns out to produce better results than LR. Furthermore, by replacing the heuristic LR by our proposal in the aforementioned composite heuristics, we obtain a new set of 17 efficient heuristics for the problem, with 15 of them incorporating our proposal. Additionally, we also discuss some issues related to the evaluation of efficient heuristics for the problem and propose an alternative indicator.     

Shipment partitioning and routing to minimize makespan in a transportation network

This paper addresses the problem of partitioning and transporting a shipment of known size through an n-node public transportation network with known scheduled departure and arrival times and expected available capacities for each departure. The objective is to minimize the makespan of shipping. The problem while practical in its scope, has received very little attention in the literature perhaps because of the concentration of research in vehicle routing without regard to partitioning and partitioning without regard to routing. A general non-linear programming model is developed. The model is then converted into a linear model through the Routing First and Assignment Second approach. This approach is different from the general decomposition approaches since they normally do not guarantee optimality. However, the linear model still involves a large number of constraints, and solution is not attempted here. Instead, three heuristics are proposed for solving the problem. Two of the heuristics use iterative techniques to evaluate all possible paths. The third heuristic uses a max-flows approach based upon aggregated capacities to reduce the size of the network presented to the other heuristics. This allows for a good starting point for other heuristics, and may impact the total computational effort. We find that the heuristics developed perform well because in the case of networks that are not congested, they find the optimal solution.     

Addressing the N/1 scheduling problem—A heuristic approach

The problem of sequencing n-jobs on one machine (n/1) to minimize maximum job lateness has been the subject of much prior research. Most of this research has been directed at identifying optimal solutions to the problem via algorithmic search techniques. A weakness in employing an algorithm for solving the problem, however, is that lengthy computational times may result because of the necessity of searching n! sequences. By employing a multiple heuristic approach this limitation can be avoided. An optimal or near optimal schedule can be identified in a finite number of steps.This paper describes a multiple heuristic model that is effective more than eighty-ninety percent of the time in providing an optimal schedule for the N/l/L max scheduling program. Ten separate heuristics are described, and the results of testing the heuristics over fifteen hundred and sixty randomly generated problems is presented. Three of the heuristics are combined to form the heuristic-scheduling model.     

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 empirical analysis of heuristics for solving the two-machine flow shop problem with job release times

The theoretical analysis of heuristics for solving intractable optimization problems has many well-known drawbacks. Constructed instances demonstrating an exceptionally poor worst-case performance of heuristics are typically too peculiar to occur in practice. Theoretical results on the average-case performance of most heuristics could not be established due to the difficulty with the use of probabilistic analysis. Moreover, the heuristics for which some type of asymptotic optimality has been proven are likely to perform questionably in practice. The purpose of this paper is to confront known theoretical results with our empirical results concerning heuristics for solving the strongly NP-hard problem of minimizing the makespan in a two-machine flow shop with job release times. The heuristics' performance is examined with respect to their average and maximum relative errors, as well as their optimality rate, that is, the probability of being optimal. In particular, this allows us to observe that the asymptotic optimality rate of so called “almost surely asymptotically optimal” heuristic can be zero. We also present a new heuristic with short worst-case running time and statistically prove that it outperforms all heuristics known so far. However, our empirical experiments reveal that the heuristic is on average slower that its competitors with much longer worst-case running times.     

Minimizing total tardiness in a two-machine re-entrant flowshop with sequence-dependent setup times

We consider a two-machine re-entrant flowshop scheduling problem in which all jobs must be processed twice on each machine and there are sequence-dependent setup times on the second machine. For the problem with the objective of minimizing total tardiness, we develop dominance properties and a lower bound by extending those for a two-machine re-entrant flowshop problem (without sequence-dependent setup times) as well as heuristic algorithms, and present a branch and bound algorithm in which these dominance properties, lower bound, and heuristics are used. For evaluation of the performance of the branch and bound algorithm and heuristics, computational experiments are performed on randomly generated instances, and results are reported.     

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.     

An artificial neural network based heuristic for flow shop scheduling problems

The objective of this paper is to find a sequence of jobs in the flow shop to minimize makespan. A feed forward back propagation neural network is used to solve the problem. The network is trained with the optimal sequences of completely enumerated five, six and seven jobs, ten machine problem and this trained network is then used to solve the problem with greater number of jobs. The sequence obtained using artificial neural network (ANN) is given as the initial sequence to a heuristic proposed by Suliman and also to genetic algorithm (GA) as one of the sequences of the population for further improvement. The approaches are referred as ANN-Suliman heuristic and ANN-GA heuristic respectively. Makespan of the sequences obtained by these heuristics are compared with the makespan of the sequences obtained using the heuristic proposed by Nawaz, Enscore and Ham (NEH) and Suliman Heuristic initialized with Campbell Dudek and Smith (CDS) heuristic called as CDS-Suliman approach. It is found that the ANN-GA and ANN-Suliman heuristic approaches perform better than NEH and CDS-Suliman heuristics for the problems considered.