Search

We consider the weighted completion time minimization problem for capacitated parallel machines, which is a fundamental problem in modern cloud computing environments. In our setting, the processed jobs may be of varying duration, require different resources, and be of unequal importance (weight). Each server (machine) can process multiple concurrent jobs up to its capacity. We study heuristic approaches with provable approximation guarantees and offer an algorithm that prioritizes the jobs with the smallest volume-by-weight ratio. We bound the algorithm's approximation ratio using a decreasing function of the ratio between the highest resource demand of any job and the server's capacity. Thereafter, we create a hybrid, constant approximation algorithm for two or more machines. We also develop a constant approximation algorithm for the case of a single machine. Via a numerical study and a mixed-integer linear program of the problem, we demonstrate the performance of the suggested algorithm with respect to the optimal solutions and alternative scheduling methods. We show that the suggested scheduling method can be applied to both offline and online problems that may arise in real-world settings. This research is the first, to the best of our knowledge, to propose a polynomial-time algorithm with a constant approximation ratio for minimizing the weighted sum of job completion times for capacitated parallel machines. [ABSTRACT FROM AUTHOR]

We investigate the seemingly untouched yet the most general parallel identical k-stage flow-shops scheduling, in which we are given an arbitrary number of indistinguishable k-stage flow-shops and a set of jobs each to be processed on one of the flow-shops, and the goal is to schedule these jobs to the flow-shops so as to minimize the makespan. Here the number k of stages is a fixed constant, but the number of flow-shops is part of the input. This scheduling problem is strongly NP-hard. To the best of our knowledge all previously presented approximation algorithms are for the special case where k = 2 , including a 17/6-approximation in 2017, a (2 + ϵ) -approximation in 2018, and the most recent polynomial-time approximation scheme in 2020; they all take advantage of the number of stages being two. We deal with an arbitrary constant k ≥ 3 , where the k-stage flow-shop scheduling is already strongly NP-hard. To define a configuration that summarizes the key information about the job assignments in a feasible schedule, we present novel concepts of big job type, big job assignment pair type, and flow-shop type. We show that the total number of distinct configurations is a polynomial in the input number of flow-shops. We then present how to compute a schedule for each configuration that assigns all the big jobs, followed by how to allocate all the small jobs into the schedule at a cost only a fraction of the makespan. These together lead to a polynomial-time approximation scheme for the problem. [ABSTRACT FROM AUTHOR]

This paper considers several two-machine open shop problems with two agents. Each agent has an independent set of nonpreemptive jobs, and the objective is to find either a schedule minimizing a linear combination of the makespans of both agents, a schedule minimizing the makespan of one agent with the makespan of the other agent not exceeding a threshold, or all Pareto-optimal schedules with respect to the makespans of both agents. We present a number of results for the problems above, including a polynomial algorithm and a pseudo-polynomial algorithm for special cases, non-approximability, two approximation algorithms, and a fully polynomial-time approximation scheme. Finally, we run numerical experiments to show the effectiveness of the pseudo-polynomial algorithm and the approximation algorithms. [ABSTRACT FROM AUTHOR]

This paper introduces the d-distanceb-matching problem, in which we are given a bipartite graph G = (S , T ; E) with S = { s 1 , ⋯ , s n } , a weight function on the edges, an integer d ∈ Z + and a degree bound function b : S ∪ T → Z + . The goal is to find a maximum-weight subset M ⊆ E of the edges satisfying the following two conditions: (1) the degree of each node v ∈ S ∪ T is at most b(v) in M, (2) if s i t , s j t ∈ M , then | i - j | ≥ d . In the cyclic version of the problem, the nodes in S are considered to be in cyclic order. We get back the (cyclic)d-distance matching problem when b (s) = 1 for s ∈ S and b (t) = ∞ for t ∈ T . We prove that the d-distance matching problem is APX-hard, even in the unweighted case. We show that 2 - 1 d is a tight upper bound on the integrality gap of the natural integer programming model for the cyclic d-distance b-matching problem provided that (2 d - 1) divides the size of S. For the non-cyclic case, the integrality gap is shown to be at most (2 - 2 d) . The proofs give approximation algorithms with guarantees matching these bounds, and also improve the best known algorithms for the (cyclic) d-distance matching problem. In a related problem, our goal is to find a permutation of S maximizing the weight of the optimal d-distance b-matching. This problem can be solved in polynomial time for the (cyclic) d-distance matching problem — even though the (cyclic) d-distance matching problem itself is NP-hard and also hard to approximate arbitrarily. For (cyclic) d-distance b-matchings, however, we prove that finding the best permutation is NP-hard, even if b ≡ 2 or d = 2 , and we give e-approximation algorithms. [ABSTRACT FROM AUTHOR]

In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation algorithms for several variants of this problem that are known to be N P -hard, while also proving N P -hardness for two variants whose complexity was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective approximation in the coupled task setting. [ABSTRACT FROM AUTHOR]

The single facility location problem in multiple regions with different norms (SMDN) generalizes the well-known Weber Problem. The SMDN consists of finding the optimum location of a single facility in the plane which is partitioned into multiple regions where the distance to travel in each region is measured or approximated with different norms. In this study, we specifically focus on the SMDN considering three regions with either rectilinear or Euclidean norms. We first introduce some analytical properties of this problem. Then, we devise a specially tailored branch-and-bound algorithm, i.e. a Big Square Small Square algorithm (BSSS), and two heuristics, named as Discrete Approximation algorithm (DA) and Modified Weiszfeld procedure (MW). The performance of the proposed approaches are tested using both standard test instances from the literature and randomly generated instances. According to our extensive computational experiments, the BSSS stands out to be a suitable exact solution approach in terms of both accuracy and efficiency when commercial mixed integer nonlinear solvers are not applicable. Besides, we also observe that the DA yields quite accurate solutions at the expense of high computation times while the MW arises to be the most efficient method with the least accuracy. [ABSTRACT FROM AUTHOR]

