Search

A dominating set of a graph is a subset of vertices such that every vertex not in the subset has at least one neighbor within the subset. The corresponding optimization problem is known to be NP-hard. It is proved to be beneficial to separate the solution process in two stages. First, one can apply a fast greedy algorithm to obtain an initial dominating set and then use an iterative procedure to purify (reduce) the size of this dominating set. In this work, we develop the purification stage and propose new purification algorithms. The purification procedures that we present here outperform, in practice, the earlier known purification procedure. We have tested our algorithms for over 1300 benchmark problem instances. Compared to the estimations due to known upper bounds, the obtained solutions are about seven times better. Remarkably, for the 500 benchmark instances for which the optimum is known, the optimal solutions are obtained for 46.33% of the tested instances, whereas the average error for the remaining instances is about 1.01. [ABSTRACT FROM AUTHOR]

We consider a basic preemptive scheduling problem where n non-simultaneously released jobs are to be processed by m unrelated parallel machines so as to minimize maximum job completion time. An optimal LP-solution has been used to construct an optimal preemptive schedule for simultaneously released jobs in time O(n³). We propose fast O(m) time algorithm that finds an optimal schedule in case the above LP-solution possesses "small enough" number of non-zero elements. We propose another linear program for non-simultaneously released jobs and show how an optimal schedule can be constructed also in time O(m) from the optimal solution to that linear program. Based on another stronger linear program formulation, we extend the earlier known schedule construction procedure for non-simultaneously released jobs. The procedure is important, in particular, because there may exist no optimal schedule that agrees with an optimal LP-solution. An optimal LPsolution imposes a number of preemptions, and additional preemptions may occur during the schedule construction process, a job might be forced to be split on the same machine. We show that if no job split is allowed, even a restricted version of the problem on three unrelated machines is NP-hard. As a result, we obtain that, given an optimal LP-solution, it is NP-hard to find an optimal schedule that agrees with that LP-solution. As another side result, we obtain that it is NP-hard to find an optimal schedule with at most m - 1 preemptions. [ABSTRACT FROM AUTHOR]

The Traveling Salesman Problem (TSP) aims to find the shortest tour for a salesman who starts and ends in the same city and visits the remaining n − 1 cities exactly once. There are a number of common generalizations of the problem including the Multiple Traveling Salesman Problem (MTSP), where instead of one salesman, there are k salesmen and the same amount of individual tours are to be constructed. We consider the Euclidean version of the problem where the distances between the cities are calculated in two-dimensional Euclidean space. Both general the TSP and its Euclidean version are strongly NP-hard. Hence, approximation algorithms with a good practical behavior are of primary interest. We describe a general method for the solution of the Euclidean versions of the TSP (including MTSP) that yields approximation algorithms with a favorable practical behavior for large real-life instances. Our method creates special types of convex hulls, which serve as a basis for the constructions of our initial and intermediate partial solutions. Here, we overview three algorithms; one of them is for the bounded version of the MTSP. The proposed novel algorithm for the Euclidean TSP provides close-to-optimal solutions for some real-life instances. [ABSTRACT FROM AUTHOR]

