A flexible flowshop problem with total flow time minimization

In this study, we consider total flow time problem in a flexible flowshop environment. We develop a branch and bound algorithm to find the optimal schedule. The efficiency of the algorithm is enhanced by upper and lower bounds and a dominance criterion. Computational experience reveals that the algorithm solves moderate sized problems in reasonable solution times.     

Total tardiness minimization in permutation flowshop with deterioration consideration

In this paper, we consider a permutation flowshop scheduling problem with deteriorating jobs. The objective is to minimize the total tardiness of all jobs. A branch-and-bound algorithm incorporating with a dominance property and a lower bound is developed. Furthermore, two metaheuristic algorithms, the simulated annealing algorithm, and the particle swarm optimization method, are proposed. Finally, computational studies are given.     

Minimizing total tardiness on a two-machine re-entrant flowshop

We present a branch and bound algorithm for a two-machine re-entrant flowshop scheduling problem with the objective of minimizing total tardiness. In the re-entrant flowshop considered here, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2. By regarding a job as a pair of sub-jobs, each of which represents a pass through the two machines, we develop dominance properties, a lower bound and heuristic algorithms for the problem, and use these to develop a branch and bound algorithm. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems and results are reported. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 20 sub-jobs in a reasonable amount of CPU time, and the average percentage gap of the heuristic solutions is about 13%.     

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.     

Hybrid genetic algorithm for permutation flowshop scheduling problems with total flowtime minimization

In this paper, a HGA (hybrid genetic algorithm) is proposed for permutation flowshop scheduling problems (PFSP) with total flowtime minimization, which are known to be NP-hard. One of the chromosomes in the initial population is constructed by a suitable heuristic and the others are yielded randomly. An artificial chromosome is generated by a weighted simple mining gene structure, with which a new crossover operator is presented. Additionally, two effective heuristics are adopted as local search to improve all generated chromosomes in each generation. The HGA is compared with one of the most effective heuristics and a recent meta-heuristic on 120 benchmark instances. Experimental results show that the HGA outperforms the other two algorithms for all cases. Furthermore, HGA obtains 115 best solutions for the benchmark instances, 92 of which are newly discovered.     

Solution of the NP-hard total tardiness minimization problem in scheduling theory

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1‖ΣT _j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. Algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O(n ²Σp _j ), where n is the number of jobs and p _j is the processing time of the jth job (j = 1, 2, …, n).     

A note on the equivalence of two heuristics to minimize total tardiness

Over the last thirty years, many researchers have studied single machine static and deterministic scheduling with the objective of minimizing total tardiness. It has been established that the tardiness problem is NP-hard. So it is unlikely that a polynomial time algorithm can be found for developing optimal solutions to this problem. The Modified Due Date rule (MDD) is generally considered to be an efficient heuristic that deals with the tardiness problem. Recently, Panwalkar et al. have proposed the PSK rule as effective in dealing with tardiness. The purpose of this paper is to show that the PSK rule is an implementation of the MDD rule. Furthermore, the relationship between the MDD rule and the WI (Wilkeson and Irwin) rule is clarified.     

Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date

This paper deals with the total weighted tardiness minimization with a common due date on a single machine. The best previous approximation algorithm for this problem was recently presented in [H. Kellerer, V.A. Strusevich, A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date, Theoretical Computer Science 369 (2006) 230-238] by Kellerer and Strusevich. They proposed a fully polynomial time approximation scheme (FPTAS) of O((n⁶logW)/ε³) time complexity (W is the sum of weights, n is the number of jobs and ε is the error bound). For this problem, we propose a new approach to obtain a more effective FPTAS of O(n²/ε) time complexity. Moreover, a more effective and simpler dynamic programming algorithm is designed.     

Performance guarantees for flowshop heuristics to minimize makespan

This paper reviews the known worst-case ratios and absolute performance guarantees of various flowshop heuristics to minimize makespan. The absolute and worst-case performance ratio bounds are compared using probabilistic analysis. The best absolute performance bound is shown to outperform the tightest worst-case ratio bound with 99% probability when a certain minimum number of jobs is present. Thus, probabilistic analysis may provide a bridge between the absolute and worst-case performance guarantees of heuristic algorithms.     

A Petri Net based algorithm for minimizing total tardiness in flexible manufacturing systems