The Unsplittable Flow on a Path (UFP) problem has garnered considerable attention as a challenging combinatorial optimization problem with notable practical implications. Steered by its pivotal applications in power engineering, the present work formulates a novel generalization of UFP, wherein demands and capacities in the input instance are monotone step functions over the set of edges. As an initial step towards tackling this generalization, we draw on and extend ideas from prior research to devise a quasi-polynomial time approximation scheme under the premise that the demands and capacities lie in a quasi-polynomial range. Second, retaining the same assumption, an efficient logarithmic approximation is introduced for the single-source variant of the problem. Finally, we round up the contributions by designing a (kind of) black-box reduction that, under some mild conditions, allows to translate LP-based approximation algorithms for the studied problem into their counterparts for the Alternating Current Optimal Power Flow problem—a fundamental workflow in operation and control of power systems. [ABSTRACT FROM AUTHOR]

Multiobjective optimization approaches have allowed the improvement of technical features in industrial processes, focusing on more accurate approaches for solving complex engineering problems and support decision-making. This paper proposes a hybrid approach to optimize the 3D printing technology parameters, integrating the design of experiments and multiobjective optimization methods, as an alternative to classical parametrization design used in machining processes. Alongside the approach, a multiobjective differential evolution with uniform spherical pruning (usp-MODE) algorithm is proposed to serve as an optimization tool. The parametrization design problem considered in this research has the following three objectives: to minimize both surface roughness and dimensional accuracy while maximizing the mechanical resistance of the prototype. A benchmark with non-dominated sorting genetic algorithm II (NSGA-II) and with the classical sp-MODE is used to evaluate the performance of the proposed algorithm. With the increasing complexity of engineering problems and advances in 3D printing technology, this study demonstrates the applicability of the proposed hybrid approach, finding optimal combinations for the machining process among conflicting objectives regardless of the number of decision variables and goals involved. To measure the performance and to compare the results of metaheuristics used in this study, three Pareto comparison metrics have been utilized to evaluate both the convergence and diversity of the obtained Pareto approximations for each algorithm: hyper-volume (H), g-Indicator (G), and inverted generational distance. To all of them, ups-MODE outperformed, with significant figures, the results reached by NSGA-II and sp-MODE algorithms. [ABSTRACT FROM AUTHOR]

Consider an arc-capacitated network N through which an integer-valued flow must be sent from several source nodes to a sink node. Each feasible flow defines a corresponding multigraph with the same vertices as N and an edge for each arc of N , where the edge multiplicity is the flow in the respective arc. The maximum flow degree of a feasible flow is the maximum sum of the flow entering and leaving a node of N , i.e. the maximum degree of the corresponding multigraph. The minimum maximum flow degree problem (MMFDP) consists in determining on N a feasible flow such that its maximum flow degree is minimum. We present a polynomial time algorithm for this problem. We use its optimum value to derive an improved upper bound for the flow coloring problem (FCP), which consists in finding a feasible flow whose corresponding multigraph has the minimum chromatic index. Based on this procedure, we design an approximation algorithm for the FCP that improves the best known approximation factor. [ABSTRACT FROM AUTHOR]

We present two new algorithms for convex Mixed Integer Nonlinear Programming (MINLP), both based on the well known Extended Cutting Plane (ECP) algorithm proposed by Weterlund and Petersson. Our first algorithm, Refined Extended Cutting Plane (RECP), incorporates additional cuts to the MILP relaxation of the original problem, obtained by solving linear relaxations of NLP problems considered in the Outer Approximation algorithm. Our second algorithm, Linear Programming based Branch-and-Bound (LP-BB), applies the strategy of generating cuts that is used in RECP, to the linear approximation scheme used by the LP/NLP based Branch-and-Bound algorithm. Our computational results show that RECP and LP-BB are highly competitive with the most popular MINLP algorithms from the literature, while keeping the nice and desirable characteristic of ECP, of being a first-order method. [ABSTRACT FROM AUTHOR]

Interaction effect across complementary products plays an important role in characterizing the optimal inventory policy. The inventory levels of complementary products are interrelated due to interaction between demand streams. In this paper, we consider a periodic review base-stock policy in the presence of two complementary products with interrelated demands and joint replenishment. Demands are modeled by a Poisson process and any unmet demand is lost. Demands can be in sets of one unit of each or jointly. If an arrival demand requests two products jointly and one of the products is not in stock, then the whole demand is lost. We aim to investigate how this interrelated demand phenomenon influences the optimal base-stock levels and the period length of a periodic review policy. We utilize the renewal reward theorem to derive the explicit expression of the expected profit rate in the system. The goal is to determine the optimal period length and the base-stock levels such that the expected profit rate is maximized. Enumeration and approximation algorithms are employed to find the optimal and near-optimal solutions, respectively. The approximation algorithm is based on a scenario with independent demand processes which results in an explicit expression for the long-run profit per time unit and leads to analytical solutions for optimal policies. Our numerical results reveal that the solutions obtained by the approximation algorithm are close to optimal solutions. Numerical experiences show that the maximum profit in the system is achieved if the proportion of customers with jointly demand increases. Moreover, the interaction effect between demand processes has a significant impact on the control policy performance when the units lost sales and unit holding costs are high, and the demand rare is low. [ABSTRACT FROM AUTHOR]

