A new ant colony algorithm for makespan minimization in permutation flow shops

The problem of scheduling in permutation flow shop with the objective of minimizing the maximum completion time, or makespan, is considered. A new ant colony optimization algorithm is developed for solving the problem. A novel mechanism is employed in initializing the pheromone trails based on an initial sequence. Moreover, the pheromone trail intensities are limited between lower and upper bounds which change dynamically. When a complete sequence of jobs is constructed by an artificial ant, a local search is performed to improve the performance quality of the solution. The proposed ant colony algorithm is applied to Taillard’s benchmark problems. Computational experiments suggest that the algorithm yields better results than well-known ant colony optimization algorithms available in the literature.     

Heuristic for no-wait flow shops with makespan minimization based on total idle-time increments

No-wait flow shops with makespan minimization are classified as NP-hard. In this paper, the optimization objective is equivalently transformed to total idle-time minimization. The independence relationship between tasks is analyzed, and objective increment properties are established for the fundamental operators of the heuristics. The quality of the new schedules generated during a heuristic is judged only by objective increments and not by the traditional method, which computes and compares the objective of a whole schedule. Based on objective increments, the time complexity of the heuristic can be decreased by one order. A seed phase is presented to generate an initial solution according to the transformed objective. Construction and improvement phases are introduced by experimental analysis. The FCH （fast composite heuristic） is proposed and compared with the most effective algorithms currently available for the considered problem. Experimental results show that the effectiveness of the FCH is similar to that of the best methods but requires far less computation time. The FCH can also be efficient in real time scheduling and rescheduling for no-wait flow shops.     

A heuristic procedure for makespan minimization in job shops with multiple identical processors

Scheduling has been and continues to be a major issue in production planning. Job shop scheduling is one area where a considerable amount of research has been and continues to be pursued. Usual emphasis is on one machine per work center job shop scheduling. There appears to be very limited literature available on scheduling a job shop problem which requires scheduling of n jobs in m machine centers where each machine center may have k number of identical processors (though the number of identical processors may vary from one machine center to next). We discuss here, the problem of minimize of the makespan for such a job shop arrangement The problem can be represented by the symbol m x n x k.     

A heuristic for minimizing the makespan in no-idle permutation flow shops

The paper deals with the problem of finding a job sequence that minimizes the makespan in m-machine flow shops under the no-idle condition. This condition requires that each machine must process jobs without any interruption from the start of processing the first job to the completion of processing the last job. Since the problem is NP-hard, we propose a constructive heuristic for solving it that significantly outperforms heuristics known so far.     

Minimizing makespan in three-machine flow shops with deteriorating jobs

In this paper, a three-machine permutation flow shop scheduling problem with time-dependent processing times is considered. By the time-dependent processing times we mean that the job's processing time is an increasing function of its starting time. The objective is to find a sequence that minimizes the makespan. This problem is well known to be NP-hard. Several dominance properties and a lower bound are derived to speed up the elimination process of a branch-and-bound algorithm. Moreover, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational experiments on randomly generated problems are conducted to evaluate the branch-and-bound algorithm and heuristic algorithm. Computational results show that the proposed heuristic algorithm M-NEH perform effectively and efficiently.     

A note on 2-facial coloring of plane graphs

An l-facial coloring of a plane graph is a vertex coloring such that any two different vertices joined by a facial walk of length at most l receive distinct colors. It is known that every plane graph admits a 2-facial coloring using 8 colors [D. Král, T. Madaras, R. Škrekovski, Cyclic, diagonal and facial coloring, European J. Combin. 3-4 (26) (2005) 473-490]. We improve this bound for plane graphs with large girth and prove that if G is a plane graph with girth g?14 (resp. 10, 8) then G admits a 2-facial coloring using 5 colors (resp. 6, 7). Moreover, we give exact bounds for outerplanar graphs and K₄-minor free graphs.     

A note on robustness tolerances for combinatorial optimization problems

We consider so-called generic combinatorial optimization problem, where the set of feasible solutions is some family of nonempty subsets of a finite ground set with specified positive initial weights of elements, and the objective function represents the total weight of elements of the feasible solution. We assume that the set of feasible solutions is fixed, but the weights of elements may be perturbed or are given with errors. All possible realizations of weights form the set of scenarios.A feasible solution, which for a given set of scenarios guarantees the minimum value of the worst-case relative regret among all the feasible solutions, is called a robust solution. The maximum percentage perturbation of a single weight, which does not destroy the robustness of a given solution, is called the robustness tolerance of this weight with respect to the solution considered.In this paper we give formulae for computing the robustness tolerances with respect to an optimal solution obtained for some initial weights and we show that this can be done in polynomial time whenever the optimization problem is polynomially solvable itself.     

A note on 3-choosability of planar graphs

