A high quality solution constructive heuristic for flow shop sequencing

This paper addresses the flow shop sequencing problem. Following an investigation of the problem characteristics, a property of this scheduling problem is presented, and is used for the development of a new constructive heuristic with the objective of minimizing the total time to complete the schedule (makespan). The new method, denoted by N&M, is compared with the best constructive heuristic reported in the literature, named NEH. Results from computational experience have shown that for problems having up to 10 machines and 100 jobs, the new heuristic outperforms, on average, the NEH heuristic. There is no significant difference regarding computation effort for both NEH and N&M heuristics.     

A partial enumeration heuristic for multi-objective flowshop scheduling problems

This paper addresses the flowshop scheduling problem with multiple performance objectives in such a way as to provide the decision maker with approximate Pareto optimal solutions. It is well known that the partial enumeration constructive heuristic NEH and its adaptations perform well for single objectives such as makespan, total tardiness and flowtime. In this paper, we develop a similar heuristic using the concept of Pareto dominance when comparing partial and complete schedules. The heuristic is tested on problems involving combinations of the above criteria. For the two-machine case, and the pairs of objectives: (i) makespan and maximum tardiness, (ii) makespan and total tardiness, the heuristic is compared with branch-and-bound algorithms proposed in the literature. For two and more than two machines, and the criteria combinations considered in this article, the heuristic performance is tested against constructive heuristics reported in the literature. By means of an illustrative example, it is shown that a genetic algorithm from the literature performs better when starting from heuristic solutions rather than random solutions.     

On the automatic discovery of variants of the NEH procedure for flow shop scheduling using genetic programming

We use genetic programming to find variants of the well-known Nawaz, En-score and Ham (NEH) heuristic for the permutation flow shop problem. Each variant uses a different ranking function to prioritize operations during schedule construction. We have tested our ideas on problems where jobs have release times, due dates, and weights and have considered five objective functions: makespan, sum of tardiness, sum of weighted tardiness, sum of completion times and sum of weighted completion times. The implemented genetic programming system has been carefully tuned and used to generate one variant of NEH for each objective function. The new NEHs, obtained with genetic programming, have been compared with the original NEH and randomized NEH versions on a large set of benchmark problems. Our results indicate that the NEH variants discovered by genetic programming are superior to the original NEH and its stochastic version on most of the problems investigated.     

A fuzzy greedy heuristic for permutation flow-shop scheduling

This paper describes a polynomial-time heuristic for the permutation flow-shop scheduling problem with the makespan criterion. The proposed method consists of two phases: arranging the jobs in priority order and then constructing a sequence. A fuzzy greedy evaluation function is employed to prioritize the jobs for incorporating into the construction phase of the heuristic. Computational experiments using standard benchmark problems indicate an improvement of the new heuristic over the well-known Nawaz, Enscore and Ham (NEH) heuristic. It will be seen that the NEH heuristic is a special case of our more general heuristic.     

A heuristic for single machine scheduling with early and tardy costs

The problem of scheduling jobs with distinct ready times and due dates in a single machine to minimise the total earliness and tardiness penalties is considered. A constructive heuristic, which determines the sequence of jobs and simultaneously inserts idle times, is proposed. Adjacent pairwise interchange is then applied to the schedule obtained. For problems involving at most 12 jobs the heuristic solutions are compared to optimal solutions. For larger problems with up to 80 jobs the heuristic is tested against a local search based on pairwise interchanges and four dispatching rules presented in the literature. In each case, idle times are optimally inserted.     

Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time

This study considers a hybrid assembly-differentiation flowshop scheduling problem (HADFSP), in which there are three production stages, including components manufacturing, assembly, and differentiation. All the components of a job are processed on different machines at the first stage. Subsequently, they are assembled together on a common single machine at the second stage. At the third stage, each job of a particular type is processed on a dedicated machine. The objective is to find a job schedule to minimize total flow time (TFT). At first, a mixed integer programming (MIP) model is formulated and then some properties of the optimal solution are presented. Since the NP-hardness of the problem, two fast heuristics (SPT-based heuristic and NEH-based heuristic) and three hybrid meta-heuristics (HGA-VNS, HDDE-VNS and HEDA-VNS) are developed for solving medium- and large-size problems. In order to evaluate the performances of the proposed algorithms, a lower bound for the HADFSP with TFT criteria (HADFSP-TFT) is established. The MIP model and the proposed algorithms are compared on randomly generated problems. Computational results show the effectiveness of the MIP model and the proposed algorithms. The computational analysis indicates that, in average, the HDDE-VNS performs better and more robustly than the other two meta-heuristics, whereas the NEH heuristic consume little time and could reach reasonable solutions.     

The dynamic vehicle rescheduling problem