This paper introduces the d-distance matching problem, in which we are given a bipartite graph G = (S , T ; E) with S = { s 1 , ⋯ , s n } , a weight function on the edges and an integer d ∈ Z + . The goal is to find a maximum-weight subset M ⊆ E of the edges satisfying the following two conditions: (i) the degree of every node of S is at most one in M, (ii) if s i t , s j t ∈ M , then | j - i | ≥ d . This question arises naturally, for example, in various scheduling problems. We show that the problem is NP-complete in general and admits a simple 3-approximation. We give an FPT algorithm parameterized by d and also show that the case when the size of T is constant can be solved in polynomial time. From an approximability point of view, we show that the integrality gap of the natural integer programming model is at most 2 - 1 2 d - 1 , and give an LP-based approximation algorithm for the weighted case with the same guarantee. A combinatorial (2 - 1 d) -approximation algorithm is also presented. Several greedy approaches are considered, and a local search algorithm is described that achieves an approximation ratio of 3 / 2 + ϵ for any constant ϵ > 0 in the unweighted case. The novel approaches used in the analysis of the integrality gap and the approximation ratio of locally optimal solutions might be of independent combinatorial interest. [ABSTRACT FROM AUTHOR]

We consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some time-dependent cost, the time-of-use tariff, which must be paid in addition to the standard scheduling cost. We focus on preemptive single-machine scheduling and two classical scheduling cost functions, the sum of (weighted) completion times and the maximum completion time, that is, the makespan. While these problems are easy to solve in the classical scheduling setting, they are considerably more complex when time-of-use tariffs must be considered. We contribute optimal polynomial-time algorithms and best possible approximation algorithms. For the problem of minimizing the total (weighted) completion time on a single machine, we present a polynomial-time algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time slots to be used for preemptively scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. For the more general problem, in which jobs may have individual weights, we develop a polynomial-time approximation scheme (PTAS) based on a dual scheduling approach introduced for scheduling on a machine of varying speed. As the weighted problem is strongly NP-hard, our PTAS is the best possible approximation we can hope for. For preemptive scheduling to minimize the makespan, we show that there is a comparably simple optimal algorithm with polynomial running time. This is true even in a certain generalized model with unrelated machines. [ABSTRACT FROM AUTHOR]

We investigate two min–max k-postmen cover problems. The first is the Min–Max Rural Postmen Cover Problem (RPC), in which we are given an undirected weighted graph and the objective is to find at most k closed walks, covering a required subset of edges, to minimize the weight of the maximum weight closed walk. The other is called the Min–Max Chinese Postmen Cover Problem, in which the goal is to find at most k closed walks, covering all the edges of an undirected weighted graph, to minimize the weight of the maximum weight closed walk. For both problems we propose the first constant-factor approximation algorithms with ratios 10 and 4, respectively. For the Metric RPC, a special case of the RPC with the edge weights obeying the triangle inequality, we obtain an improved 6-approximation algorithm by a matching-based approach. For the Min–Max Rural Postmen Walk Cover Problem (RPWC), a variant of the RPC with the closed walks replaced by (open) walks, we give a 5-approximation algorithm that improves on the previous 7-approximation algorithm. If k is fixed, we devise improved approximation algorithms for the Metric RPC and the RPWC with ratios 4 + ϵ and 3 + ϵ , respectively, where ϵ > 0 is an arbitrary small constant. The latter result improves on the existing (4 + ϵ) -approximation algorithm. Moreover, we develop a (3 + ϵ) -approximation algorithm for a special case of the RPC with fixed k, improving on the previous (4 + ϵ) -approximation algorithm. [ABSTRACT FROM AUTHOR]