We study a single-machine scheduling problem with two allowable job release and delivery times. This special case of a strongly NP-hard single-machine scheduling problem with an arbitrary number of job release and delivery times and with the objective to minimize the maximum job completion time remains NP-hard. Nevertheless, it is more transparent and accessible than the general version. Hence, it permitted us to establish some nice properties that yielded simple and efficient solution methods. On the one hand, the restricted setting is useful by its own right since it fits some real-life applications. On the other hand, the presented case study is helpful in the solution of a more general setting with a constant number of job release and delivery times. In particular, the optimality conditions and the heuristics methods that we propose here for the restricted setting might be generalized to the extended setting. The established optimality criteria are explicit conditions under which the restricted problem can be solved optimally in time O (n log n) . The extensive computational study showed that at least one of these conditions is satisfied for practically all the randomly generated 50 million problem instances while applying our heuristics to these instances. We report a favorable practical performance of our polynomial-time subroutine that invokes our five heuristics and verifies the proposed optimality conditions consecutively. These conditions were verified for the solutions delivered by the five heuristics individually and in a combined fashion as four pairs of heuristics and as all the five heuristics together. Fifty million problem instances were randomly generated using uniform distribution for each of these ten combinations. For the 50 million instances generated for the last (overall) combination, the schedule created by at least one of the heuristics has satisfied at least one of our optimality conditions (so all these problem instances were solved optimally). We also addressed the (theoretical) possibility that none of our conditions is satisfied, and showed how a known dynamic programming algorithm for SUBSET SUM problem can be used for the solution of the scheduling problem in pseudo-polynomial time. For a considerable part of the tested instances, one of the five scheduling heuristics has solved optimally also SUBSET SUM problem. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of scheduling a set of jobs having only two possible processing times on a set of unrelated parallel machines. This problem is a generalisation of the much more common problem of scheduling equal-length jobs on identical machines. Such a situation may occur in the production of two different types of products. First, we show that an earlier open problem of scheduling jobs with two possible processing times and on unrelated machines with the objective to minimise the makespan can be polynomially solved by an algorithm consisting of two phases. A slight modification of this algorithm yields an absolute worst-case error of for the case of two arbitrary processing times and ,. Thus, for practical problems of a large size with two types of products and two possible processing times, the approximation algorithm generates schedules very close to an optimal one. [ABSTRACT FROM AUTHOR]

The multiprocessor job-shop scheduling problem (JSP) is a generalisation of the classical job-shop problem, in which each machine is replaced by a group of parallel machines. We consider the most general case when the parallel machines are unrelated, where the number of feasible solutions grows drastically even compared with the classical JSP, which itself is one of the most difficult strongly NP-hard problems. We exploit the practical behaviour of a method of the preliminary reduction of the solution space of this general model from an earlier paper by Vakhania and Shchepin (this model works independently and before the application of lower bounds). According to the probabilistic model proposed by Vakhania and Shchepin, this results in an exponential reduction of the whole set of feasible solutions with a probability close to 1. In this paper, this theoretical estimation is certified by intensive computational experiments. Despite an exponential increase in the number of feasible solutions in the instances generated from job-shop instances, we were able to solve many of them optimally just with our reduction algorithm, where the results of our computational experiments have surpassed even our theoretical estimations. The preliminary reduction of the solution space of our multiprocessor job-shop problem is of essential importance due to the fact that the elaboration of efficient lower bounds for this problem is complicated. We address the difficulties connected with this kind of development and propose a few possible lower bounds. [ABSTRACT FROM AUTHOR]

Some special cases of single-machine problems is considered. In these cases there are many optimal solutions. It is given the formulas of quantity of optimal solutions and calculated the probability of the event that an arbitrary schedule is optimal; the sufficient conditions to increase the value of this probability is given and the corresponding optimal full completion time is calculated. [ABSTRACT FROM AUTHOR]

The computational complexity of an algorithm is traditionally measured for the worst and the average case.The worst-case estimation guarantees a certain worst-case behavior of a given algorithm, although it might be rough, since in “most instances” the algorithm may have a significantly better performance.The probabilistic average-case analysis claims to derive an average performance of an algorithm, say, for an “average instance” of the problem in question.That instance may be far away from the average of the problem instances arising in a given real-life application, and so the average case analysis would also provide a non-realistic estimation.We suggest that, in general, a wider use of probabilistic models for a more accurate estimation of the algorithm efficiency could be possible.For instance, the quality of the solutions delivered by an approximation algorithm may also be estimated in the “average” probabilistic case.Such an approach would deal with the estimation of the quality of the solutions delivered by the algorithm for the most common (for a given application) problem instances.As we illustrate, the probabilistic modeling can also be used to derive an accurate time complexity performance measure, distinct from the traditional probabilistic average-case time complexity measure.Such an approach could, in particular, be useful when the traditional average-case estimation is still rough or is not possible at all. [ABSTRACT FROM AUTHOR]