Petri Nets have been extensively used for modeling and simulating of the dynamics of flexible manufacturing systems. Petri Nets can capture features such as parallel machines, alternative routings, batch sizes, multiplicity of resources, to name but a few. However, Petri Nets have not been very popular for scheduling in manufacturing due to the Petri Net “state explosion” combined with the NP-hard nature of many of such problems. A promising approach for scheduling consists of generating only portions of the Petri Net state space with heuristic search methods. Thus far, most of this scheduling work with Petri Nets has been oriented to minimize makespan. The problem of minimizing total tardiness and other due date-related criteria has received little attention. In this paper, we extend the Beam A^* Search algorithm presented in a previous work with capability to handle the total tardiness criterion. Computational tests were conducted on Petri Net models of both flexible job shop and flexible manufacturing systems. The results suggest that the Petri Net approach is also valid to minimize due date related criteria in flexible systems.     

Makespan minimization in machine dominated flowshop

In a flowshop scheduling problem, a set of jobs is processed by a set of machines. The jobs follow the same sequence in all machines. We study the flowshop scheduling problem under a new case of machine dominance that is often found in the manufacturing of computers and electronic devices. We provide a formula for makespan value for a given sequence, show that the makespan value depends only on certain jobs in the sequence, and present an algorithm that finds a sequence with minimum makespan. Numerical examples of the solution approaches are provided.     

Evaluation of greedy,myopic and less-greedy heuristics for the single machine,total tardiness problem

Simple, yet highly effective modifications to the net benefit of relocation (NBR) heuristic of Holsenback and Russell provide significant improvements in solution quality without any increase in computational effort by tempering the greedy nature of the original NBR heuristic. Two lemmas reduce the size of the search while adhering to optimality conditions. Experimentation compares the modified NBR heuristic (M-NBR) with the two leading heuristics of the literature. Testing on 25, 50 and 100-job problems over a wide range of due dates and tardiness factors shows the M-NBR algorithm to be the best single-pass heuristic to date. We show that a composite heuristic, employing the better of the M-NBR and another leading heuristic solution, consistently produces near-optimal solutions with negligible CPU requirements.     

Beam search heuristics for quadratic earliness and tardiness scheduling

In this paper, we present beam search heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. These heuristics include classic beam search procedures, as well as filtered and recovering algorithms. We consider three dispatching heuristics as evaluation functions, in order to analyse the effect of different rules on the performance of the beam search procedures. The computational results show that using better dispatching heuristics improves the effectiveness of the beam search algorithms. The performance of the several heuristics is similar for instances with low variability. For high variability instances, however, the detailed, filtered and recovering beam search (RBS) procedures clearly outperform the best existing heuristic. The detailed beam search algorithm performs quite well, and is recommended for small- to medium-sized instances. For larger instances, however, this procedure requires excessive computation times, and the RBS algorithm then becomes the heuristic of choice.     

Randomized heuristics for handover minimization in mobility networks

A mobile device connects to the cell tower (base station) from which it receives the strongest signal. As the device moves it may connect to a series of towers. The process in which the device changes the base station it is connected to is called handover. A cell tower is connected to a radio network controller (RNC) which controls many of its operations, including handover. Each cell tower handles an amount of traffic and each radio network controller has capacity to handle a maximum amount of traffic from all base stations connected to it. Handovers between base stations connected to different RNCs tend to fail more often than handovers between base stations connected to the same RNC. Handover failures result in dropped connections and therefore should be minimized. The Handover Minimization Problem is to assign towers to RNCs such that RNC capacity is not violated and the number of handovers between base stations connected to different RNCs is minimized. We describe an integer programming formulation for the handover minimization problem and show that state-of-the-art integer programming solvers can solve only very small instances of the problem. We propose several randomized heuristics for finding approximate solutions of this problem, including a GRASP with path-relinking for the generalized quadratic assignment problem, a GRASP with evolutionary path-relinking, and a biased random-key genetic algorithm. Computational results are presented.     

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.     

An evaluation of heuristics for scheduling a non-delay permutation flow shop with family setups to minimize total earliness and tardiness