In Packet Scheduling with Adversarial Jamming, packets of arbitrary sizes arrive over time to be transmitted over a channel in which instantaneous jamming errors occur at times chosen by the adversary and not known to the algorithm. The transmission taking place at the time of jamming is corrupt, and the algorithm learns this fact immediately. An online algorithm maximizes the total size of packets it successfully transmits and the goal is to develop an algorithm with the lowest possible asymptotic competitive ratio, where the additive constant may depend on packet sizes. Our main contribution is a universal algorithm that works for any speedup and packet sizes and, unlike previous algorithms for the problem, it does not need to know these parameters in advance. We show that this algorithm guarantees 1-competitiveness with speedup 4, making it the first known algorithm to maintain 1-competitiveness with a moderate speedup in the general setting of arbitrary packet sizes. We also prove a lower bound of ϕ + 1 ≈ 2.618 on the speedup of any 1-competitive deterministic algorithm, showing that our algorithm is close to the optimum. Additionally, we formulate a general framework for analyzing our algorithm locally and use it to show upper bounds on its competitive ratio for speedups in [1, 4) and for several special cases, recovering some previously known results, each of which had a dedicated proof. In particular, our algorithm is 3-competitive without speedup, matching both the (worst-case) performance of the algorithm by Jurdzinski et al. (Proceedings of the 12th workshop on approximation and online algorithms (WAOA), LNCS 8952, pp 193–206, 2015. http://doi.org/10.1007/978-3-319-18263-6%5f17) and the lower bound by Anta et al. (J Sched 19(2):135–152, 2016. http://doi.org/10.1007/s10951-015-0451-z). [ABSTRACT FROM AUTHOR]

The transportation problem is a fundamental problem in operations research, where items need to be transported from supply nodes (each with a given supply) to demand nodes (each with a given demand) in the cheapest possible way. Here, we are interested in a generalization of the transportation problem where, each supply node has a (possibly empty) set of conflicting pairs of demand nodes, and each demand node a (possibly empty) set of conflicting pairs of supply nodes. Each supply node may only send supply to at most one demand node of each conflicting pair. Likewise, each demand node may only receive supply from at most one supply node of each conflicting pair. We call the resulting problem the transportation problem with conflicts (TPC). We show that the complexity of TPC depends upon the structure of the so-called conflict graph that follows from the conflicting pairs. More concrete, we show that for many graph-classes the corresponding TPC remains NP-hard, and for some special cases we derive constant factor approximation algorithms. [ABSTRACT FROM AUTHOR]

In this paper we consider a coordinated in-house production scheduling and outsourcing model, where a manufacturer might outsource part of the production to a subcontractor so as to achieve a tight production due date. The manufacturer pays a specific outsourcing cost for each job that is outsourced. To encourage the manufacturer to outsource more jobs, the subcontractor provides a specific discount scheme on the total outsourcing cost. Previous studies focus on the balance between in-house production performance and the total outsourcing cost. Our model is the first to investigate the impact on the manufacturer's decision-making under different discount schemes on the total outsourcing cost. Four distinct discount schemes on the total outsourcing cost are studied. We either show the intractability of those problems, or provide efficient exact or approximation algorithms. [ABSTRACT FROM AUTHOR]

The problem of computing the vertices of the convex hull of a given input set S = { v i ∈ R m : i = 1 , ⋯ , n } is a classic and fundamental problem, studied in the context of computational geometry, linear and convex programming, machine learning and more. In this article we present All Vertex Triangle Algorithm (AVTA), a robust and efficient algorithm for this problem. On the one hand, without any assumptions, AVTA computes approximation to the subset S ¯ of all K vertices of the convex hull of S so that the convex hull of the approximate subset of vertices is as close to conv(S) as desired. On the other hand, assuming a known lower bound γ on the ratio Γ ∗ / R , where Γ ∗ the minimum of the distances from each vertex to the convex hull of the remaining vertices and R the diameter of S, AVTA can recover all of S ¯ . Furthermore, assuming that instead of S the input is an ε -perturbation of S, S ¯ ε , where ‖ v i - v i ε ‖ ≤ ε R , AVTA can compute approximation to c o n v (S ¯ ε) , to any prescribed accuracy. Also, given a lower bound to the ratio Σ ∗ / R , where Σ ∗ is the minimum of the distances from each vertex to the convex hull of the remaining point of S, AVTA can recover all of S ¯ ε . We show Σ ∗ ≥ ρ ∗ Γ ∗ / R , where ρ ∗ is the minimum distance between distinct pair of points in S and prove the following main results: Given any t ∈ (0 , 1) , AVTA computes a subset S ¯ t of S ¯ of cardinality K (t) in O (n K (t) (m + t - 2)) operations so that for any p ∈ c o n v (S) its Euclidean distance to c o n v (S ¯ t) is at most tR. Given γ ≤ γ ∗ = Γ ∗ / R , AVTA computes S ¯ in O (n K (m + γ - 2)) operations. If K is known, the complexity of AVTA is O (n K (m + γ ∗ - 2) log (γ ∗ - 1)) . Assuming instead of S, its ε -perturbation, S ε is given, we prove Given any t ∈ (0 , 1) , AVTA computes a subset S ¯ ε t ⊂ S ¯ ε of cardinality K ε (t) in O (n K ε (t) (m + t - 2)) operations so that for any p ∈ c o n v (S) its distance to c o n v (S ¯ ε t) is at most (t + ε) R . Given σ ∈ [ 4 ε , σ ∗ = Γ ∗ / R ] , AVTA computes S ¯ ε in O (n K ε (m + σ - 2)) operations, where K ≤ K ε ≤ n . If γ ≤ γ ∗ = Γ ∗ / R is known satisfying 4 ε ≤ γ ρ ∗ / R , AVTA computes S ¯ ε in O (n K ε (m + (γ ρ ∗) - 2)) operations. Given σ ∈ [ 4 ε , σ ∗ ] , if K is known, AVTA computes S ¯ ε in O (n K (m + σ ∗ - 2) log (σ ∗ - 1)) operations. We also consider the application of AVTA in the recovery of vertices through the projection of S or S ε under a Johnson–Lindenstrauss randomized linear projection L : R m → R m ′ . Denoting U = L (S) and U ε = L (S ε) , by relating the robustness parameters of conv(U) and c o n v (U ε) to those of conv(S) and c o n v (S ε) , we derive analogous complexity bounds for probabilistic computation of the vertex set of conv(U) or those of c o n v (U ε) , or an approximation to them. Finally, we apply AVTA to design new practical algorithms for two popular machine learning problems: topic modeling and non-negative matrix factorization. For topic models, our new algorithm leads to significantly better reconstruction of the topic-word matrix than state of the art approaches of Arora et al. (International conference on machine learning, pp 280–288, 2013) and Bansal et al. (Advances in neural information processing systems, pp 1997–2005, 2014). Additionally, we provide a robust analysis of AVTA and empirically demonstrate that it can handle larger amounts of noise than existing methods. For non-negative matrix factorization we show that AVTA is competitive with existing methods that are specialized for this task in Arora et al. (Proceedings of the forty-fourth annual ACM symposium on theory of computing, ACM, pp 145–162, 2012a). We also contrast AVTA with Blum et al. (Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, Society for Industrial and Applied Mathematics, pp 548–557, 2016) Greedy Clustering coreset algorithm for computing approximation to the set of vertices and argue that not only there are regimes where AVTA outperforms that algorithm but it can also be used as a pre-processing step to their algorithm. Thus the two algorithms in fact complement each other. [ABSTRACT FROM AUTHOR]

This paper proposes a scheduling model for the washing step of medical device sterilization. After use in a surgery, medical devices pass through several steps where the washing is usually a bottleneck. We study the cases of external and internal sterilization services to minimize two objectives: makespan and flow time of washing operations. First, we study internal sterilization services considering jobs can have different or unit sizes. For these two cases, we provide a mixed integer linear model and a dynamic programming model, and integrate these methods in an ϵ -constraint model. For the case of external services, first we develop a simultaneous (2, 2) approximation algorithm and then derive an algorithmic scheme to generate a partial 2-approximation of the Pareto set. Several numerical experiments are conducted to demonstrate the strength of proposed solution methods. [ABSTRACT FROM AUTHOR]

In the current study, an unrelated parallel machine scheduling problem with release dates is considered, which is to obtain a job assignment with minimal sum of weighted completion times. Although this problem is NP-hard in the strong sense, which renders the optimality seeking a formidable task within polynomial time, a 4-approximation algorithm based on the constant worst-case bound is devised and proved in comparison with the existing 16/3-approximation (Hall et al. in Math Oper Res 22(3):513–544, 1997). In the newly proposed algorithm, the original scheduling problem is divided into several sub-problems based on release dates. For each sub-problem, a convex quadratic integer programming model is constructed in accordance with the specific problem structure. Then a semi-definite programming approach is implemented to produce a lower bound via the semi-definite relaxation of each sub-problem. Furthermore, by considering the binary constraint, a branch and bound based method and a local search strategy are applied separately to locate the optimal solution of each sub-problem. Then the solution of the original scheduling problem is derived by integrating the outcomes of the sub-problems via the proposed approximation algorithm. In the numerical analysis, it is discovered that the proposed methods could always obtain a scheduling result within 1 % of the optimal solution. And an asymptotic trend could be observed where the quality of solutions improves even further as the scale of the scheduling problem increases. [ABSTRACT FROM AUTHOR]

We consider a multiobjective scheduling problem, with the aim of minimizing the maximum lateness and the makespan on two identical machines. In this problem, we are given a set J of n jobs to be scheduled on two identical machines. Each job j ∈ J has a processing time p j and a delivery time q j . The machines are available at time t = 0 and each of them can process at most one job at a given time. This paper proposes an exact algorithm (based on a dynamic programming) to generate the complete Pareto Frontier in a pseudo-polynomial time. Then, we present a polynomial time approximation scheme (PTAS) to generate an approximate Pareto Frontier. In this scheme, we use a simplification technique based on the merging of jobs. Furthermore, we present two fully polynomial time approximation scheme (FPTAS) to generate an approximate Pareto Frontier, the first one is based on the conversion of the dynamic programming, the second one is applied to the simplified instances given by the PTAS. The proposed FPTAS algorithms are strongly polynomial. Finally, some numerical experiments are provided in order to compare the four proposed approaches. [ABSTRACT FROM AUTHOR]

The challenges in evacuation planning have been vital because of rapid disasters and limited road capacity. Contraflow strategy is very effective and widely accepted approach for the optimal use of available road network in evacuation management that increases the outward road capacities from the disastrous areas towards the safe destinations. Modeling the contraflow problem mathematically, there are available a number of efficient solution algorithms in literature, however, in general, the problem is still computationally quite hard. In this paper, we introduce the partial contraflow approach, in the abstract network setting with flow on paths and adapt the previous contraflow solution techniques to save unused capacities of road segments (elements) which can be used for supplying other facilities during emergency. We present efficient algorithms to solve the maximum static, lex-maximum static, maximum dynamic and earliest arrival partial contraflow problems on an abstract network. We also present an approximation algorithm to solve 2-value approximate earliest arrival transshipment partial contraflow problem for multi-terminal abstract network. Implementation of the partial contraflow reconfiguration leads to a significant improvement in increasing the flow values, decreasing the evacuation time, and utilizing the unused capacities of paths for humanitarian logistics and vehicle movements. [ABSTRACT FROM AUTHOR]

We study packing problems with matroid structures, which includes the strength of a graph of Cunningham and scheduling problems. If M is a matroid over a set of elements S with independent set I, and m=|S|, we suppose that we are given an oracle function that takes an independent set A∈I and an element e∈S and determines if A∪{e} is independent in time I(m). Also, given that the elements of A are represented in an ordered way A={A1,⋯,Ak}, we denote the time to check if A∪{e}∉I and if so, to find the minimum i∈{0,⋯,k} such that {A1,⋯,Ai}∪{e}∉I by I∗(m). Then, we describe a new FPTAS that computes for any ε>0 and for any matroid M of rank r over a set S of m elements, in memory space O(m), the packing Λ(M) within 1+ε in time O(mI∗(m)log(m)log(m/r)/ε2), and the covering Υ(M) in time O(rΥ(M)I(m)log(m)log(m/r)/ε2). This method outperforms in time complexity by a factor of Ω(m/r) the FPTAS of Plotkin, Shmoys, and Tardos, and a factor of Ω(m) the FPTAS of Garg and Konemann. On top of the value of the packing and the covering, our algorithm exhibits a combinatorial object that proves the approximation. The applications of this result include graph partitioning, minimum cuts, VLSI computing, job scheduling and others. [ABSTRACT FROM AUTHOR]

We outline a relatively new research agenda aiming at building a new approximation paradigm by matching two distinct domains, the polynomial approximation and the exact solution ofNP-hard problems by algorithms with guaranteed and non-trivial upper complexity bounds. We show how one can design approximation algorithms achieving ratios that are “forbidden” in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower than that of an exact computation. [ABSTRACT FROM AUTHOR]

This new writing impacts the other following results, now stated appropriately: Theorem 1 Let HT ht be an FCP instance. Then HT ht Graph If HT ht , we can replace HT ht by HT ht in the above upper bound. [Extracted from the article]

Deadlock prevention techniques are essential in the design of robust distributed systems. However, despite the large number of different algorithmic approaches to detect and solve deadlock situations, yet there remains quite a wide field to be explored in the study of deadlock-related combinatorial properties. In this work we consider a simplified AND-OR model, where the processes and their communication are given as a graph G. Each vertex of G is labelled AND or OR, in such a way that an AND-vertex (resp., OR-vertex) depends on the computation of all (resp., at least one) of its neighbors. We define a graph convexity based on this model, such that a set S⊆V(G) is convex if and only if every AND-vertex (resp., OR-vertex) v∈V(G)\S has at least one (resp., all) of its neighbors in V(G)\S. We relate some classical convexity parameters to blocking sets that cause deadlock. In particular, we show that those parameters in a graph represent the sizes of minimum or maximum blocking sets, and also the computation time until system stability is reached. Finally, a study on the complexity of combinatorial problems related to such graph convexity is provided. [ABSTRACT FROM AUTHOR]

The paper defines new distances between univariate probability distributions, based on the concept of the CVaR norm. We consider the problem of approximation of a discrete distribution by some other discrete distribution. The approximating distribution has a smaller number of atoms than the original one. Such problems, for instance, must be solved for generation of scenarios in stochastic programming. The quality of the approximation is evaluated with new distances suggested in this paper. We use CVaR constraints to assure that the approximating distribution has tail characteristics similar to the target distribution. The numerical algorithm is based on two main steps: (i) optimal placement of positions of atoms of the approximating distribution with fixed probabilities; (ii) optimization of probabilities with fixed positions of atoms. These two steps are iterated to find both optimal atom positions and probabilities. Numerical experiments show high efficiency of the proposed algorithms, solved with convex and linear programming. [ABSTRACT FROM AUTHOR]

In this article we introduce a new multiobjective optimizer based on a recently proposed metaheuristic algorithm named Variable Mesh Optimization (VMO). Our proposal (multiobjective VMO, MOVMO) combines typical concepts from the multiobjective optimization arena such as Pareto dominance, density estimation and external archive storage. MOVMO also features a crossover operator between local and global optima as well as dynamic population replacement. We evaluated MOVMO using a suite of four well-known benchmark function families, and against seven state-of-the-art optimizers: NSGA-II, SPEA2, MOCell, AbYSS, SMPSO, MOEA/D and MOEA/D.DRA. The statistically validated results across the additive epsilon, spread and hypervolume quality indicators confirm that MOVMO is indeed a competitive and effective method for multiobjective optimization of numerical spaces. [ABSTRACT FROM AUTHOR]

In this paper, we give an overview of the main results obtained on the complexity of scheduling under the non-idling constraint, i.e, when the jobs assigned to each machine must be processed with no intermediate delay. That constraint is met in practice when the cost of intermediate idle time is too high due to the idle time itself and/or the machine restarting. The non idling constraint is a strong constraint that often needs a new solving approach and most results about classical scheduling problems do not easily extend to the non-idling variant of the problem. In this survey, we mainly consider the non-idling variants of the basic scheduling problems. So, we first present basic properties, complexity results and some algorithms concerning the one-machine non-idling scheduling problem. Then we consider the m-machine non idling scheduling problem. We show that a few basic problems may be solved by rather easy extensions of the algorithm solving their classical counterpart. However, the complexity status of the non idling version of quite easy polynomial basic problems remains an open question. We finally consider a more constrained version of non-idling, called the 'homogeneously non idling' constraint, where for any subset of machines, the union of their busy intervals must make an interval and we present the structural property that leads to a polynomial algorithm for unit time jobs and a weak precedence. We conclude by giving some research directions that seem quite interesting to study both for theoretical and practical issues. [ABSTRACT FROM AUTHOR]

This paper reviews the problems of Boolean non-linear programming related to the half-product problem. All problems under consideration have a similar quadratic non-separable objective function. For these problems, we focus on the development of fully polynomial-time approximation schemes, especially of those with strongly polynomial time, and on their applications to various scheduling problems. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling jobs on a single machine to minimize the total electricity cost of processing these jobs under time-of-use electricity tariffs. For the uniform-speed case, in which all jobs have arbitrary power demands and must be processed at a single uniform speed, we prove that the non-preemptive version of this problem is inapproximable within a constant factor unless $$\text {P} = \text {NP}$$ . On the other hand, when all the jobs have the same workload and the electricity prices follow a so-called pyramidal structure, we show that this problem can be solved in polynomial time. For the speed-scalable case, in which jobs can be processed at an arbitrary speed with a trade-off between speed and power demand, we show that the non-preemptive version of the problem is strongly NP-hard. We also present different approximation algorithms for this case, and test the computational performance of these approximation algorithms on randomly generated instances. In addition, for both the uniform-speed and speed-scaling cases, we show how to compute optimal schedules for the preemptive version of the problem in polynomial time. [ABSTRACT FROM AUTHOR]

We present fast approximation algorithms for the problem of dividing a given convex geographic region into smaller sub-regions so as to distribute the workloads of a set of vehicles. Our objective is to partition the region in such a fashion as to ensure that vehicles are capable of communicating with one another under limited communication radii. We consider variations of this problem in which sub-regions are constrained to have equal area or be convex, and as a side consequence, our approach yields a factor 1.99 approximation algorithm for the continuous k-centers problem on a convex polygon. [ABSTRACT FROM AUTHOR]

For many popular stochastic approximation algorithms, such as the stochastic gradient method and the simultaneous perturbation stochastic approximation method, the practical gain sequence selection is different from the optimal selection, that is theoretically derived from asymptotical performance. We provide formal justification for the reasons why we choose such gain sequence in practice. [ABSTRACT FROM AUTHOR]

Given $$S= \{v_1, \dots , v_n\} \subset {\mathbb {R}}^m$$ and $$p \in {\mathbb {R}}^m$$ , testing if $$p \in conv(S)$$ , the convex hull of $$S$$ , is a fundamental problem in computational geometry and linear programming. First, we prove a Euclidean distance duality, distinct from classical separation theorems such as Farkas Lemma: $$p$$ lies in $$conv(S)$$ if and only if for each $$p' \in conv(S)$$ there exists a pivot, $$v_j \in S$$ satisfying $$d(p',v_j) \ge d(p,v_j)$$ . Equivalently, $$p \not \in conv(S)$$ if and only if there exists a witness, $$p' \in conv(S)$$ whose Voronoi cell relative to $$p$$ contains $$S$$ . A witness separates $$p$$ from $$conv(S)$$ and approximate $$d(p, conv(S))$$ to within a factor of two. Next, we describe the Triangle Algorithm: given $$\epsilon \in (0,1)$$ , an iterate, $$p' \in conv(S)$$ , and $$v \in S$$ , if $$d(p, p') < \epsilon d(p,v)$$ , it stops. Otherwise, if there exists a pivot $$v_j$$ , it replace $$v$$ with $$v_j$$ and $$p'$$ with the projection of $$p$$ onto the line $$p'v_j$$ . Repeating this process, the algorithm terminates in $$O(mn \min \{ \epsilon ^{-2}, c^{-1}\ln \epsilon ^{-1} \})$$ arithmetic operations, where $$c$$ is the visibility factor, a constant satisfying $$c \ge \epsilon ^2$$ and $$\sin (\angle pp'v_j) \le 1/\sqrt{1+c}$$ , over all iterates $$p'$$ . In particular, the geometry of the input data may result in efficient complexities such as $$O(mn \root t \of {\epsilon ^{-2}} \ln \epsilon ^{-1})$$ , $$t$$ a natural number, or even $$O(mn \ln \epsilon ^{-1})$$ . Additionally, (i) we prove a strict distance duality and a related minimax theorem, resulting in more effective pivots; (ii) describe $$O(mn \ln \epsilon ^{-1})$$ -time algorithms that may compute a witness or a good approximate solution; (iii) prove generalized distance duality and describe a corresponding generalized Triangle Algorithm; (iv) prove a sensitivity theorem to analyze the complexity of solving LP feasibility via the Triangle Algorithm. The Triangle Algorithm is practical and competitive with the simplex method, sparse greedy approximation and first-order methods. Finally, we discuss future work on applications and generalizations. [ABSTRACT FROM AUTHOR]

