Permutation-induced acyclic networks for the job shop scheduling problem

In the literature of the combinatorial optimization problems, it is a commonplace to find more than one mathematical model for the same problem. The significance of a model may be measured in terms of the efficiency of the solution algorithms that can be built upon it. The purpose of this article is to present a new network model for the well known combinatorial optimization problem – the job shop scheduling problem. The new network model has similar structure as the disjunctive graph model except that it uses permutations of jobs as decision variables instead of the binary decision variables associated with the disjunctive arcs. To assess the significance of the new model, the performances of exact branch-and-bound algorithmic implementations that are based on both the new model and the disjunctive graph model are compared.     

An approximation algorithm for the m-machine permutation flow shop scheduling problem with controllable processing times

The paper deals with the m-machine permutation flow shop scheduling problem in which job processing times, along with a processing order, are decision variables. It is assumed that the cost of processing a job on each machine is a linear function of its processing time and the overall schedule cost to be minimized is the total processing cost plus maximum completion time cost. A algorithm for the problem with m = 2 is provided; the best approximation algorithm until now has a worst-case performance ratio equal to . An extension to the m-machine (m ≥2) permutation flow shop problem yields an approximation algorithm with a worst-case bound equal to

Full-size image

, where is the worst-case performance ratio of a procedure used, in the proposed algorithm, for solving the (pure) sequencing problem. Moreover, examples which achieve this bound for = 1 are also presented.     

Using genetic algorithm to solve dynamic cell formation problem

In this paper, solving a cell formation (CF) problem in dynamic condition is going to be discussed using genetic algorithm (GA). Previous models presented in the literature contain some essential errors which will decline their advantageous aspects. In this paper these errors are discussed and a new improved formulation for dynamic cell formation (DCF) problem is presented. Due to the fact that CF is a NP-hard problem, solving the model using classical optimization methods needs a long computational time. Therefore the improved DCF model is solved using a proposed GA and the results are compared with the optimal solution and the efficiency of the proposed algorithm is discussed and verified.     

The flow shop problem with no-idle constraints: A review and approximation

The makespan minimization problem in flow shops with no-idle constraints on machines is considered. The latter means that each machine, once started, must process all its operations without intermediate idle time until all those operations are completed. The problem is known to be strongly NP-hard already for three machines. While being based on a geometrical approach, we propose several polynomial time heuristics (for the general case and for special cases of 3 and 4 machines) which provide asymptotically optimal solutions for the increasing number of jobs. A comprehensive review of relevant results is also presented.     

A new heuristic for open shop total completion time problem

The m  -machine open shop problem to minimize the sum of the completion times is investigated in our paper. First, a heuristic algorithm, Shortest Processing Time Block, is presented to deal with problem _Om|n=km|∑_Cj$O_m|n=\mathit{km}|\sum C_j$, where k   is positive integer. And then, the heuristic is extended to solve the general problem _Om‖∑_Cj$O_m\Vert \sum C_j$. It is proved that the heuristic is asymptotically optimal when the job number goes to infinity. At the end of this paper, numerical experimentation results show the effectiveness of the heuristic algorithm.     

Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration

In this paper, we address a two-machine flow shop scheduling problem under simple linear deterioration. By a simple linear deterioration function, we mean that the processing time of a job is a simple linear function of its execution start time. The objective is to find a sequence that minimizes total weighted completion time. Optimal schedules are obtained for some special cases. For the general case, several dominance properties and two lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational analysis on randomly generated problems is conducted to evaluate the branch-and-bound algorithm and heuristic algorithm.     

An O(n) algorithm for the variable common due date,minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

We consider the ordinary NP- hard two-machine flow shop problem with the objective of determining simultaneously a minimal common due date and the minimal number of tardy jobs. We present an O(n²) algorithm for the problem when the machines are ordered, that is, when each job has its smaller processing time on the first (second) machine. We also discuss the applicability of the proposed algorithm to the corresponding single-objective problem in which the common due date is given.     

A note of using effective immune based approach for the flow shop scheduling with buffers

This note considers flow shop scheduling with buffers. The objective is to minimize the makespan. As we know, such a problem has several applications in manufacturing and has gained wide attention both in academic and engineering fields. In this note, we propose an immune based approach (IA) to solve this NP-hard problem. Numerical results of 29 benchmark problems from the OR-Library are reported and compared with those of a hybrid genetic algorithm (HGA). As shown, the proposed IA is effective and robust. The solutions by proposed IA are superior to those of HGA reported in the literature. In addition, the average of the relative errors of the proposed IA is only 0.85% for 29 instances with infinite buffers. Limited numerical results show that, as expected, buffer size has a great impact on the scheduling objective especially for larger-scale instances, and there are also significant differences with or without buffers for all instances. But the effect of increasing buffer size from 1 up to 2, 4 or ∞ decreases drastically for all instances.     

Heuristic solution methods for the stochastic flow shop problem

We investigate the stochastic flow shop problem with m machines and general distributions for processing times. No analytic method exists for solving this problem, so we looked instead at heuristic methods. We devised three constructive procedures with modest computational requirements, each based on approaches that have been successful at solving the deterministic counterpart. We compared the performance of these procedures experimentally on a set of test problems and found that all of them achieve near-optimal performance.     

Solving a dynamic cell formation problem using metaheuristics

