A new neighborhood and tabu search for the Blocking Job Shop

The Blocking Job Shop is a version of the job shop scheduling problem with no intermediate buffers, where a job has to wait on a machine until being processed on the next machine. We study a generalization of this problem which takes into account transfer operations between machines and sequence-dependent setup times. After formulating the problem in a generalized disjunctive graph, we develop a neighborhood for local search. In contrast to the classical job shop, there is no easy mechanism for generating feasible neighbor solutions. We establish two structural properties of the underlying disjunctive graph, the concept of closures and a key result on short cycles, which enable us to construct feasible neighbors by exchanging critical arcs together with some other arcs. Based on this neighborhood, we devise a tabu search algorithm and report on extensive computational experience, showing that our solutions improve most of the benchmark results found in the literature.     

Paths, trees and matchings under disjunctive constraints

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints.We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge.Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.     

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.     

A Precedence Graph Algorithm for the Shop Scheduling Problem

This paper is concerned with the development of a precedence graph algorithm for solving certain combinatorial problems. This algorithm is applied mainly to job-shop scheduling problems; however, the extension of its applicability can be demonstrated by considering project scheduling, travelling salesman and explosion problems. The algorithm employs linear graphs to construct the quantified precedence matrix, a powerful criterion to resolve the conflict between the tied operations, and the use of a quasi-Boolean procedure to evaluate the obtained sequence.Considerable experimentation is conducted to evaluate the performance of the algorithm. Significant results pertaining to the quality of solution, the computation time and the number of iterations and conflicts encountered in obtaining a solution are given.     

Surgical case scheduling as a generalized job shop scheduling problem

Surgical case scheduling allocates hospital resources to individual surgical cases and decides on the time to perform the surgeries. This task plays a decisive role in utilizing hospital resources efficiently while ensuring quality of care for patients. This paper proposes a new surgical case scheduling approach which uses a novel extension of the Job Shop scheduling problem called multi-mode blocking job shop (MMBJS). It formulates the MMBJS as a mixed integer linear programming (MILP) problem and discusses the use of the MMBJS model for scheduling elective and add-on cases. The model is illustrated by a detailed example, and preliminary computational experiments with the CPLEX solver on practical-sized instances are reported.     

Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops

In this paper, we consider a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities (Wafer Fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic uses a disjunctive graph to decompose the overall scheduling into scheduling problems for single tool groups. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). In previous research, only subproblem solution procedures based on dispatching rules have been considered. In this paper, we are interested in how much we can gain in terms of TWT if we apply more sophisticated subproblem solution procedures like genetic algorithms for parallel machine scheduling. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the suggested subproblem solution procedures. It turns out that using near to optimal subproblem solution procedures leads in many situations to improved results compared to dispatching-based subproblem solution procedures.     

Local adjustments: A general algorithm

Processing a set of operations on a single processor that can handle at most one job at a time is an underlying issue of many combinatorial optimization problems, and especially classical scheduling problems, such as job-shops, flow-shops and other X-shops. The main goal of local operations is to narrow the time-windows of operations for that kind of disjunctive scheduling problem.In this paper, we investigate the properties of local adjustments and provide a unified and efficient framework for the combination of the main adjustment procedures. Beyond its rapid prototyping feature, our implementation is proved to guarantee a good stability property that finally leads to a better convergence process. Computational experiments on single machine and on job-shop scheduling problems are reported.     

平面图的Alcuin数

广义渡河问题是一类重要的组合优化问题,它是经典的狼-羊-卷心菜游戏的推广。冲突图是一个图,这个图的任意两个点所代表的物品不相容时(例如,狼和羊代表的物品不相容),则在这两个点之间连结一条边。渡河覆盖问题的目的是确定冲突图全部点所代表的物品从河的一岸安全地摆渡到河的对岸时所需船的最小容量,而冲突图的Alcuin数定义这个最小容量。本文讨论了平面图的Alcuin数, 给出了该类图Alcuin数的完全刻画。     

Constraint Propagation and Problem Decomposition: A Preprocessing Procedure for the Job Shop Problem

In recent years, constraint propagation techniques have been shown to be highly effective for solving difficult scheduling problems. In this paper, we present an algorithm which combines constraint propagation with a problem decomposition approach in order to simplify the solution of the job shop scheduling problem. This is mainly guided by the observation that constraint propagation is more effective for small problem instances. Roughly speaking, the algorithm consists of deducing operation sequences that are likely to occur in an optimal solution of the job shop scheduling problem (JSP).The algorithm for which the name edge-guessing procedure has been chosen – since with respect to the job shop scheduling problem (JSP) the deduction of machine sequences is mainly equivalent to orienting edges in a disjunctive graph – can be applied in a preprocessing step, reducing the solution space, thus speeding up the overall solution process. In spite of the heuristic nature of edge-guessing, it still leads to near-optimal solutions. If combined with a heuristic algorithm, we will demonstrate that given the same amount of computation time, the additional application of edge-guessing leads to better solutions. This has been tested on a set of well-known JSP benchmark problem instances.     

