Search

Since the publication of the first scheduling paper in 1954, a huge number of works dealing with different types of single machine problems appeared. They addressed many heuristics and enumerative procedures, complexity results or structural properties of certain problems. Regarding surveys, often particular subjects like special objective functions are discussed, or more general scheduling problems were surveyed, where a substantial part is devoted to single machine problems. In this paper we present some results on polynomial algorithms, complexity and approximation issues, where the main focus is on results, which have been published during the last decades in papers, where at least one of the first two authors of this paper was involved. We hope that the reviewed results will stimulate further investigation in related research fields.

In the Bounded Multiple Traveling Salesman Problem (BMTSP), a tour for each salesman, that starts and ends at the depot and that respects the bounds on the number of cities that a feasible salesman tour should satisfy, is to be constructed. The objective is to minimize the total length of all tours. Already Euclidean traveling salesman problem is NP-hard. We propose a 3-Phase heuristic algorithm for the Euclidean BMTSP. We tested the algorithm for the 22 benchmark instances and 168 new problem instances that we created. We report 19 best known solutions for the 22 benchmark instances including the 12 largest ones. For the newly created instances, we compared the performance of our algorithm with that of an ILP-solver CPLEX, which was able to construct a feasible solution for 71% of the instances within the time limit of two hours imposed by us. For about 10% of the smallest new instances, CPLEX delivered slightly better solutions, where our algorithm took less than 180 seconds for the largest of these instances. For the remaining 61% of the instances solved by CPLEX, the solutions by our heuristic were, on average, about 21.5% better than those obtained by CPLEX.

A dominating set of a graph $G=(V,E)$ is a subset of vertices $S\subseteq V$ such that every vertex $v\in V\setminus S$ has at least one neighbor in set $S$. The corresponding optimization problem is known to be NP-hard. The best known polynomial time approximation algorithm for the problem separates the solution process in two stages applying first a fast greedy algorithm to obtain an initial dominating set, and then it uses an iterative procedure to reduce (purify) this dominating set. The purification stage turned out to be practically efficient. Here we further strengthen the purification stage presenting four new purification algorithms. All four purification procedures outperform the earlier purification procedure. The algorithms were tested for over 1300 benchmark problem instances. Compared to the known upper bounds, the obtained solutions were about 7 times better. Remarkably, for the 500 benchmark instances for which the optimum is known, the optimal solutions were obtained for 46.33\% of the tested instances, whereas the average error for the remaining instances was about 1.01.

A dominating set D in a graph G is a subset of its vertices such that every vertex of the graph which does not belong to set D is adjacent to at least one vertex from set D. A set of vertices of graph G is a global dominating set if it is a dominating set for both, graph G and its complement. The objective is to find a global dominating set with the minimum cardinality. The problem is known to be NP-hard. Neither exact nor approximation algorithm existed . We propose two exact solution methods, one of them being based on an integer linear program (ILP) formulation, three heuristic algorithms and a special purification procedure that further reduces the size of a global dominated set delivered by any of our heuristic algorithms. We show that the problem remains NP-hard for restricted types of graphs and specify some families of graphs for which the heuristics guarantee the optimality. The second exact algorithm turned out to be about twice faster than ILP for graphs with more than 230 vertices and up to 1080 vertices, which were the largest benchmark instances that were solved optimally. The heuristics were tested for the existing 2284 benchmark problem instances with up to 14000 vertices and delivered solutions for the largest instances in less than one minute. Remarkably, for about 52% of the 1000 instances with the obtained optimal solutions, at least one of the heuristics generated an optimal solution, where the average approximation error for the remaining instances was 1.07%.

In a simple connected graph $G=(V,E)$, a subset of vertices $S \subseteq V$ is a dominating set if any vertex $v \in V\setminus S$ is adjacent to some vertex $x$ from this subset. A number of real-life problems can be modeled using this problem which is known to be among the difficult NP-hard problems in its class. We formulate the problem as an integer liner program (ILP) and compare the performance with the two earlier existing exact state-of-the-art algorithms and exact implicit enumeration and heuristic algorithms that we propose here. Our exact algorithm was able to find optimal solutions much faster than ILP and the above two exact algorithms for middle-dense instances. For graphs with a considerable size, our heuristic algorithm was much faster than both, ILP and our exact algorithm. It found an optimal solution for more than half of the tested instances, whereas it improved the earlier known state-of-the-art solutions for almost all the tested benchmark instances. Among the instances where the optimum was not found, it gave an average approximation error of $1.18$.

In contrast to the fixed parameter analysis (FPA), in the variable parameter analysis (VPA) the value of the target problem parameter is not fixed, it rather depends on the structure of a given problem instance and tends to have a favorable asymptotic behavior when the size of the input increases. While applying the VPA to an intractable optimization problem with $n$ objects, the exponential-time dependence in enumeration of the feasible solution set is attributed solely to the variable parameter $\nu$, $\nu<