In this paper, solving a cell formation (CF) problem in dynamic condition is going to be discussed by using some traditional metaheuristic methods such as genetic algorithm (GA), simulated annealing (SA) and tabu search (TS). Most of previous researches were done under the static condition. Due to the fact that CF is a NP-hard problem, then solving the model using classical optimization methods needs a long computational time. In this research, a nonlinear integer model of CF is first given and then solved by GA, SA and TS. Then, the results are compared with the optimal solution and the efficiency of the proposed algorithms is discussed.     

Two-machine flow shop total tardiness scheduling problem with deteriorating jobs

This paper studies a two-machine scheduling problem with deteriorating jobs which their processing times depend on their waiting time. We develop a branch and bound algorithm to minimize the total tardiness criteria. A lower bound, several dominance properties and an initial upper bound derived from a heuristic algorithm are used to increase the speed of branch and bound algorithm and decrease its required memory space. Computational results are presented to evaluate effectiveness and efficiency of the algorithms.     

An alternative approach for unbalanced assignment problem via genetic algorithm

This paper presents an alternative approach using genetic algorithm to a new variant of the unbalanced assignment problem that dealing with an additional constraint on the maximum number of jobs that can be assigned to some agent(s). In this approach, genetic algorithm is also improved by introducing newly proposed initialization, crossover and mutation in such a way that the developed algorithm is capable to assign optimally all the jobs to agents. Computational results with comparative performance of the algorithm are reported for four test problems.     

A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem

This paper deals with a general job shop scheduling problem with multiple constraints, coming from printing and boarding industry. The objective is the minimization of two criteria, the makespan and the maximum lateness, and we are interested in finding an approximation of the Pareto frontier. We propose a fast and elitist genetic algorithm based on NSGA-II for solving the problem. The initial population of this algorithm is either randomly generated or partially generated by using a tabu search algorithm, that minimizes a linear combination of the two criteria. Both the genetic and the tabu search algorithms are tested on benchmark instances from flexible job shop literature and computational results show the interest of both methods to obtain an efficient and effective resolution method.     

A hybrid heuristic for the maximum clique problem

In this paper we present a heuristic based steady-state genetic algorithm for the maximum clique problem. The steady-state genetic algorithm generates cliques, which are then extended into maximal cliques by the heuristic. We compare our algorithm with three best evolutionary approaches and the overall best approach, which is non-evolutionary, for the maximum clique problem and find that our algorithm outperforms all the three evolutionary approaches in terms of best and average clique sizes found on majority of DIMACS benchmark instances. However, the obtained results are much inferior to those obtained with the best approach for the maximum clique problem.     

CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up

This paper addresses the vehicle routing problem with sequence-constrained delivery and pick-up (VRPDP). We propose a multi-phase constructive heuristic that clusters nodes based on proximity, orients them along a route using shrink-wrap algorithm and allots vehicles using generalized assignment procedure. We employ genetic algorithm for an intensive final search. Trials on a large number of test-problems have yielded encouraging results.     

An integer-programming-based heuristic for the balanced loading problem

This paper presents an efficient heuristic algorithm for the one-dimensional loading problem in which the goal is to pack homogeneous blocks of given length and weight in a container in such a way that the center of gravity of the packed blocks is as close to a target point as possible. The proposed algorithm is based on the approximation of this problem as a knapsack problem. This algorithm has the same computational complexity but a better worst-case performance than the algorithm recently proposed by Amiouny et al. [Oper. Res. 40 (1992) 238]. Moreover, the computational results also show that, in general, it performs better on randomly generated problems.     

An optimization heuristic for the berth scheduling problem

Berths are among the most important resources in a port. In this research we present an optimization-based approach for the berth scheduling problem, which is to determine the berthing time and space for each incoming ship. The neighborhood-search based heuristic treats the quay as a continuous space. In additional to basic physical requirements, this model takes several factors important in practice into consideration, including the first-come-first-served rule, clearance distance between ships, and possibility of ship shifting. Computational experience is provided.     

A hybrid single and dual population search procedure for the job shop scheduling problem

This paper presents a genetic algorithm and a scatter search procedure to solve the well-known job shop scheduling problem. In contrast to the single population search performed by the genetic algorithm, the scatter search algorithm splits the population of solutions in a diverse and high-quality set to exchange information between individuals in a controlled way. The extension from a single to a dual population, by taking problem specific characteristics into account, can be seen as a stimulator to add diversity in the search process. This has a positive influence on the important balance between intensification and diversification. Computational experiments verify the benefit of this diversity on the effectiveness of the meta-heuristic search process. Various algorithmic parameters from literature are embedded in both procedures and a detailed comparison is made. A set of standard instances is used to compare the different approaches and the best obtained results are benchmarked against heuristic solutions found in literature.     

Scheduling problem using genetic algorithm,simulated annealing and the effects of parameter values on GA performance

Genetics algorithms have been designed as general purpose optimisation methods. Simulated annealing simulates the cooling process of solid materials-known as annealing. However this analogy is limited to the physical movement of the molecules without involving complex thermodynamic systems. Physical annealing refers to the process of cooling a solid material so that it reaches a low energy state. Initially the solid is heated up to the melting point. Then it is cooled very slowly, allowing it is to come to thermal equilibrium at each temperature. This process of slow cooling is called annealing. The goal is to find the best arrangement of molecules that minimises the energy of the system, which is referred to as the ground state of the solid material. If the cooling process is fast, the solid will not attain the ground state, but a locally optimal structure. In this paper presents a general purpose schedule optimiser for manufacturing shop scheduling using genetic algorithms and simulated annealing. Then, the ‘uniform order-based’ crossover and mutation operators and novel general effects of parameter values on minimised objective value are presented.