The pre-planned schedules of a transportation company are often disrupted by unforeseen events. As a result of a disruption, a new schedule has to be produced as soon as possible. This process is called the vehicle rescheduling problem, which aims to solve a single disruption and restore the order of transportation. However, there are multiple disruptions happening over a “planning unit” (usually a day), and all of them have to be addressed to achieve a final feasible schedule. From an operations management point of view the quality of the final solution has to be measured by the combined quality of every change over the horizon of the “planning unit”, not by evaluating the solution of each disruption as a separate problem. The problem of finding an optimal solution where all disruptions of a “planning unit” are addressed will be introduced as the dynamic vehicle rescheduling problem (DVRSP). The disruptions of the DVRSP arrive in an online manner, but giving an optimal final schedule for the “planning unit” would mean knowing all information in advance. This is not possible in a real-life scenario, which means that heuristic solution methods have to be considered. In this paper, we present a recursive and a local search algorithm to solve the DVRSP. In order to measure the quality of the solutions given by the heuristics, we introduce the so-called quasi-static DVRSP, a theoretical problem where all the disruptions are known in advance. We give two mathematical models for this quasi-static problem, and use their optimal solutions to evaluate the quality of our heuristic results. The heuristic methods for the dynamic problem are tested on different random instances.     

Tabu search for non-permutation flowshop scheduling problem with minimizing total tardiness

This paper deals with the non-permutation flowshop problem which means that the job sequences are allowed to be different on machines. The objective function is minimizing the total tardiness. Firstly, three mixed-integer linear programming (MILP) models for non-permutation flowshop problems are described, and then are analyzed and assessed their relative effectiveness. Secondly, two Tabu search based algorithms, denoted by LH1 and LH2, are proposed to solve the complicated non-permutation flowshop problems. The algorithms are constructed on specific neighborhood structures which enable the searching method effective. Finally, the performance is evaluated against Taillard’s famous benchmark. Computational experiments show that the proposed algorithms, LH1 and LH2, are significantly superior to the L_TS algorithm. And the percentages of improved permutation flowshop instances by LH1 and LH2 algorithms are about 87.8% and 98.3% with respect to total tardiness, respectively. The non-permutation schedules also have achieved significant improvement in four different scenarios of due dates. Consequently, average percentage improvement (API) is 14.52% for flowshop problems with low tardiness factors. It is evident that exploring non-permutation schedule is effective and necessary for low tardiness factors.     

Scheduling preemptive open shops to minimize total tardiness

This article considers the problem of scheduling preemptive open shops to minimize total tardiness. The problem is known to be NP-hard. An efficient constructive heuristic is developed for solving large-sized problems. A branch-and-bound algorithm that incorporates a lower bound scheme based on the solution of an assignment problem as well as various dominance rules are presented for solving medium-sized problems. Computational results for the 2-machine case are reported. The branch-and-bound algorithm can handle problems of up to 30 jobs in size within a reasonable amount of time. The solution obtained by the heuristic has an average deviation of less than 2% from the optimal value, while the initial lower bound has an average deviation of less than 11% from the optimal value. Moreover, the heuristic finds approved optimal solutions for over 65% of the problems actually solved.     

Flow shop scheduling jobs with position-dependent processing times

The paper is devoted to some flow shop scheduling problems, where job processing times are defined by functions dependent on their positions in the schedule. An example is constructed to show that the classical Johnson's rule is not the optimal solution for two different models of the two-machine flow shop scheduling to minimize makespan. In order to solve the makespan minimization problem in the two-machine flow shop scheduling, we suggest Johnson's rule as a heuristic algorithm, for which the worst-case bound is calculated. We find polynomial time solutions to some special cases of the considered problems for the following optimization criteria: the weighted sum of completion times and maximum lateness. Some furthermore extensions of the problems are also shown.     

A genetic algorithm for flow shop scheduling problems

Many scheduling problems are NP-hard problems. For such NP-hard combinatorial optimization problems, heuristics play a major role in searching for near-optimal solutions. In this paper we develop a genetic algorithm-based heuristic for the flow shop scheduling problem with makespan as the criterion. The performance of the algorithm is compared with the established NEH algorithm. Computational experience indicates that genetic algorithms can be good techniques for flowshop scheduling problems.     

A heuristic for scheduling problems,especially for scheduling farm operations

Scheduling problems in agriculture are often solved using techniques such as linear programming (the multi-period formulation) and dynamic programming. But it is difficult to obtain an optimal schedule with these techniques for any but the smallest problems, because the model is unwieldly and much time is needed to solve the problem. Therefore, a new algorithm, a heuristic, has been developed to handle scheduling problems in agriculture. It is based on a search technique (i.e. hill-climbing) supported by a strong heuristic evaluation function. In this paper the heuristic performance is compared with dynamic programming. The heuristic offers near-optimal solutions and is much faster than the dynamic programming model. When tested against dynamic programming the difference in results was about 3%. This heuristic could probably also be applied in an industrial environment (e.g. agribusiness or road construction).     

Single machine scheduling under market uncertainty