A {\em dominating set} of a graph $G=(V,E)$ is a subset of vertices $S\subseteq V$ such that every vertex $v\in V\setminus S$ has at least one neighbor in $S$. Finding a dominating set with the minimum cardinality in a connected graph $G=(V,E)$ is known to be NP-hard. A polynomial-time approximation algorithm for this problem, described here, works in two stages. At the first stage a dominant set is generated by a greedy algorithm, and at the second stage this dominating set is purified (reduced). The reduction is achieved by the analysis of the flowchart of the algorithm of the first stage and a special kind of clustering of the dominating set generated at the first stage. The clustering of the dominating set naturally leads to a special kind of a spanning forest of graph $G$, which serves as a basis for the second purification stage. We expose some types of graphs for which the algorithm of the first stage already delivers an optimal solution and derive sufficient conditions when the overall algorithm constructs an optimal solution. We give three alternative approximation ratios for the algorithm of the first stage, two of which are expressed in terms of solely invariant problem instance parameters, and we also give one additional approximation ratio for the overall two-stage algorithm. The greedy algorithm of the first stage turned out to be essentially the same as the earlier known state-of-the-art algorithms for the set cover and dominating set problem Chv\'atal \cite{chvatal} and Parekh \cite{parekh}. The second purification stage results in a significant reduction of the dominant set created at the first stage, in practice. The practical behavior of both stages was verified for randomly generated problem instances. The computational experiments emphasize the gap between a solution of Stage 1 and a solution of Stage 2.

We consider a basic problem of preemptive scheduling of $n$ non-simultaneously released jobs on a group of $m$ unrelated parallel machines so as to minimize maximum job completion time, the makespan. In the scheduling literature, the problem is commonly considered to be solvable in polynomial time by linear programming (LP) techniques proposed in Lawler and Labetoulle \cite{ll78}. The authors in \cite{ll78} give a LP formulation of the version with simultaneously released jobs and show how an optimal solution to this LP can be used to construct an optimal schedule to the latter problem. As the current study shows, for non-simultaneously released jobs, unlikely, there exist a linear program such that a schedule with the minimum makespan can be constructed based on an optimal LP solution. We also prove that, in case no splitting of the same job on a machine is allowed (i.e., job part assigned to a machine is to be processed without an interruption on that machine), the problem is NP-hard. As a side result, we obtain that, whenever job splitting is not allowed, given an optimal LP solution, it is NP-hard to find an optimal schedule with the minimum makespan that agrees with that LP solution. We also extend the schedule construction procedure based on an optimal LP solution from Lawler and Labetoulle \cite{ll78} for non-simultaneously released jobs. The extended procedure, among all feasible schedules that agree with any feasible (not necessarily optimal) LP solution, generates one with the minimum makespan. Such procedure is helpful, in particular, because, as we show, there may exist no optimal schedule that agrees with an optimal LP solution if jobs are non-simultaneously released.

The problem of scheduling non-simultaneously released jobs with due dates on a single machine with the objective to minimize the maximum job lateness is known to be strongly NP-hard. Here we consider an extended model in which the compression of the job processing times is allowed. The compression is accomplished at the cost of involving additional emerging resources, whose use, however, yields some cost. With a given upper limit $U$ on the total allowable cost, one wishes to minimize the maximum job lateness. It is clear that, by using the available resources, some jobs may complete earlier and the objective function value may respectively be decreased. As we show here, for minimizing the maximum job lateness, by shortening the processing time of some specially determined jobs, the objective value can be decreased. Although the generalized problem is harder than the generic non-compressible version, given a ``sufficient amount'' of additional resources, we can solve the problem optimally. We determine the compression rate for some specific jobs and develop an algorithm that obtains an optimal solution. Such an approach can be beneficial in practice since the manufacturer can be provided with an information about the required amount of additional resources in order to solve the problem optimally. In case the amount of the available additional resources is less than used in the above solution, i.e., it is not feasible, it is transformed to a tight minimal feasible solution., Comment: 20 pages

A Variable Parameter (VP) analysis aims to give precise time complexity expressions of algorithms with exponents appearing solely in terms of variable parameters. A variable parameter is the number of objects with specific properties. Here we describe two VP-algorithms, an implicit enumeration and a polynomial-time approximation scheme for a strongly $NP$-hard problem of scheduling $n$ independent jobs with release and due times on one machine to minimize the maximum job completion time $C_{\max}$. Our variable parameters are the amounts of some specially defined types of jobs. A partial solution without these jobs is constructed in a low degree polynomial time, and an exponential time procedure (in the number of variable parameters) is carried out to augment it to a complete optimal solution. In the alternative time complexity expressions, the exponential dependence is solely on the some job parameters. Applying the fixed parameter analysis to these estimations, a polynomial-time dependence is achieved. Both, the intuitive probabilistic estimations and our extensive experimental study support our conjecture that the total number of the variable parameters is far less than $n$ and its ratio to $n$ converges to 0 asymptotically.

We study the problem of computing a preemptive schedule of equal-length jobs with given release times, deadlines and weights. Our goal is to maximize the weighted throughput, which is the total weight of completed jobs. In Graham's notation this problem is described as (1 | r_j;p_j=p;pmtn | sum w_j U_j). We provide an O(n^4)-time algorithm for this problem, improving the previous bound of O(n^{10}) by Baptiste., Comment: gained one author and lost one degree in the complexity