The Ferry Cover Problem on Regular Graphs and Small-Degree GraphsThe Ferry Cover Problem on Regular Graphs and Small-Degree Graphs

The ferry problem may be viewed as generalizations of the classical wolf-goatcabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.     

Complexity of the job insertion problem in multi-stage scheduling

The job insertion problem in multi-stage scheduling is: given a schedule for n jobs and an additional job, find a feasible insertion of the additional job into the schedule that minimizes the resulting makespan. We prove that finding the optimal job insertion is NP-hard for flow shops and open shops.     

The Ferry Cover Problem on Regular Graphs and Small-Degree Graphs

The ferry problem may be viewed as generalizations of the classical wolf-goat-cabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.     

Precedence constrained parallel-machine scheduling of position-dependent jobs

We consider parallel-machine job scheduling problems with precedence constraints. Job processing times are variable and depend on positions of jobs in a schedule. The objective is to minimize the maximum completion time or the total weighted completion time. We specify certain conditions under which the problem can be solved by scheduling algorithms applied earlier for fixed job processing times.     

A heuristic approach for dividing graphs into bi-connected components with a size constraint

In this paper we propose a new problem of finding the maximal bi-connected partitioning of a graph with a size constraint (MBCPG-SC). With the goal of finding approximate solutions for the MBCPG-SC, a heuristic method is developed based on the open ear decomposition of graphs. Its essential part is an adaptation of the breadth first search which makes it possible to grow bi-connected subgraphs. The proposed randomized algorithm consists of growing several subgraphs in parallel. The quality of solutions generated in this way is further improved using a local search which exploits neighboring relations between the subgraphs. In order to evaluate the performance of the method, an algorithm for generating pseudo-random unit disc graphs with known optimal solutions is created. Computational experiments have also been conducted on graphs representing electrical distribution systems for the real-world problem of dividing them into a system of fault tolerant interconnected microgrids. The experiments show that the proposed method frequently manages to find optimal solutions and has an average error of only a few percent to known optimal solutions. Further, it manages to find high quality approximate solutions for graphs having up to 10,000 nodes in reasonable time.     

Complexity of two coloring problems in cubic planar bipartite mixed graphs

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].     

A MILP model for an extended version of the Flexible Job Shop Problem

A MILP model for an extended version of the Flexible Job Shop Scheduling problem is proposed. The extension allows the precedences between operations of a job to be given by an arbitrary directed acyclic graph rather than a linear order. The goal is the minimization of the makespan. Theoretical and practical advantages of the proposed model are discussed. Numerical experiments show the performance of a commercial exact solver when applied to the proposed model. The new model is also compared with a simple extension of the model described by Özgüven et al. (Appl Math Modell 34:1539–1548, 2010), using instances from the literature and instances inspired by real data from the printing industry.     

Short cycle structures for graphs on surfaces and an open problem of Mohar and Thomassen

In this paper we investigate cycle base structures of a (weighted) graph and show that much information of short cycles is contained in an MCB (i.e., minimum cycle base). After setting up a Hall type theorem for base-transformation, we give a sufficient and necessary condition for a cycle base to be an MCB. Furthermore, we show that the structure of MCB in a (weighted) graph is unique. The property is also true for those having a longest length (although much work has been down in evaluating MCB, little is known for those having a longest length). We use those methods to find out some unknown properties for short cycles sharing particular properties in (unweighted) graphs. As applications, we determine the structures of short cycles in an embedded graph and show that there exist polynomially bounded algorithms in finding a shortest contractible cycle and a shortest two-sided cycle provided such cycles exist. Those answer an open problem of B. Mohar and C. Thomassen.     

CYCLE SPACES OF GRAPHS ON THE SPHERE AND THE PROJECTIVE PLANE

Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in pratical uses such as electric circuit theory and structure analysis, etc. In this paper graph embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph on the sphere and the projective plane and it is shown that short cycles do generate the cycle spaces in the case of ““““small face-embeddings““““. As applications the authors find the exact formulae for the minimum lengthes of cycle bases of some types of graphs and present several known results. Infinite examples shows that the conditions in their main results are best possible and there are many 3-connected planar graphs whose minimum cycle bases can not be determined by the planar formulae but may be located by re-embedding them into the projective plane.     

General properties of some families of graphs defined by systems of equations

In this paper we present a simple method for constructing infinite families of graphs defined by a class of systems of equations over commutative rings. We show that the graphs in all such families possess some general properties including regularity and biregularity, existence of special vertex colorings, and existence of covering maps—hence, embedded spectra—between every two members of the same family. Another general property, recently discovered, is that nearly every graph constructed in this manner edge‐decomposes either the complete, or complete bipartite, graph which it spans. In many instances, specializations of these constructions have proved useful in various graph theory problems, but especially in many extremal problems. A short survey of the related results is included. We also show that the edge‐decomposition property allows one to improve existing lower bounds for some multicolor Ramsey numbers. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 65–86, 2001