Iterated greedy local search methods for unrelated parallel machine scheduling

This work deals with the parallel machine scheduling problem which consists in the assignment of n jobs on m   parallel machines. The most general variant of this problem is when the processing time depends on the machine to which each job is assigned to. This case is known as the unrelated parallel machine problem. Similarly to most of the literature, this paper deals with the minimization of the maximum completion time of the jobs, commonly referred to as makespan (_Cmax)$(C_{\text{max}})$. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated procedures. By contrast, in this paper we propose a set of simple iterated greedy local search based metaheuristics that produce solutions of very good quality in a very short amount of time. Extensive computational campaigns show that these solutions are, most of the time, better than the current state-of-the-art methodologies by a statistically significant margin.     

A condition-based replacement and spare provisioning policy for deteriorating systems with uncertain deterioration to failure

A new policy, referred to as the condition-based replacement and spare provisioning policy, is presented for deteriorating systems with a number of identical units. It combines the condition-based replacement policy with periodical inspections and the (S,s$S\text{,}s$) type inventory policy, noted as the (T,S,s,_Lp$T\text{,}S\text{,}s\text{,}{L}_{\text{p}}$) policy, where T is the inspection interval, S is the maximum stock level, s   is the reorder level, and _Lp$L_{\text{p}}$ is the preventive replacement threshold for the deterioration levels of units. The deterioration level of each unit in the system can be described by a scalar random variable, which is continuous and increasing monotonically. Furthermore, the deterioration level just when the unit failure occurs, termed deterioration to failure, is uncertain. Therefore, the condition-based reliability is proposed in order to characterize various and uncertain deterioration levels when unit failure occurs. A simulation model is developed for the system operation under the proposed condition-based replacement and spare provisioning policy. Thus, via the simulation method and the genetic algorithm, the decision variables T, S, s  , and _Lp$L_{\text{p}}$ can be jointly optimized for minimizing the cost rate. A case study is given, showing the procedure of applying the proposed policy and the condition-based reliability methodology to optimizing the maintenance scheme of haul truck motors at a mine site based on oil inspections, and proving beneficial for plant maintenance managers to reduce maintenance cost.     

Parallel machine scheduling with nested processing set restrictions

We consider the problem of scheduling a set of n independent jobs on m parallel machines, where each job can only be scheduled on a subset of machines called its processing set. The machines are linearly ordered, and the processing set of job j   is given by two machine indexes _aj$a_j$ and _bj$b_j$; i.e., job j   can only be scheduled on machines _aj,_aj+1,…,_bj$a_j\text{,}{a}_j+1\text{,}\dots \text{,}{b}_j$. Two distinct processing sets are either nested or disjoint. Preemption is not allowed. Our goal is to minimize the makespan. It is known that the problem is strongly NP-hard and that there is a list-type algorithm with a worst-case bound of 2-1/m$2-1/m$. In this paper we give an improved algorithm with a worst-case bound of 7/4. For two and three machines, the algorithm gives a better worst-case bound of 5/4 and 3/2, respectively.     

Bounds for naive multiple machine scheduling with release times and deadlines

We examine an on-line polynomial time heuristic for the NP-complete problem of scheduling m identical machines to minimize the maximum lateness of jobs with release times and due dates. The main result is that for any set of jobs, the difference between the lateness given by the heuristic and the minimum possible lateness is bounded by $\text{[}\text{(2m ? 1)}\text{m}\text{]P}{}_{\mathrm{<mtext>max</mtext>}}$, where P_max is the largest processing time of any of the jobs. The conclusion is that for many applications, optimization is not necessary. We also prove that when all jobs have a common processing time P, the difference between the heuristic and the minimum lateness is bounded by P. This gives a fast estimate of the minimum possible lateness, and is useful in accelerating the practical performance of algorithms for the exact solution.     

On the Lazarev–Lieb extension of the Hobby–Rice theorem

O. Lazarev and E.H. Lieb proved that, given _f1,…,_fn∈L¹([0,1];C)$f_1,\dots ,f_n\in L^1([0,1];\mathbb{C})$, there exists a smooth function Φ$\Phi$ that takes values on the unit circle and annihilates span{_f1,…,_fn}$\text{span}\{f_1,\dots ,f_n\}$. We give an alternative proof of that fact that also shows the W^1,1$W^{1,1}$ norm of Φ$\Phi$ can be bounded by 5πn+1$5\pi n+1$. Answering a question raised by Lazarev and Lieb, we show that if p>1$p>1$ then there is no bound for the W^1,p$W^{1,p}$ norm of any such multiplier in terms of the norms of _f1,…,_fn$f_1,\dots ,f_n$.     