Given a graph G( N, A) with a cost (or benefit) and a delay on each arc, the constrained routing problem (CRP) aims to find a minimum-cost or a maximum-benefit path from a given source to a given destination node, subject to an end-to-end delay constraint. The problem (with a single constraint) is NP-hard, and has been studied by many researchers who found fully polynomial approximation schemes (FPAS) for this problem. The current paper focuses on a generalized CRP version, CRP with hop-wise constraints (CRPH). In the generalized version, instead of one constraint there are up to n−1 special-type constraints, where n is the number of nodes. An FPAS based on interval partitioning is proposed for both the minimization and the maximization versions of CRPH. For G( N, A) with n nodes and m arcs, the complexity of the algorithm is O( mn/ ε). [ABSTRACT FROM AUTHOR]

An uncertain version of the task scheduling problem on unrelated machines to minimize the total flow time is considered. It is assumed that processing times are not known a priori, but they belong to intervals of known bounds. The absolute regret is applied to evaluate the uncertainty, and minmax regret task scheduling problem is solved. A simple 2-approximate middle intervals time efficient algorithm is proposed. More time consuming but better in terms of the quality of solutions scatter search based heuristic algorithm is described. Its usefulness is justified via computational experiments. [ABSTRACT FROM AUTHOR]

In this paper we propose an approximation for the Traveling Tournament Problem which is the problem of designing a schedule for a sports league consisting of a set of teams T such that the total traveling costs of the teams are minimized. It is not allowed for any team to have more than k home-games or k away-games in a row. We propose an algorithm which approximates the optimal solution by a factor of 2+2 k/ n+ k/( n−1)+3/ n+3/(2⋅ k) which is not more than 5.875 for any choice of k≥4 and n≥6. This is the first constant factor approximation for k>3. We furthermore show that this algorithm is also applicable to real-world problems as it produces solutions of high quality in a very short amount of time. It was able to find solutions for a number of well known benchmark instances which are even better than the previously known ones. [ABSTRACT FROM AUTHOR]