A basic 2-approximation heuristic was suggested by Jackson in early 50s last century for scheduling jobs with release times and due dates to minimize the maximum job lateness. The theoretical worst-case bound of 2 helps a little in practice, when the solution quality is important. The quality of the solution delivered by Jackson’s heuristic is closely related to the maximum job processing time pmax   that occurs in a given problem instance and with the resultant interference with other jobs that such a long job may cause. We use the relationship of pmax with the optimal objective value to obtain more accurate approximation ratio, which may drastically outperform the earlier known worst-case ratio of 2. This is proved, in practice, by our computational experiments. [ABSTRACT FROM AUTHOR]

We study inherent structural properties of a strongly NP-hard problem of scheduling $$n$$ jobs with release times and due dates on a single machine to minimize the number of late jobs. Our study leads to two polynomial-time algorithms. The first algorithm with the time complexity $$O(n^3\log n)$$ solves the problem if during its execution no job with some special property occurs. The second algorithm solves the version of the problem when all jobs have the same length. The time complexity of the latter algorithm is $$O(n^2\log n)$$, which is an improvement over the earlier known algorithm with the time complexity $$O(n^5)$$. [ABSTRACT FROM AUTHOR]

In this paper we study multiprocessor and open shop scheduling problems from several points of view. We explore a tight dependence of the polynomial solvability/intractability on the number of allowed preemptions. For an exhaustive interrelation, we address the geometry of problems by means of a novel graphical representation. We use the so-called preemption and machine-dependency graphs for preemptive multiprocessor and shop scheduling problems, respectively. In a natural manner, we call a scheduling problem acyclic if the corresponding graph is acyclic. There is a substantial interrelation between the structure of these graphs and the complexity of the problems. Acyclic scheduling problems are quite restrictive; at the same time, many of them still remain NP-hard. We believe that an exhaustive study of acyclic scheduling problems can lead to a better understanding and give a better insight of general scheduling problems. We show that not only acyclic but also a special non-acyclic version of periodic job-shop scheduling can be solved in polynomial (linear) time. In that version, the corresponding machine dependency graph is allowed to have a special type of the so-called parti-colored cycles. We show that trivial extensions of this problem become NP-hard. Then we suggest a linear-time algorithm for the acyclic open-shop problem in which at most m−2 preemptions are allowed, where m is the number of machines. This result is also tight, as we show that if we allow one less preemption, then this strongly restricted version of the classical open-shop scheduling problem becomes NP-hard. In general, we show that very simple acyclic shop scheduling problems are NP-hard. As an example, any flow-shop problem with a single job with three operations and the rest of the jobs with a single non-zero length operation is NP-hard. We suggest linear-time approximation algorithm with the worst-case performance of $\|\mathcal{M}\|+2\|\mathcal{J}\|$ ( $\|\mathcal{M}\|+\|\mathcal{J}\|$ , respectively) for acyclic job-shop (open-shop, respectively), where $\|\mathcal{J}\|$ (|ℳ|, respectively) is the maximal job length (machine load, respectively). We show that no algorithm for scheduling acyclic job-shop can guarantee a better worst-case performance than $\|\mathcal{M}\|+\|\mathcal{J}\|$ . We consider two special cases of the acyclic job-shop with the so-called short jobs and short operations (restricting the maximal job and operation length) and solve them optimally in linear time. We show that scheduling m identical processors with at most m−2 preemptions is NP-hard, whereas a venerable early linear-time algorithm by McNaughton yields m−1 preemptions. Another multiprocessor scheduling problem we consider is that of scheduling m unrelated processors with an additional restriction that the processing time of any job on any machine is no more than the optimal schedule makespan C . We show that the (2 m−3)-preemptive version of this problem is polynomially solvable, whereas the (2 m−4)-preemptive version becomes NP-hard. For general unrelated processors, we guarantee near-optimal (2 m−3)-preemptive schedules. The makespan of such a schedule is no more than either the corresponding non-preemptive schedule makespan or max { C , p max }, where C is the optimal (preemptive) schedule makespan and p max is the maximal job processing time. [ABSTRACT FROM AUTHOR]