This paper considers single machine scheduling problems where job processing times are known and deterministic but where the reward received upon completion of a job changes stochastically over time according to Brownian motion. The objectives of maximizing expected net-present-value (NPV), minimizing the variance of NPV and maximizing the probability of achieving a minimum benchmark NPV are considered. For non-preemptive static list policies complexity results and branch and bound procedures are presented. The branch and bound procedures are shown to be effective for problem instances with 20–25 jobs. For the problem of maximizing NPV with non-preemptive dynamic policies the optimal static schedule is shown through empirical testing to be as good as a greedy heuristic and to be near optimal when the variance is not large.     

A search heuristic for the sequence-dependent economic lot scheduling problem

Almost all of the research on the economic lot scheduling problem (ELSP) has assumed that setup times are sequence-independent even though sequence-dependent problems are common in practice. Furthermore, most of the solution approaches that have been developed solve for a single optimal schedule when in practice it is more important to provide managers with a range of schedules of different length and complexity. In this paper, we develop a heuristic procedure to solve the ELSP problem with sequence-dependent setups. The heuristic provides a range of solutions from which a manager can choose, which should prove useful in an actual stochastic production environment. We show that our heuristic can outperform Dobson's heuristic when the utilization is high and the sequence-dependent setup times and costs are significant.     

A New Heuristic Method for the Permutation Flow Shop Scheduling Problem

A new heuristic method for the permutation flow shop scheduling problem is presented and compared with two other heuristics named NEH and SPIRIT. The new heuristic method is based on a property of the scheduling problem that provides an upper bound on the idle time of the last machine between any two adjacent jobs regardless of their position in the sequence of jobs. The results from computational experience have shown that the new heuristic outperforms, in solution quality, all others for problems having up to 50 jobs and 30 machines.     

Single-machine scheduling to minimize total absolute differences in waiting times with deteriorating jobs

In this paper we consider a single-machine scheduling problem with simple linear deterioration. By simple linear deterioration, we mean that the processing time of a job is a simple linear function of its execution starting time and its deterioration rate. The objective is to find a schedule that minimizes total absolute differences in waiting times. We show that the optimal schedule is V-shaped: jobs are arranged in descending order of their deterioration rates if they are placed before the job with the smallest deterioration rate, but in ascending order of their deterioration rates if placed after it. We prove other several properties of an optimal schedule, and introduce two efficient heuristic algorithms that are tested against a lower bound. We also provide computational results to evaluate the performance of the heuristic algorithms.     

A Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem

In this paper, we present a branch-and-bound approach for solving a two-machine flow shop scheduling problem, in which the objective is to minimize a weighted combination of job flowtime and schedule makespan. Experimental results show that the algorithm works very well for certain special cases and moderately well for others. In fact, it is able to produce optimal schedules for 500-job problems in which the second machine dominates the first machine. It is also shown that the algorithm developed to provide an upper bound for the branch-and-bound is optimal when processing times for jobs are the same on both machines. The primary reason for developing the branch-and-bound approach is that its results can be used to guide other heuristic techniques, such as simulated annealing, tabu search and genetic algorithms, in their search for optimal solutions for larger problems.     

An empirical analysis of the optimality rate of flow shop heuristics

If a certain optimization problem is NP-hard or even harder, one could expect that the chances of solving it optimally should rather decrease with an increase of the problem size. We reveal, however, that the opposite occurs for a strongly NP-hard problem, which requires sequencing n jobs through an m machine flow shop so as to minimize the makespan. In particular, we empirically examine optimality rates (the probability of being optimal) of the famous NEH heuristic of Nawaz et al. [Nawaz, M., Enscore, Jr., E., Ham, I., 1983. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, The International Journal of Management Science 11, 91–95] and two improved versions of NEH. By using millions of simulation trials and a new effective lower bound on the shortest makespan, we observe relatively high optimality rates of the three heuristics for small values of m. Rather surprisingly, for larger values of n, the heuristics become more frequently optimal as n increases. Neither theoretical nor empirical studies of optimality rates of flow shop heuristics have been conducted so far, and – to the best of our knowledge – no similar studies are known in the field of operations research.     

Single facility scheduling with multiple job classes

This paper considers a static single facility scheduling problem where jobs are divided into several mutually exclusive classes. The jobs in a given class need not be processed together. In addition to a known processing time for each job, there is a switching time involved which depends on the class of the job immediately preceding a job. A heuristic algorithm is proposed to find a minimum mean flow time schedule. The effectiveness of the proposed heuristic algorithm is empirically evaluated and found to indicate that the solutions obtained from this heuristic algorithm are often close to optimal.     

Minimizing maximum tardiness and number of tardy jobs on parallel machines subject to minimum flow-time

This paper considers the problems of scheduling jobs on parallel identical machines where an optimal schedule is defined as one that gives the smallest maximum tardiness (or the minimum number of tardy jobs) among the set of schedules with optimal total flow-time (the sum of the completion times of all jobs). We show that these problems are unary NP-Hard, develop lower bounds for these two secondary criteria problems, and describe heuristic algorithms for their solution. Results of a computational study show that the proposed heuristic algorithms are quite effective and efficient in solving these hierarchical criteria scheduling problems.