A 2.75-approximation algorithm is proposed for the unconstrained traveling tournament problem, which is a variant of the traveling tournament problem. For the unconstrained traveling tournament problem, this is the first proposal of an approximation algorithm with a constant approximation ratio. In addition, the proposed algorithm yields a solution that meets both the no-repeater and mirrored constraints. Computational experiments show that the algorithm generates solutions of good quality. [ABSTRACT FROM AUTHOR]

In this paper, a class of stochastic extended vertical linear complementarity problems is studied as an extension of the stochastic linear complementarity problem. The expected residual minimization (ERM) formulation of this stochastic extended vertical complementarity problem is proposed based on an NCP function. We study the corresponding properties of the ERM problem, such as existence of solutions, coercive property and differentiability. Finally, we propose a descent stochastic approximation method for solving this problem. A comprehensive convergence analysis is given. A number of test examples are constructed and the numerical results are presented. [ABSTRACT FROM AUTHOR]

This paper addresses a scheduling problem in a flexible supply chain, in which the jobs can be either processed in house, or outsourced to a third-party supplier. The goal is to minimize the sum of holding and delivery costs. This problem is proved to be strongly $\mathcal{NP}$-hard. Consider two special cases, in which the jobs have identical processing times. For the problem with limited outsourcing budgets, a $\mathcal{NP}$-hardness proof, a pseudo-polynomial algorithm and a fully polynomial time approximation scheme are presented. For the problem with unlimited outsourcing budgets, the problem is shown to be equivalent to the shortest path problem, and therefore it is in class $\mathcal{P}$. This shortest-path-problem solution approach is further shown to be applicable to a similar but more applicable problem, in which the number of deliveries is upper bounded. [ABSTRACT FROM AUTHOR]