We study the problem of scheduling jobs with release times and tails on a single machine with the objective to minimize the makespan. This problem is strongly NP-hard, however it is known to be polynomially solvable if all jobs have equal processing time P. We generalize this result and suggest an O( n2 log nlog P) algorithm for the case when the processing times of some jobs are restricted to either P or 2 P. [ABSTRACT FROM AUTHOR]

The problem of scheduling n jobs of equal duration p with release and delivery times on m identical processors with the objective to minimize the maximal job completion time is considered. An algorithm is proposed that has the time complexity O ( mn log n ) if the maximal job delivery time q max is bounded by some constant. This is better than the earlier known best bound of O ( mn 2 log( np / m )) for the version of the problem with non-restricted q max . The algorithm has the time complexity O(q_{\max }^2 n\log n\max \{ m,\;q_{\max } \} ) without the restriction on q max . As the presented computational experiments show, practical behavior of the algorithm remains good without restriction on q max , i.e., for arbitrarily long delivery times, the running time of the algorithm, in practice, does not depend on q max . [ABSTRACT FROM AUTHOR]

The worst-case behavior of the “critical path” (CP) algorithm for multiprocessor scheduling with an out-tree task dependency structure is studied. The out-tree is not known in advance and the tasks are released on-line over time (each task is released at the completion time of its direct predecessor task in the out-tree). For each task, the processing time and the remainder (the length of the longest chain of the future tasks headed by this task) become known at its release time. The tight worst-case ratio and absolute error are derived for this strongly clairvoyant on-line model. For out-trees with a specific simple structure, essentially better worst-case ratio and absolute error are derived. Our bounds are given in terms of tmax, the length of the longest chain in the out-tree, and it is shown that the worst-case ratio asymptotically approaches 2 for large tmax when the number of processors $$m=\widetilde {\tau}(\widetilde{\tau}+1)/2-2$$ , where $$\widetilde{\tau}$$ is an integer close to $$\sqrt {t_{\max}}$$ . A non-clairvoyant on-line version (without knowledge of task processing time and remainder at the release time of the task) is also considered and is shown that the worst-case behavior of width-first search is better or the same as that of the depth-first search. [ABSTRACT FROM AUTHOR]