In this note, we prove that a planar graph is 3-choosable if it contains neither cycles of length 4, 7, and 9 nor 6-cycle with one chord. In particular, every planar graph without cycles of length 4, 6, 7, or 9 is 3-choosable. Together with other known parallel results, this completes a theorem on 3-choosability of planar graphs: planar graphs without cycles of length 4, i, j, 9 with i<j and i, j∈{5,6,7,8} are 3-choosable. Moreover, some further problems on this direction are proposed.     

A survey on makespan minimization in semi-online environments

We discuss variants of online scheduling on identical and uniformly related machines, where the objective is to minimize the makespan. All variants are such that some information regarding the input is provided in advance, and therefore these models are known as semi-online problems. Algorithms are analyzed with respect to the competitive ratio. We discuss the benefit arising from different kinds of available information and find that almost all variants allow one to reduce the competitive ratio significantly compared to the best possible competitive ratio for the corresponding pure online problem.     

A note on total colorings of 1-planar graphs

A 1-planar graph is a graph that can be drawn in the plane such that each edge is crossed by at most one other edge. In this paper we give an upper bound for the total chromatic number for 1-planar graphs with maximum degree at least 10.     

Family scheduling with batch availability in flow shops to minimize makespan

This paper addresses a batch scheduling problem in flow shop production systems, where job families are formed based on setup similarities. In order to improve setup efficiency, we consider batching decisions in our solution procedure. Due to its high practical relevance, the batch availability assumption is also adopted in this study. In the presence of sequence-dependent setup times, it is proved that a permutation flow shop is generally not optimal. Therefore, our objective is to determine solutions with inconsistent batches, which essentially lead to non-permutation schedules, to minimize makespan. After examining structural properties, we develop a tabu search algorithm with multiple neighbourhood functions. Computational results confirm the remarkable benefits of batching decisions. Our algorithm also outperforms some well-known and well-performing approaches.     

An improved NEH heuristic to minimize makespan in permutation flow shops

For over 20 years the NEH heuristic of Nawaz, Enscore, and Ham [A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, The International Journal of Management Science 1983;11:91–5] has been commonly regarded as the best heuristic for solving the NP-hard problem of minimizing the makespan in permutation flow shops. The strength of NEH lies mainly in its priority order according to which jobs are selected to be scheduled during the insertion phase. Framinan et al. [Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idle time or flowtime in the static permutation flowshop problem. International Journal of Production Research 2003;41:121–48] presented the results of an extensive study to conclude that the NEH priority order is superior to 136 different orders examined. Based upon the concept of Johnson's algorithm, we propose a new priority order combined with a simple tie-breaking method that leads to a heuristic that outperforms NEH for all problem sizes.     

A note on t-complementing permutations for graphs

In this note we present a necessary and sufficient condition for a permutation to be t-complementing which is a natural generalization of the well-known result concerning self-complementing permutations.     

A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem

This note considers the longest processing time heuristic for scheduling n independent jobs on two uniform parallel machines to minimize the makespan. A posterior worst-case performance ratio, by depending on the index of the latest job inserted in the machine where the makespan takes place, is developed for this heuristic, and some examples demonstrate that the ratio is tight.     

A note on binary sequence pairs with two-level correlation

In this letter, we present a new proof of the ideal two-level correlation binary sequence pairs introduced by Peng et al. We also provide a new construction of ideal two-level correlation binary sequence pair. As a co-product, new classes of difference set pairs can be derived.     

Remarks on the makespan minimization problem

In this brief article we consider the worst-case performance of a heuristic proposed for the problem of minimizing the overall completion time in scheduling a collection of independent tasks to a system of identical processors. It has been suggested that this heuristic, based on the familiar LPTrule, possesses a vastly improved worst-case behavior. We demonstrate that it instead shares LPT's asymptotic worst-case performance bound of 4/3.     

Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops

We propose a constructive and an iterated local search heuristic for minimizing the makespan in the non-permutation flow shop scheduling problem. Both heuristics are based on the observation that optimal non-permutation schedules often exhibit a permutation structure with a few local job inversions. In computational experiments we compare our heuristics to the best heuristics for finding non-permutation and permutation flow shop schedules, and evaluate the reduction in makespan and buffer size that can be achieved by non-permutation schedules.     

A note on the Hadwiger number of circular arc graphs

The intention of this note is to motivate the researchers to study Hadwiger's conjecture for circular arc graphs. Let η(G) denote the largest clique minor of a graph G, and let χ(G) denote its chromatic number. Hadwiger's conjecture states that η(G)?χ(G) and is one of the most important and difficult open problems in graph theory. From the point of view of researchers who are sceptical of the validity of the conjecture, it is interesting to study the conjecture for graph classes where η(G) is guaranteed not to grow too fast with respect to χ(G), since such classes of graphs are indeed a reasonable place to look for possible counterexamples. We show that in any circular arc graph G, η(G)?2χ(G)−1, and there is a family with equality. So, it makes sense to study Hadwiger's conjecture for this family.