In this paper, we consider the well-known resource-constrained project scheduling problem. We give some arguments that already a special case of this problem with a single type of resources is not approximable in polynomial time with an approximation ratio bounded by a constant. We prove that there exist instances for which the optimal makespan values for the non-preemptive and the preemptive problems have a ratio of O(log n), where n is the number of jobs. This means that there exist instances for which the lower bound of Mingozzi et al. has a bad relative error of O(log n), and the calculation of this bound is an NP-hard problem. In addition, we give a proof that there exists a type of instances for which known approximation algorithms with polynomial time complexity have an approximation ratio of at least equal to $O(\sqrt{n})$, and known lower bounds have a relative error of at least equal to O(log n). This type of instances corresponds to the single machine parallel-batch scheduling problem 1| p− batch, b=∞| C. [ABSTRACT FROM AUTHOR]

We consider general properties of isomorphic scheduling problems that constitute a new class of pairs of mutually related scheduling problems. Any such a pair is composed of a scheduling problem with fixed job processing times and its time-dependent counterpart with processing times that are proportional-linear functions of the job starting times. In order to introduce the class formally, first we formulate a generic scheduling problem with fixed job processing times and define isomorphic problems by a one-to-one transformation of instances of the generic problem into instances of time-dependent scheduling problems with proportional-linear job processing times. Next, we prove basic properties of isomorphic scheduling problems and show how to convert polynomial algorithms for scheduling problems with fixed job processing times into polynomial algorithms for proportional-linear counterparts of the original problems. Finally, we show how are related approximation algorithms for isomorphic problems. Applying the results, we establish new worst-case results for time-dependent parallel-machine scheduling problems and prove that many single- and dedicated-machine time-dependent scheduling problems with proportional-linear job processing times are polynomially solvable. [ABSTRACT FROM AUTHOR]