In recent years, Multimetric Indices (MMIs) have received a lot of attention thanks to their ability to develop integrative evaluations of water quality, particularly in lagoons. In this article, we propose a new MMI for determining the water quality in lagoons. The proposed index is composed of biotic and abiotic indicators, in particular macroinvertebrates, macrophytes and morphological indicators. The proposed index is based on a geometric representation of a phenomenon associated with an ecological system, the ecosystem elements are mapped as vertices of a network and the relationship between them is represented by the corresponding edges. We classify the status of water bodies, from very low to very high using the ecological quality ratio. We compare our index with different different indices that measure water quality, such as General Biotic Index ( J P (G) ), Macrophyte Index for River (MIR) and Shannon diversity index (H') and validate our index with Pearson's correlation coefficient. A strong correlation with the J P (G) and M I R indices ( R 2 = 0.8605 and R 2 = 0.7661 , respectively) is obtained. Although the proposed index is composed of other indices, the independence of the proposed index with respect to its component indices is proven and the structure of the geometric model associated to the proposed network is studied. A close relationship between the measure called medium articulation and the geometric model associated with the proposed index is highlighted, which allows to determine the missing relationships in the network using structural analysis. The proposed index presents a more comprehensive measure than most indices currently used and has the advantage in the scalability, since other existing indicators can be integrated into our model. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling n jobs with identical processing times and given release as well as delivery times on m uniform machines. The goal is to minimize the makespan, i.e., the maximum full completion time of any job. This problem is well-known to have an open complexity status even if the number of jobs is fixed. We present a polynomial-time algorithm for the problem which is based on the earlier introduced algorithmic framework blesscmore ("branch less and cut more"). We extend the analysis of the so-called behavior alternatives developed earlier for the version of the problem with identical parallel machines and show how the earlier used technique for identical machines can be extended to the uniform machine environment if a special condition on the job parameters is imposed. The time complexity of the proposed algorithm is O (γ m 2 n log n) , where γ can be either n or the maximum job delivery time q max . This complexity can even be reduced further by using a smaller number κ < n in the estimation describing the number of jobs of particular types. However, this number κ becomes only known when the algorithm has terminated. [ABSTRACT FROM AUTHOR]

A nonempty subset D ⊂ V of vertices of a graph G = (V , E) is a dominating set if every vertex of this graph is adjacent to at least one vertex from this set except the vertices which belong to this set itself. D ⊆ V is a total k-dominating set if there are at least k vertices in set D adjacent to every vertex v ∈ V , and it is a global total k-dominating set if D is a total k-dominating set of both G and G ¯ . The global total k-domination number of G, denoted by γ k t g (G) , is the minimum cardinality of a global total k-dominating set of G, GTkD-set. Here we derive upper and lower bounds of γ k t g (G) , and develop a method that generates a GTkD-set from a GT (k − 1) D-set for the successively increasing values of k. Based on this method, we establish a relationship between γ (k − 1) t g (G) and γ k t g (G) , which, in turn, provides another upper bound on γ k t g (G) . [ABSTRACT FROM AUTHOR]

A basic supply chain scheduling problem in which the orders released over time are to be delivered into the batches with unlimited capacity is considered. The delivery of each batch has a fixed cost D, whereas any order delivered after its release time yields an additional delay cost equal to the waiting time of that order in the system. The objective is to minimize the total delivery cost of the batches plus the total delay cost of the orders. A new algorithmic framework is proposed based on which fast algorithms for the solution of this problem are built. The framework can be extended to more general supply chain scheduling models and is based on a theoretical study of some useful properties of the offline version of the problem. An online scenario is considered as well, when at each assignment (order release) time the information on the next order released within the following T time units is known but no information on the orders that might be released after that time is known. For the online setting, it is shown that there is no benefit in waiting for more than D time units for incoming orders, i.e., potentially beneficial values for T are 0 < T < D , and three linear-time algorithms are proposed, which are optimal for both the offline and the online cases when T ≥ D . For the case 0 < T < D an important real-life scenario is studied. It addresses a typical situation when the same number of orders are released at each order release time and these times are evenly distributed within the scheduling horizon. An optimal algorithm which runs much faster than earlier known algorithms is proposed. [ABSTRACT FROM AUTHOR]

We give a complement note on the proof of the NP-hardness of preemptive acyclic open-shop problem presented earlier by the authors in Ann. Oper. Res. 159:183-213, . [ABSTRACT FROM AUTHOR]

We propose an approximation algorithm for scheduling jobs with release and delivery times on a single machine with the objective to minimize the makespan. The algorithm is based on an implicit enumeration of the set of complete solutions in a search tree. By analyzing specific structural properties of the solutions created in each branch of the solution tree, a certain approximation factor of each solution from that branch is calculated. Our algorithm guarantees approximation factor 1 + 1 / κ for a generated solution if there are κ jobs with a specified property in that solution (typically, the longer the length of the path from the root to the node representing that solution in the solution tree, the larger the κ value). We have carried out an extensive computational study to verify the practical performance of our algorithm and the effectiveness of the approximation factor provided by us. While our problem instances are generated randomly, we have discarded a considerable number of the instances, ones which were already solved optimally by the earlier known dominance rules. For the vast majority of the tested problem instances, within a short running time of our algorithm parameter κ becomes sufficiently large so that the approximation factor which the algorithm guarantees becomes better than that provided by the earlier known approximation algorithms. [ABSTRACT FROM AUTHOR]

The Traveling Salesman Problem (TSP) aims at finding the shortest trip for a salesman, who has to visit each of the locations from a given set exactly once, starting and ending at the same location. Here, we consider the Euclidean version of the problem, in which the locations are points in the two-dimensional Euclidean space and the distances are correspondingly Euclidean distances. We propose simple, fast, and easily implementable heuristics that work well, in practice, for large real-life problem instances. The algorithm works on three phases, the constructive, the insertion, and the improvement phases. The first two phases run in time O (n 2) and the number of repetitions in the improvement phase, in practice, is bounded by a small constant. We have tested the practical behavior of our heuristics on the available benchmark problem instances. The approximation provided by our algorithm for the tested benchmark problem instances did not beat best known results. At the same time, comparing the CPU time used by our algorithm with that of the earlier known ones, in about 92% of the cases our algorithm has required less computational time. Our algorithm is also memory efficient: for the largest tested problem instance with 744,710 cities, it has used about 50 MiB, whereas the average memory usage for the remained 217 instances was 1.6 MiB. [ABSTRACT FROM AUTHOR]

Scheduling jobs with release and due dates on a single machine is a classical strongly NP-hard combination optimization problem. It has not only immediate real-life applications but also it is effectively used for the solution of more complex multiprocessor and shop scheduling problems. Here, we propose a general method that can be applied to the scheduling problems with job release times and due-dates. Based on this method, we carry out a detailed study of the single-machine scheduling problem, disclosing its useful structural properties. These properties give us more insight into the complex nature of the problem and its bottleneck feature that makes it intractable. This method also helps us to expose explicit conditions when the problem can be solved in polynomial time. In particular, we establish the complexity status of the special case of the problem in which job processing times are mutually divisible by constructing a polynomial-time algorithm that solves this setting. Apparently, this setting is a maximal polynomially solvable special case of the single-machine scheduling problem with non-arbitrary job processing times. [ABSTRACT FROM AUTHOR]

Given any function f : Z + → R + , let us define the f-index I f (G) = ∑ u ∈ V (G) f (d u) and the f-polynomial P f (G , x) = ∑ u ∈ V (G) x 1 / f (d u) − 1 , for x > 0 . In addition, we define P f (G , 0) = lim x → 0 + P f (G , x) . We use the f-polynomial of a large family of topological indices in order to study mathematical relations of the inverse degree, the generalized first Zagreb, and the sum lordeg indices, among others. In this paper, using this f-polynomial, we obtain several properties of these indices of some classical graph operations that include corona product and join, line, and Mycielskian, among others. [ABSTRACT FROM AUTHOR]

We study a scheduling problem in which jobs with release times and due dates are to be processed on a single machine. With the primary objective to minimize the maximum job lateness, the problem is strongly NP-hard. We describe a general algorithmic scheme to minimize the maximum job lateness, with the secondary objective to minimize the maximum job completion time. The problem of finding the Pareto-optimal set of feasible solutions with these two objective criteria is strongly NP-hard. We give the dominance properties and conditions when the Pareto-optimal set can be formed in polynomial time. These properties, together with our general framework, provide the theoretical background, so that the basic framework can be expanded to (exponential-time) implicit enumeration algorithms and polynomial-time approximation algorithms (generating the Pareto sub-optimal frontier with a fair balance between the two objectives). Some available in the literature experimental results confirm the practical efficiency of the proposed framework. [ABSTRACT FROM AUTHOR]

Motivated by the conjecture that an interaction between scheduling and pre-scheduling phases in production planning may give certain benefits, we conduct a detailed study of the optimality conditions and dominance relations for a strongly NP-hard single-machine scheduling model when jobs have release and due-dates and the objective is to minimize maximum job lateness. By exploring the inherent structure of the problem, we establish the optimality conditions when the problem can be efficiently solved. We come to an NP-hard special case of the problem with only two possible job release times, that as we show allows stricter dominance rules and optimality conditions verifiable in polynomial time. The established properties give a potential of a beneficial interaction between scheduling and pre-scheduling phases in production planning, and also provide basic theoretical background for the construction of efficient heuristic and implicit enumerative algorithms. [ABSTRACT FROM AUTHOR]