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.     

Pareto and scalar bicriterion optimization in scheduling deteriorating jobs

In the paper two problems of a single machine bicriterion scheduling of a set of deteriorating jobs are considered. The jobs are independent, nonpreemptable and are ready for processing at time 0$0$. The processing time _pj$p_j$ of each job is a linear function of the starting time _Sj$S_j$ of the job, _pj=1+_αjSj$p_j=1+{\alpha }_j{S}_j$, where _Sj?0$S_j?0$ and _αj>0${\alpha }_j>0$ for j=0,1,...,n$j=0,1,...,n$.     

From Nerode’s congruence to suffix automata with mismatches

In this paper we focus on the minimal deterministic finite automaton _Sk$S_k$ that recognizes the set of suffixes of a word w$w$ up to k$k$ errors. As first result we give a characterization of the Nerode’s right-invariant congruence that is associated with _Sk$S_k$. This result generalizes the classical characterization described in [A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985, 31–55]. As second result we present an algorithm that makes use of _Sk$S_k$ to accept in an efficient way the language of all suffixes of w$w$ up to k$k$ errors in every window of size r$r$ of a text, where r$r$ is the repetition index of w$w$. Moreover, we give some experimental results on some well-known words, like prefixes of Fibonacci and Thue-Morse words. Finally, we state a conjecture and an open problem on the size and the construction of the suffix automaton with mismatches.     

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$.     

Online bin packing with arbitrary release times

We study a new variant of the online bin-packing problem, in which each item _ai$a_i$ is associated with a size _ai$a_i$ and also a release time _ri$r_i$ so that it must be placed at least _ri$r_i$ above the bottom of a bin. Items arrive in turn and must be assigned without any knowledge of subsequent items. The goal is to pack all items into unit-size bins using the minimum number of bins. We study the problem with all items have equal size. First, we show that the ANY FIT algorithm cannot be approximated within any constant. Then we present a best possible online algorithm with asymptotic competitive ratio of two.     

Investigation of Lattice Boltzmann wetting boundary conditions for capillaries with irregular polygonal cross-section

We have investigated the performance of an alternative wetting boundary condition for complex geometries in a phase field Lattice Boltzmann scheme, which is an alternative to the commonly used formulation by Yeomans and coworkers. Though our boundary condition is much simpler in its implementation, all investigated schemes show proper droplet spreading behaviour following the Cox–Voinov law. Still, numerical artefacts like spurious velocities or chequer board effects in the pressure field can be significantly reduced by the use of a two-relaxation-time (TRT) scheme, likewise recent studies by the Yeomans group. The outstanding property of our implementation is the presence of an (artificial) thin wetting layer, which influences the relation between the saturation (_Sw$S_w$) and capillary pressure _pcap$p_{cap}$ in channels with irregular polygonal cross section. The _pcap(_Sw)$p_{cap}\left(S_w\right)$ relation from our simulation follows the shifted-Young–Laplace (sYL) law, showing that the physics of this wetting layer is similar to precursor films due to Van der Waals forces. With the knowledge of the thickness of the wetting layer, simulation results can be translated back to realistic pore configurations with thinner wetting layers.     

Minimum cost source location problem with local 3-vertex-connectivity requirements

Let G=(V,E)$G=(V,E)$ be a simple undirected graph with a set V$V$ of vertices and a set E$E$ of edges. Each vertex v∈V$v\in V$ has a demand d(v)∈_Z+$d\left(v\right)\in Z_{+}$ and a cost c(v)∈_R+$c\left(v\right)\in R_{+}$, where _Z+$Z_{+}$ and _R+$R_{+}$ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G$G$ requires finding a set S$S$ of vertices minimizing _∑v∈Sc(v)${\sum }_{v\in S}c\left(v\right)$ such that there are at least d(v)$d\left(v\right)$ pairwise vertex-disjoint paths from S$S$ to v$v$ for each vertex v∈V−S$v\in V-S$. It is known that if there exists a vertex v∈V$v\in V$ with d(v)≥4$d\left(v\right)\ge 4$, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in O(|V|⁴log²|V|)$O\left({\left|V\right|}^4{log}^2\left|V\right|\right)$ time if d(v)≤3$d\left(v\right)\le 3$ holds for each vertex v∈V$v\in V$.     

Affine-evasive sets modulo a prime

In this work, we describe a simple and efficient construction of a large subset S   of _Fp${\mathbb{F}}_p$, where p   is a prime, such that the set A(S)$A(S)$ for any non-identity affine map A   over _Fp${\mathbb{F}}_p$ has small intersection with S.     

Data-stream-based global event monitoring using pairwise interactions