In this paper, we address the optimal batch sizing and just-in-time scheduling problem where upper and lower bounds on the size of the batches are imposed. The objective is to find a feasible schedule that minimizes the sum of the weighted earliness and tardiness penalties as well as the setup costs, which involves the cost of creating a new batch. We present some structural properties of the optimal schedules and describe solving algorithms for the single machine problem. [ABSTRACT FROM AUTHOR]

Demand-Adaptive Systems (DASs) display features of both traditional fixed-line bus services and purely on-demand systems such as dial-a-ride, that is, they offer demand-responsive services within the framework of traditional scheduled bus transportation. A DAS bus line serves a given set of compulsory stops according to a predefined schedule, which specifies the time windows associated with each stop, and thus provides the traditional use of a transit line without reservation. On the other hand, passengers may issue requests for transportation between two optional stops, inducing detours in the vehicle routes. The design of a DAS line is a complex planning process that requires to select the compulsory stops and to determine its master schedule in terms of the time windows associated with the compulsory stops. In this paper, we focus on determining the master schedule for a single DAS line. We propose a mathematical description and a solution method based on probabilistic approximations of several DAS line core characteristics. Results of numerical experiments are also given and analyzed. [ABSTRACT FROM AUTHOR]

This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose a new lower bound for the traveling tournament problem, and construct a randomized approximation algorithm yielding a feasible solution whose approximation ratio is less than 2+(9/4)/( n−1), where n is the number of teams. Additionally, we propose a deterministic approximation algorithm with the same approximation ratio using a derandomization technique. For the traveling tournament problem, the proposed algorithms are the first approximation algorithms with a constant approximation ratio, which is less than 2+3/4. [ABSTRACT FROM AUTHOR]

Development of applicable robustness results for stochastic programs with probabilistic constraints is a demanding task. In this paper we follow the relatively simple ideas of output analysis based on the contamination technique and focus on construction of computable global bounds for the optimal value function. Dependence of the set of feasible solutions on the probability distribution rules out the straightforward construction of these concavity-based global bounds for the perturbed optimal value function whereas local results can still be obtained. Therefore we explore approximations and reformulations of stochastic programs with probabilistic constraints by stochastic programs with suitably chosen recourse or penalty-type objectives and fixed constraints. Contamination bounds constructed for these substitute problems may be then implemented within the output analysis for the original probabilistic program. [ABSTRACT FROM AUTHOR]

Given a graph G=( V, E) and a weight function on the edges w: E→ℝ, we consider the polyhedron P( G, w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P( G, w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1-3):174-190, ), we show that, unless P= NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (Discrete Comput. Geom. 39(1-3):174-190, ) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lübbecke in Comput. Geom., Theory Appl. 11(2):103-109, ). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron in ℝ within a factor of 12/ n. [ABSTRACT FROM AUTHOR]

We are interested in the problem of scheduling orders for different product types in a facility with a number of machines in parallel. Each order asks for certain amounts of various different product types which can be produced concurrently. Each product type can be produced on a subset of the machines. Two extreme cases of machine environments are of interest. In the first case, each product type can be produced on one and only one machine which is dedicated to that product type. In the second case, all machines are identical and flexible; each product type can be produced by any one of the machines. Moreover, when a machine in this case switches over from one product type to another, no setup is required. Each order has a release date and a weight. Preemptions are not allowed. The objective is minimizing the total weighted completion time of the orders. Even when all orders are available at time 0, both types of machine environments have been shown to be NP-hard for any fixed number (≥2) of machines. This paper focuses on the design and analysis of approximation algorithms for these two machine environments. We also present empirical comparisons of the various algorithms. The conclusions from the empirical analyses provide insights into the trade-offs with regard to solution quality, speed, and memory space. [ABSTRACT FROM AUTHOR]

We consider the following scheduling setting: a set of n tasks have to be executed on a set of m identical machines. It is well known that shortest processing time (SPT) schedules are optimal for the problem of minimizing the total sum of completion times of the tasks. In this paper, we measure the quality of SPT schedules, from an approximation point of view, with respect to the following optimality criteria: sum of completion times per machine, global fairness, and individual fairness. [ABSTRACT FROM AUTHOR]

We consider scheduling problems in the master slave model, which was introduced by Sahni in 1996. The goal is to minimize the makespan and the total completion time. It has been shown that the problem of minimizing makespan is NP-hard. Sahni and Vairaktarakis developed some approximation algorithms to generate schedules whose makespan is at most constant times the optimal. In this paper, we show that the problem of minimizing total completion time is NP-hard in the strong sense. Then we develop algorithms to generate schedules whose total completion time and makespan are both bounded by some constants times their optimal values. [ABSTRACT FROM AUTHOR]