Using an extended activated sludge model to simulate nitrite and nitrate variations in TNCU2 process

In this study, an extended activated sludge model was established to describe the transformation of nitrite (_SNO₂)$(S_{{\text{NO}}_2})$, nitrate (_SNO₃)$S_{{\text{NO}}_3})$ and other components in TNCU2 process (National Central University of Taiwan No. 2) that consisted of anaerobic, oxic, anoxic, oxic zones in sequence. The significant differences between this extended model and other models were that two-stage nitrification, multi-stage denitrification, and phosphorus removal were taken into account simultaneously. The results indicated that the growth rate constants of _XAOB$X_{\text{AOB}}$ and _XNOB$X_{\text{NOB}}$ were 1.4 and 0.4 d⁻¹, respectively. _YAOB$Y_{\text{AOB}}$ value was 0.14 and _YNOB$Y_{\text{NOB}}$ value was 0.04. According to model simulation, the heterotrophic microorganism (X_H), phosphorus accumulating organism (X_PAO), _XAOB$X_{\text{AOB}}$ and _XNOB$X_{\text{NOB}}$ concentrations were 1160–1322, 182–226, 21–26 and 13–17 mg l⁻¹, respectively, in TNCU2 process. _XH,_XPAO,_XAOB$X_{\text{H}}\text{,}{X}_{\text{PAO}}\text{,}{X}_{\text{AOB}}$, and _XNOB$X_{\text{NOB}}$ decreased in the anaerobic tanks because of the lysis reaction. Then _XH,_XPAO,_XAOB$X_{\text{H}}\text{,}{X}_{\text{PAO}}\text{,}{X}_{\text{AOB}}$, and _XNOB$X_{\text{NOB}}$ increased in the aerobic tanks due to aerobic growth. _XH,_XPAO,_XAOB$X_{\text{H}}\text{,}{X}_{\text{PAO}}\text{,}{X}_{\text{AOB}}$, and _XNOB$X_{\text{NOB}}$ increased in quantities by about 5%, 6%, 6% and 4% in the first aerobic tank and decreased in quantities by about 12%, 19%, 20% and 19% in the anoxic tank in which the step feeding influent flowed. The ratio of total nitrifying species to total active biomass was about 3% in each tank.     

Fatou sets of entire solutions of linear differential equations

This paper is devoted to studying the dynamical properties of solutions of f^″+A(z)f=0$f^{″}+A\left(z\right)f=0$, where A(z)$A\left(z\right)$ is an entire function of finite order. With some added conditions on A(z)$A\left(z\right)$, we prove that all the Fatou components of E(z)$E\left(z\right)$ are simply-connected provided that E=_f1f2$E=f_1{f}_2$ and _f1,_f2$f_1,f_2$ are two linearly independent solutions of such equations.     

Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan

We consider a scheduling problem in which n jobs are to be processed on a single machine. The jobs are processed in batches and the processing time of each job is a simple linear function of its waiting time, i.e., the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. The objective is to minimize the makespan, i.e., the completion time of the last job. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B  , the problem remains strongly NP-hard when B?U$B?U$ for a variable U?2$U?2$ or B?U$B?U$ for any constant U?2$U?2$. For the case of B?U$B?U$, we present a dynamic programming algorithm that runs in pseudo-polynomial time and a fully polynomial time approximation scheme (FPTAS) for any constant U?2$U?2$. Furthermore, we provide an optimal linear time algorithm for the special case where the jobs are subject to a linear precedence constraint, which subsumes the case where all the job growth rates are equal.     

A Widom like formula for some Toeplitz plus Hankel determinants

A well known Widom formula expresses the determinant of a Toeplitz matrix _Tn$T_n$ with Laurant polynomial symbol f in terms of the zeros of f. We give similar formulae for some even Toeplitz plus Hankel matrices. The formulae are based on an analytic representation of the determinant of such matrices in terms of Chebyshev polynomials.     

Frequency-dependent interpolation rules using first derivatives for oscillatory functions

We construct frequency-dependent rules to interpolate oscillatory functions y(x)$y(x)$ with frequency ω$\omega$ of the form,

y(x)=_f1(x)cos(ωx)+_f2(x)sin(ωx),$y(x)=f_1(x)\cos (\omega x)+f_2(x)\sin (\omega x)\text{,}$

S-Noetherian properties on amalgamated algebras along an ideal