The problem of global state observation is fundamental to distributed systems and to the analysis of data streams. Many interactions in distributed systems can be analyzed in terms of the building block formed by the pairwise interactions of intervals at two processes. Considering causality-based pairwise interactions by which two processes may interact with each other, there are 40 orthogonal interaction types. For each pair of processes (_Pi,_Pj)$(P_i,P_j)$, let interaction type _ri,j$r_{i,j}$ be of interest. This paper examines the problem: “If a global state of interest to an application is specified in terms of such pairwise interaction types, one per pair of processes, how can such a global state be detected?” A solution identifies a global state in which the interaction type specified for each process pair is satisfied. This paper formulates the specific conditions on the communication structures to determine which of the intervals being examined at any time may never satisfy the stipulated interaction type for that pair of processes, and therefore that interval(s) need no longer be considered as forming a part of any solution. Based on this theory, the paper proposes two on-line distributed algorithms to solve the problem.     

Continuous and impulsive vaccination of SEIR epidemic models with saturation incidence rates

In this paper, two delayed SEIR epidemic models with continuous and impulsive vaccination and saturating incidence are investigated. The dynamical behaviors of the disease are analyzed. For continuous vaccination, we obtain a basic reproductive number _R1$R_1$ and prove that if _R1≤1$R_1\le 1$ then the disease-free equilibrium is globally attractive and if _R1>1$R_1>1$ then the disease is permanent by using the Lyapunov functional method. For impulsive vaccination, we obtain two thresholds R^∗$R^{\ast }$ and _R∗$R_{\ast }$ and prove that if R^∗<1$R^{\ast }<1$ then the disease-free periodic solution is globally attractive and if _R∗>1$R_{\ast }>1$ then the disease is permanent by using the comparison theorem of impulsive differential equation and the Lyapunov functional method. Lastly, we compared the effects of two vaccination strategies.     

Minimizing earliness and tardiness subject to total completion time in an identical parallel machine system

This study addresses the identical parallel machine scheduling problem in which the total earliness and tardiness about a common due date are minimized subject to minimum total flowtime, P∥(E+T)/∑_Ci$P\parallel (E+T)/\sum C_i$. The problem is demonstrated to be transformed into a simplified version of the parallel machine problem with the objective of minimizing makespan subject to minimum total flowtime, P∥_Cmax/∑_Ci$P\parallel C_{\max }/\sum C_i$. Several properties are considered to solve optimally the restricted version of the problem. A streamlined binary integer programming model is developed to solve the P∥_Cmax/∑_Ci$P\parallel C_{\max }/\sum C_i$ problem and the P∥(E+T)/∑_Ci$P\parallel (E+T)/\sum C_i$ problem. Computational experiments indicate that the binary integer programming model is superior to the existing optimization algorithm for the P∥_Cmax/∑_Ci$P\parallel C_{\max }/\sum C_i$ problem in the literature.     

On learning embedded midbit functions

A midbit function on ?$?$ binary inputs _x1,…,_x?$x_1,\dots ,x_{?}$ outputs the middle bit in the binary representation of _x1+?+_x?$x_1+?+x_{?}$. We consider the problem of Probably Approximately Correct (PAC) learning embedded   midbit functions, where the set S⊂{_x1,…,_xn}$S\subset \{x_1,\dots ,x_n\}$ of relevant variables on which the midbit depends is unknown to the learner.     

A new model for path planning with interval data

In this paper, we establish a new model for path planning with interval data which arises in a variety of applications. It is formulated as minimum risk-sum path problem  : given a source-destination pair in a network G=(V,E)$G=(V,E)$, traveling on each link e in G   may take time _xe$x_e$ in a prespecified interval [_le,_ue]$[l_e,u_e]$ and take risk (_ue-_xe)/(_ue-_le)$(u_e-x_e)/(u_e-l_e)$, the goal is to find a path in G from the source to the destination, together with an allocation of travel times along each link on the path, so that the total travel time of links on the path is no more than a given time bound and the risk-sum over the links on the path is minimized. Our study shows that this new model has two features that make it different from the existing models. First, the minimum risk-sum path problem is polynomial-time solvable, and second, it provides many solutions that vary with time bounds and risk sums and leaves the choice for decision makers. Therefore, the new model is more flexible and easier to use for the path planning with interval data.     

Choosing starting values for certain Newton–Raphson iterations

We aim at finding the best possible seed values when computing a^1/p$a^{1/p}$ using the Newton–Raphson iteration in a given interval. A natural choice of the seed value would be the one that best approximates the expected result. It turns out that in most cases, the best seed value can be quite far from this natural choice. When we evaluate a monotone function f(a)$f(a)$ in the interval [_amin,_amax]$[a_{\min },a_{\max }]$, by building the sequence _xn$x_n$ defined by the Newton–Raphson iteration, the natural choice consists in choosing _x0$x_0$ equal to the arithmetic mean of the endpoint values. This minimizes the maximum possible distance between _x0$x_0$ and f(a)$f(a)$. And yet, if we perform n$n$ iterations, what matters is to minimize the maximum possible distance between _xn$x_n$ and f(a)$f(a)$. In several examples, the value of the best starting point varies rather significantly with the number of iterations.