This paper presents several procedures for developing non-delay schedules for a permutation flow shop with family setups when the objective is to minimize total earliness and tardiness. These procedures consist of heuristics that were found to be effective for minimizing total tardiness in flow shops without family setups, modified to consider family setups and the total earliness and tardiness objective. These procedures are tested on several problem sets with varying conditions. The results show that variable greedy algorithms are effective when solving small problems, but using a genetic algorithm that includes a neighbourhood defined by the sequence of batches of jobs belonging to the same set-up family is effective when solving medium- or large-sized problems. The results also show that if setup times can be reduced a significant reduction in total earliness and tardiness could result.     

A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion

In this paper, we present a discrete artificial bee colony algorithm to solve the no-idle permutation flowshop scheduling problem with the total tardiness criterion. The no-idle permutation flowshop problem is a variant of the well-known permutation flowshop scheduling problem where idle time is not allowed on machines. In other words, the start time of processing the first job on a given machine must be delayed in order to satisfy the no-idle constraint. The paper presents the following contributions: First of all, a discrete artificial bee colony algorithm is presented to solve the problem on hand first time in the literature. Secondly, some novel methods of calculating the total tardiness from makespan are introduced for the no-idle permutation flowshop scheduling problem. Finally, the main contribution of the paper is due to the fact that a novel speed-up method for the insertion neighborhood is developed for the total tardiness criterion. The performance of the discrete artificial bee colony algorithm is evaluated against a traditional genetic algorithm. The computational results show its highly competitive performance when compared to the genetic algorithm. Ultimately, we provide the best known solutions for the total tardiness criterion with different due date tightness levels for the first time in the literature for the Taillard’s benchmark suit.     

Evaluation of leading heuristics for the single machine tardiness problem

A recent paper on the single machine tardiness problem by Panwalker, Smith and Koulamas [8] disputes experimental results of Holsenback and Russell [5] that indicated the Net Benefit of Relocation (NBR) heuristic provides significant improvement over the adjacent pairwise interchange (API) routine of Fry et al. [4], which in turn, was reported to show better solution quality than the Wilkerson-Irwin (W-I) heuristic ([13]). Panwalker et al. [8] claim that the P-S-K heuristic yields better results than the other methods over a wide range of problems and suggest that the NBR heuristic is not only inferior to the P-S-K heuristic, but also inferior to the API and W-I routines. This paper will shed new light on the quality of the experimentation of Panwalker et al. [8] and show that in general, the P-S-K heuristic is inferior to the NBR heuristic.     

A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem

In this paper, a particle swarm optimization algorithm (PSO) is presented to solve the permutation flowshop sequencing problem (PFSP) with the objectives of minimizing makespan and the total flowtime of jobs. For this purpose, a heuristic rule called the smallest position value (SPV) borrowed from the random key representation of Bean [J.C. Bean, Genetic algorithm and random keys for sequencing and optimization, ORSA Journal of Computing 6(2) (1994) 154–160] was developed to enable the continuous particle swarm optimization algorithm to be applied to all classes of sequencing problems. In addition, a very efficient local search, called variable neighborhood search (VNS), was embedded in the PSO algorithm to solve the well known benchmark suites in the literature. The PSO algorithm was applied to both the 90 benchmark instances provided by Taillard [E. Taillard, Benchmarks for basic scheduling problems, European Journal of Operational Research, 64 (1993) 278–285], and the 14,000 random, narrow random and structured benchmark instances provided by Watson et al. [J.P. Watson, L. Barbulescu, L.D. Whitley, A.E. Howe, Contrasting structured and random permutation flowshop scheduling problems: Search space topology and algorithm performance, ORSA Journal of Computing 14(2) (2002) 98–123]. For makespan criterion, the solution quality was evaluated according to the best known solutions provided either by Taillard, or Watson et al. The total flowtime criterion was evaluated with the best known solutions provided by Liu and Reeves [J. Liu, C.R. Reeves, Constructive and composite heuristic solutions to the P∥∑C_i scheduling problem, European Journal of Operational Research 132 (2001) 439–452], and Rajendran and Ziegler [C. Rajendran, H. Ziegler, Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155(2) (2004) 426–438]. For the total flowtime criterion, 57 out of the 90 best known solutions reported by Liu and Reeves, and Rajendran and Ziegler were improved whereas for the makespan criterion, 195 out of the 800 best known solutions for the random and narrow random problems reported by Watson et al. were improved by the VNS version of the PSO algorithm.