Let A and B   be commutative rings with identity, f:A→B$f:A\to B$ a ring homomorphism and J an ideal of B  . Then the subring A?^fJ:={(a,f(a)+j)|a∈A and j∈J}$A{?}^{f}J:=\{(a,f(a)+j)|a\in A\text{and}j\in J\}$ of A×B$A\times B$ is called the amalgamation of A with B along with J with respect to f. In this paper, we investigate a general concept of the Noetherian property, called the S  -Noetherian property which was introduced by Anderson and Dumitrescu, on the ring A?^fJ$A{?}^{f}J$ for a multiplicative subset S   of A?^fJ$A{?}^{f}J$. As particular cases of the amalgamation, we also devote to study the transfers of the S  -Noetherian property to the constructions D+(_X1,…,_Xn)E[_X1,…,_Xn]$D+(X_1,\dots ,X_n)E[X_1,\dots ,X_n]$ and D+(_X1,…,_Xn)E?_X1,…,_Xn?$D+(X_1,\dots ,X_n)E?X_1,\dots ,X_n?$ and Nagata?s idealization.     

A minimal repair replacement model with two types of failure and a safety constraint

Consider a system subject to two types of failures. If the failure is of type 1, the system is minimally repaired, and a cost C₁ is incurred. If the failure is of type 2, the system is minimally repaired with probability p and replaced with probability 1−p  . The associated costs are _C2,_m$C_{2\text{,}m}$ and _C2,_r$C_{2\text{,}r}$, respectively. Failures of type 2 are safety critical and to control the risk, management has specified a requirement that the probability of at least one such failure occurring in the interval [0, A] should not exceed a fixed probability limit ω. The problem is to determine an optimal planned replacement time T, minimizing the expected discounted costs under the safety constraint. A cost C_r is incurred whenever a planned replacement is performed. Conditions are established for when the safety constraint affects the optimal replacement time and causes increased costs.     

Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects

This paper studies the single machine past-sequence-dependent (p-s-d) delivery times scheduling with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects we mean that the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. We consider the following objective functions: the makespan, the total completion time, the sum of the θ$\theta$th (θ?0$\theta ?0$) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of minimization of the makespan, the total completion time, the sum of the θ$\theta$th (θ?0$\theta ?0$) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness minimization problem, the maximum tardiness minimization problem and the total tardiness minimization problem can be solved in polynomial time under certain conditions.     

A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints

This study investigates scheduling problems that occur when the weighted number of late jobs that are subject to deterministic machine availability constraints have to be minimized. These problems can be modeled as a more general job selection problem. Cases with resumable, non-resumable, and semi-resumable jobs as well as cases without availability constraints are investigated. The proposed efficient mixed integer linear programming approach includes possible improvements to the model, notably specialized lifted knapsack cover cuts. The method proves to be competitive compared with existing dedicated methods: numerical experiments on randomly generated instances show that all 350-job instances of the test bed are closed for the well-known problem 1|_ri|∑_wiUi$1|r_i|\sum w_i{U}_i$. For all investigated problem types, 98.4% of 500-job instances can be solved to optimality within 1 hour.     

Development of an analytical–numerical solution for a steady and axisymmetric turbulent jet diffusion flame for the hydrogen based on a reduced kinetic mechanism

The hydrogen fuel is considered to be an ideal source of energy, because its complete combustion generates no pollutants, only water vapor. Therefore, the hydrogen has been suggested as a clean fuel. A detailed kinetic mechanism for the combustion of hydrogen that comprises eight species (_H2,_O2,O,OH,_H2O,H,_HO2$H_2\text{,}{O}_2\text{,}O\text{,}\mathit{OH}\text{,}{H}_{2}O\text{,}H\text{,}{\mathit{HO}}_2$ and _H2O2$H_2{O}_2$) and 20 elementary reactions, was reduced to two-step mechanism for nonpremixed flames involving four reactive species (_H2,_O2,H,_H2O$H_2\text{,}{O}_2\text{,}H\text{,}{H}_{2}O$). We performed, for this mechanism, a numerical analysis of the equations, including the velocity, mixture fraction, mass fractions and temperature. To quantify the components of intermediary reactions, the mixture fraction is decomposed into three parts, each part directly related to the mass fraction of each species. The results compare favorably with data in the literature for a jet diffusion flame of 50/50% in volume of _H2-_N2$H_2-N_2$. The main advantage of the strategy employed here is to decrease the work needed to solve the system of equations of the reactive flow.