Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints

In this paper we consider the problem of scheduling n$n$ preemptive jobs on m$m$ machines with identical speed under machine availability and eligibility constraints when minimizing maximum lateness (_Lmax$(L_{\max }$). The lateness of a job is defined to be its completion time minus its due date, and _Lmax$L_{\max }$ is the maximum value of lateness among all jobs. We assume that each machine is not continuously available at all time throughout the planning horizon and each job is only allowed to be processed on specific machines. Network flow technique is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time two-phase binary search algorithm to verify the feasibility of the problem and to solve the scheduling problem optimally if a feasible schedule exists. Finally, we show that the time complexity of the algorithm is O((n+(2n+2x))³log(UB-LB))$O((n+(2n+2x){)}^3\log (\text{<italic>UB</italic>}-\text{<italic>LB</italic>}))$. Most literature in parallel machine scheduling assume that all machines are continuously available for processing and all jobs can be processed at any available machine throughout the planning horizon. But both assumptions might not be true in some practical environment, such as machine preventive maintenance and machines that have different capabilities to process jobs. This type of scheduling problem is seldom studied in the literature. The purpose of this paper is to examine the scheduling problem with machines with identical speed under machine availability and eligibility constraints. The objective is to minimize maximum lateness. We formulate this scheduling problem into a series of maximum flow problems with different values of _Lmax$L_{\max }$. A polynomial time two-phase binary search algorithm is proposed to verify the feasibility of the problem and to determine the optimal _Lmax$L_{\max }$.     

A new heuristic recursive algorithm for the strip rectangular packing problem

A fast and new heuristic recursive algorithm to find a minimum height for two-dimensional strip rectangular packing problem is presented. This algorithm is mainly based on heuristic strategies and a recursive structure, and its average running time is T(n)=θ(n³)$T(n)=\theta (n^3)$. The computational results on a class of benchmark problems have shown that this algorithm not only finds shorter height than the known meta-heuristic ones, but also runs in shorter time. Especially for large test problems, it performs better.     

On mimicking networks representing minimum terminal cuts

Given a capacitated undirected graph G=(V,E)$G=(V,E)$ with a set of terminals K⊂V$K\subset V$, a mimicking network   is a smaller graph H=(_VH,_EH)$H=(V_H,E_H)$ which contains the set of terminals K   and for every bipartition [U,K−U]$[U,K-U]$ of the terminals, the cost of the minimum cut separating U   from K−U$K-U$ in G is exactly equal to the cost of the minimum cut separating U   from K−U$K-U$ in H.     

Hypothesis testing in rank-size rule regression

This note examines testing methods for Paretoness in the framework of rank-size rule regression. Rank-size rule regression describes a relationship found in the analysis of various topics such as city population, words in texts, scale of companies and so on. In terms of city population, it is basically an empirical rule that log?(_S(i))$\log ?(S_{(i)})$ is approximately a linear function of log?(i)$\log ?(i)$ where _S(i)$S_{(i)}$ is the number of population of i  th largest city in a country. This is closely related to the so-called Zipf’s law. It is known that this kind of empirical observation is found when the city population is a random variable following a Pareto distribution. Thus one may be willing to test if city size has a Pareto distribution or not. Rosen and Resnick [K.T. Rosen, M. Resnick, The size distribution of cities: an explanation of the Pareto law and primacy, Journal of Urban Economics 8 (1980), 165–186] and Soo [K.T. Soo, Zipf’s law for cities: a cross country investigation, Regional Science and Urban Economics (35) 2005, 239–263] regress log?(_S(i))$\log ?(S_{(i)})$ on log?(i)$\log ?(i)$ and log?²(i)${\log ?}^2(i)$ and test the null of Paretoness by standard t-test for the latter regressor. It is found that t-statistics take large values and the Paretoness is rejected in many countries. We study the statistical properties of the t-statistic and show that it explodes asymptotically, in fact, by simulation and thus the t-test does not provide a reasonable testing procedure. We propose an alternative test statistic which seems to be asymptotically normally distributed. We also propose a test with the null hypothesis that the city size distribution is Pareto with exponent unity, which is a modification of the F-test.     

On the partition dimension of a class of circulant graphs

For a vertex v   of a connected graph G(V,E)$G(V,E)$ and a subset S of V, the distance between a vertex v and S   is defined by d(v,S)=min{d(v,x):x∈S}$d(v,S)=\min \{d(v,x):x\in S\}$. For an ordered k  -partition π={_S1,_S2…_Sk}$\pi =\{S_1,S_2\dots S_k\}$ of V, the partition representation of v with respect to π is the k  -vector r(v|π)=(d(v,_S1),d(v,_S2)…d(v,_Sk))$r(v|\pi )=(d(v,S_1),d(v,S_2)\dots d(v,S_k))$. The k-partition π is a resolving partition if the k  -vectors r(v|π)$r(v|\pi )$, v∈V(G)$v\in V(G)$ are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. Salman et al. [1] in their paper which appeared in Acta Mathematica Sinica, English Series   proved that partition dimension of a class of circulant graph G(n,±{1,2})$G(n,\pm \{1,2\})$, for all even n?6$n?6$ is four. In this paper we prove that it is three.     

Asynchronous deterministic rendezvous in graphs

Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting, meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. If agents are initially situated at a distance D   in an infinite line, we show a rendezvous algorithm with cost O(D|_Lmin|²)$\mathrm{O}(D|L_{\min }{|}^2)$ when D   is known and O((D+|_Lmax|)³)$\mathrm{O}((D+\left|L_{\max }\right|{)}^3)$ if D   is unknown, where |_Lmin|$\left|L_{\min }\right|$ and |_Lmax|$\left|L_{\max }\right|$ are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size, but then we also give an optimal algorithm of cost O(n|_Lmin|)$\mathrm{O}(n|L_{\min }|)$, if the size n   of the ring is known, and of cost O(n|_Lmax|)$\mathrm{O}(n|L_{\max }|)$, if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O(D|_Lmin|)$\mathrm{O}(D|L_{\min }|)$ if the topology of the graph and the initial positions are known to agents.     

Scheduling parallel CNC machines with time/cost trade-off considerations

When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well-known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. We also know that scheduling decisions are quite sensitive to the processing times. Therefore, this paper considers minimizing total manufacturing cost (_F1)$(F_1)$ and total completion time (_F2)$(F_2)$ objectives simultaneously on identical parallel CNC turning machines. Since decreasing processing time of a job increases its manufacturing cost, we cannot minimize both objectives at the same time, so the problem is to generate non-dominated solutions. We consider the problem of minimizing _F1$F_1$ subject to a given _F2$F_2$ level and give an effective formulation for the problem. For this problem, we prove some optimality properties which facilitated designing an efficient heuristic algorithm to generate approximate non-dominated solutions. Computational results show that proposed algorithm performs almost equal with the GAMS/MINOS commercial solver although it spends much less computation time.     

Single-machine parallel-batching scheduling with family jobs to minimize weighted number of tardy jobs

We consider the problem of scheduling n jobs in batches on a single parallel-batching machine, where the jobs are partitioned into jobs families and the jobs in each family have the same due date. The objective is to minimize the weighted number of tardy jobs. We first devise an efficient pseudo-polynomial time and a fully polynomial time approximation scheme for the weighted problem. Then we present $O(n^2)$-time and $O(n\log n)$-time algorithms for the case where the jobs have the same weight and for the case where the jobs have the same processing time, respectively.     

A representation theorem for (q-)holonomic sequences

Chomsky and Schützenberger showed in 1963 that the sequence _dL(n)$d_L(n)$, which counts the number of words of a given length n in a regular language L, satisfies a linear recurrence relation with constant coefficients for n  , i.e., it is C-finite. It follows that every sequence s(n)$s(n)$ which satisfies a linear recurrence relation with constant coefficients can be represented as _dL1(n)−_dL2(n)$d_{L_1}(n)-d_{L_2}(n)$ for two regular languages. We view this as a representation theorem for C-finite sequences. Holonomic or P-recursive sequences are sequences which satisfy a linear recurrence relation with polynomial coefficients. q-Holonomic sequences are the q-analog of holonomic sequences. In this paper we prove representation theorems of holonomic and q-holonomic sequences based on position specific weights on words, and for holonomic sequences, without using weights, based on sparse regular languages.     

A memetic algorithm for the job-shop with time-lags

The job-shop with time-lags (JS|t)$(\text{<italic>JS</italic>}|t)$ is defined as a job-shop problem with minimal and maximal delays between starting times of operations. In this article, time-lags between successive operations of the same job (JS|_ti,si)$(\text{<italic>JS</italic>}|t_{i,s_i})$ are studied. This problem is a generalization of the job-shop problem (null minimal time-lags and infinite maximal time-lags) and the no-wait job-shop problem (null minimal and maximal time-lags). This article introduced a framework based on a disjunctive graph to modelize the problem and on a memetic algorithm for job sequence generation on machines.     

Compatibility of unrooted phylogenetic trees is FPT

A collection of _T1,_T2,…,_Tk$T_1,T_2,\dots ,T_k$ of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be compatible   if there exists a tree T$T$ such that each tree _Ti$T_i$ can be obtained from T$T$ by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around Ω(n^k)$\mathrm{\Omega }(n^k)$ time, n$n$ being the number of leaves. Here, we present an O(nf(k))$\mathrm{O}(\mathit{nf}(k))$ algorithm, proving that compatibility of unrooted phylogenetic trees is fixed parameter tractable   (FPT) with respect to the number k$k$ of trees.     

Graphs of interval count two with a given partition

We describe a polynomial time algorithm to decide for a given connected graph G and a given partition of its vertex set into two sets A and B  , whether it is possible to assign a closed interval I(u)$I(u)$ to each vertex u of G such that two distinct vertices u and v of G   are adjacent if and only if I(u)$I(u)$ and I(v)$I(v)$ intersect, all intervals assigned to vertices in A   have some length _LA$L_A$, and all intervals assigned to vertices in B   have some length _LB$L_B$ where _LA<_LB$L_A<L_B$. Our result is motivated by the interval count problem whose complexity status is open.     

Column Subset Selection Problem is UG-hard

We address two problems related to selecting an optimal subset of columns from a matrix. In one of these problems, we are given a matrix A∈R^m×n$A\in {\mathbb{R}}^{m\times n}$ and a positive integer k, and we want to select a sub-matrix C of k   columns to minimize _{‖A−ΠCA‖F}${\Vert A-{\Pi }_{C}A\Vert }_F$, where _ΠC=CC⁺${\Pi }_C=C{C}^{+}$ denotes the matrix of projection onto the space spanned by C  . In the other problem, we are given A∈R^m×n$A\in {\mathbb{R}}^{m\times n}$, positive integers c and r, and we want to select sub-matrices C and R of c columns and r rows of A  , respectively, to minimize _{‖A−CUR‖F}${\Vert A-CUR\Vert }_F$, where U∈R^c×r$U\in {\mathbb{R}}^{c\times r}$ is the pseudo-inverse of the intersection between C and R. Although there is a plethora of algorithmic results, the complexity of these problems has not been investigated thus far. We show that these two problems are NP-hard assuming UGC.     

An efficient algorithm for minimizing earliness,tardiness, and due-date costs for equal-sized jobs

We consider a single-machine scheduling problem with equal-sized jobs. The objective is to minimize the maximum weighted earliness–tardiness and due-date costs. We present an algorithm to solve this problem. Our algorithm makes use of bottleneck jobs and priority queues, and has a computational complexity of O(n⁴logn)$O(n^4\log n)$. This complexity is a significant improvement of the existing algorithm in the literature.     

Computing the pathwidth of directed graphs with small vertex cover

We give an algorithm that computes the pathwidth of a given directed graph D   in 3^τ(D)n^O(1)$3^{\tau (D)}{n}^{O(1)}$ time where n is the number of vertices of D   and τ(D)$\tau (D)$ is the number of vertices of a minimum vertex cover of the underlying undirected graph of D. This result extends that of [5] for undirected graphs to directed graphs. Moreover, our algorithm is based on a standard dynamic programming with a simple tree-pruning trick, which is extremely simple and easy to implement. An additional advantage of our algorithm is that a minimum vertex cover appears in the analysis but not in the algorithm itself, in contrast to the algorithm of [5] which needs to compute a minimum vertex cover.     

Real-time estimation scheme for the spot cross volatility of jump diffusion processes

Given a finite set of observed data {_Xtk(_ω0),_Ytk(_ω0)}$\{X_{t_k}({\omega }_0)\text{,}{Y}_{t_k}({\omega }_0)\}$ of just one sample path at n$n$ regularly spaced time of the processes _Xt$X_t$ and _Yt$Y_t$ satisfying d_Xt=_a0(t)dt+_a1(t)d_W1(t)+_a2(t)d_W2(t)+d_J1(t),d_Yt=_b0(t)dt+_b1(t)d_W1(t)+_b2(t)d_W2(t)+d_J2(t),t∈[0,T]$d{X}_t=a_0(t)dt+a_1(t)d{W}_1(t)+a_2(t)d{W}_2(t)+d{J}_1(t)\text{,}d{Y}_t=b_0(t)dt+b_1(t)d{W}_1(t)+b_2(t)d{W}_2(t)+d{J}_2(t)\text{,}t\in [0\text{,}T]$, where _J1,_J2$J_1\text{,}{J}_2$ are jump process, we are to investigate a numerical scheme for the estimation of the value _νX,_Y(t)=_a1(t)_b1(t)+_a2(t)_b2(t)${\nu }_{X\text{,}Y}(t)=a_1(t)b_1(t)+a_2(t)b_2(t)$ called cross volatility. Our framework also contains the volatility estimation problem as a special case. We will show that our scheme works under mild assumptions on the activity of the jump process _Jt$J_t$.