Search

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]

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]

The scaffold filling problem aims to set up the whole genomes by filling those missing genes into the scaffolds to optimize a similarity measure of genomes. A typical and frequently used measure for the similarity of two genomes is the number of common adjacencies. One-sided scaffold filling is given by a scaffold and a whole genome, and asks to fill the missing genes into that scaffold to result in such a genome that the number of common adjacencies between it and the given genome is maximized. Two-sided scaffold filling is given by two scaffolds, and asks to fill the missing genes into those two scaffolds respectively to result in such two genomes that the number of common adjacencies between them is maximized. One-sided scaffold filling can be approximated to $$\frac{5}{4}$$ by now. However, the algorithmic progress for two-sided scaffold filling seems rare. What we know for two-sided scaffold filling is a 2-approximation algorithm by now. In this paper, we propose a new algorithm for two-sided scaffold filling which can achieve a performance ratio of $$\frac{3}{2}$$ in $$O(N^3)$$ time, where $$N$$ is the number of genes in an output genome. An example can be given to show that the performance ratio $$\frac{3}{2}$$ for this algorithm is actually tight. [ABSTRACT FROM AUTHOR]

This paper presents a new method and algorithms for dividing modular numbers on the basis of the use of dividend and divisor values relative with respect to the full range of a residue number system. The proposed modular division algorithm uses elementary operations of register shift and addition, which makes the algorithm very simple and fastest to date. [ABSTRACT FROM AUTHOR]

The piecewise monotonic approximation problem makes the least changes to n univariate noisy data so that the piecewise linear interpolant to the new values is composed of at most k monotonic sections. The term "least changes" is defined in the sense of a global sum of strictly convex functions of changes. The main difficulty in this calculation is that the extrema of the interpolant have to be found automatically, but the number of all possible combinations of extrema can be O (n k - 1) , which makes not practicable to test each one separately. It is known that the case k = 1 is straightforward, and that the case k > 1 reduces to partitioning the data into at most k disjoint sets of adjacent data and solving a k = 1 problem for each set. Some ordering relations of the extrema are studied that establish three quite efficient algorithms by using a binary search method for partitioning the data. In the least squares case the total work is only O (n σ + k σ log 2 σ) computer operations when k ≥ 3 and is only O (n) when k = 1 or 2, where σ - 2 is the number of sign changes in the sequence of the first differences of the data. Fortran software has been written for this case and the numerical results indicate superior performance to existing algorithms. Some examples with real data illustrate the method. Many applications of the method arise from bioinformatics, energy, geophysics, medical imaging, and peak finding in spectroscopy, for instance. [ABSTRACT FROM AUTHOR]

We study the problem of finding a spanning tree with maximum number of leaves. We present a simple, linear time 2-approximation algorithm for this problem, improving on the previous best known algorithm for the problem, which has approximation ratio 3. [ABSTRACT FROM AUTHOR]