Single Machine Scheduling with Time-Dependent Learning Effect and Non-Linear Past-Sequence-Dependent Setup Times

This paper studies a single machine scheduling problem with time-dependent learning and setup times. Time-dependent learning means that the actual processing time of a job is a function of the sum of the normal processing times of the jobs already scheduled. The setup time of a job is proportional to the length of the already processed jobs, that is, past-sequence-dependent (psd) setup time. We show that the addressed problem remains polynomially solvable for the objectives, i.e., minimization of the total completion time and minimization of the total weighted completion time. We also show that the smallest processing time (SPT) rule provides the optimum sequence for the addressed problem.

No-Wait Flowshops to Minimize Total Tardiness with Setup Times

The m-machine no-wait flowshop scheduling problem is addressed where setup times are treated as separate from processing times. The objective is to minimize total tardiness. Different dispatching rules have been investigated and three were found to be superior. Two heuristics, a simulated annealing (SA) and a genetic algorithm (GA), have been proposed by using the best performing dispatching rule as the initial solution for SA, and the three superior dispatching rules as part of the initial population for GA. Moreover, improved versions of SA and GA are proposed using an insertion algorithm. Extensive computational experiments reveal that the improved versions of SA and GA perform about 95% better than SA and GA. The improved version of GA outperforms the improved version of SA by about 3.5%.

A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times

A hybrid estimation of distribution algorithm (EDA) with iterated greedy (IG) search (EDA-IG) is proposed for solving the unrelated parallel machine scheduling problem with sequence-dependent setup times (UPMSP-SDST). For makespan criterion, some properties about neighborhood search operators to avoid invalid search are derived. A probability model based on neighbor relations of jobs is built in the EDA-based exploration phase to generate new solutions by sampling the promising search region. Two types of deconstruction and reconstruction as well as an IG search are designed in the IG-based exploitation phase. Computational complexity of the algorithm is analyzed, and the effect of parameters is investigated by using the Taguchi method of design-of-experiment. Numerical tests on 1640 benchmark instances are carried out. The results and comparisons demonstrate the effectiveness of the EDA-IG. Especially, the bestknown solutions of 531 instances are updated. In addition, the effectiveness of the properties is also demonstrated by numerical comparisons. © 2014 Chinese Association of Automation.

An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times

Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu- ally independent and available at time zero.The machine processes the jobs sequentially and it is not idle if there is any job to be pro- cessed.The operation of each job cannot be interrupted.The machine cannot process more than one job at a time.A setup time is needed if the machine switches from one type of job to another.The objective is to find an optimal schedule with the minimal total jobs’completion time.While the sum of jobs’processing time is always a constant,the objective is to minimize the sum of setup times.Ant colony optimization(ACO)is a meta-heuristic that has recently been applied to scheduling problem.In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation(DPBAC)algorithm for the single-machine schedul- ing problem.DPBAC improves traditional ACO in following aspects:introducing Branching Method to choose starting points;im- proving state transition rules;introducing Mutation Method to shorten tours;improving pheromone updating rules and introduc- ing Conditional Dynamic Perturbation Strategy.Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.

Hybrid Flow Shop with Setup Times Scheduling Problem

The two-stage hybridflow shop problem under setup times is addressed in this paper.This problem is NP-Hard.on the other hand,the studied problem is modeling different real-life applications especially in manufacturing and high performance-computing.Tackling this kind of problem requires the development of adapted algorithms.In this context,a metaheuristic using the genetic algorithm and three heuristics are proposed in this paper.These approximate solutions are using the optimal solution of the parallel machines under release and delivery times.Indeed,these solutions are iterative procedures focusing each time on a particular stage where a parallel machines problem is called to be solved.The general solution is then a concatenation of all the solutions in each stage.In addition,three lower bounds based on the relaxation method are provided.These lower bounds present a means to evaluate the efficiency of the developed algorithms throughout the measurement of the relative gap.An experimental result is discussed to evaluate the performance of the developed algorithms.In total,8960 instances are implemented and tested to show the results given by the proposed lower bounds and heuristics.Several indicators are given to compare between algorithms.The results illustrated in this paper show the performance of the developed algorithms in terms of gap and running time.

Identical Machine Scheduling Problem with Sequence-Dependent Setup Times: MILP Formulations Computational Study

This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph- based and sequence-based, of the well-known scheduling problem. Two upper bounds of job completion times are introduced. A numerical test result analysis is conducted with a two-fold objective 1) testing the performance of each solving methods, and 2) identifying and analyzing the tractability of an instance according to the instance structure in terms of the number of machines, of the jobs setup time lengths and of the jobs release date distribution over the scheduling horizon.

A Linear Programming Approach for Parallel Cell Scheduling with Sequence-Dependent Setup Times

In this study, we consider the problem of scheduling a set of jobs with sequence-dependent setup times on a set of parallel production cells. The objective of this study is to minimize the total completion time. We note that total customer demands for each type should be satisfied, and total required production time in each cell cannot exceed the capacity of the cell. This problem is formulated as an integer programming model and an interface is designed to provide integrity between data and software. Mathematical model is tested by both randomly generated data set and real-world data set from a factory that produce automotive components. As a result of this study, the solution which gives the best alternative production schedule is obtained.

Scheduling a three-machine no-wait flowshop with separated setup time

In many practical flowshop production environments, there is no intermediate storage space available to keep partially completed jobs between any two machines. The workflow has to be continuous, implying that the no-wait conditions must be abided, which is typical in steel and plastic production. We discuss the three-machine no-wait flowshop scheduling problem where the setup times are considered as separated from processing times and sequence independent. The scheduling goal is to minimize the total flowtime. An optimal property and two heuristic algorithms for this problem are proposed. Evaluated over a large number of problems, the proposed heuristics are found that they can yield good solutions effectively with low computational complexity, and have more obvious advantage for the large size problem compared with the existing one.

Oscillation of Third-order Delay Dynamic Equations on Time Scales

This paper is concerned with the oscillatory behavior of a class of third-order noonlinear variable delay neutral functional dynamic equations on time scale. By using the generalized Riccati transformation and inequality technique, we establish some new oscilla- tion criteria for the equations. Our results extend and improve some known results, but also unify the oscillation of third-order nonlinear variable delay functional differential equations and functional difference equations with a nonlinear neutral term. Some examples are given to illustrate the importance of our results.

Analytical Solutions of System of Non-Linear Differential Equations in the Single-Enzyme, Single-Substrate Reaction with Non-Mechanism-Based Enzyme Inactivation

A closed form of an analytical expression of concentration in the single-enzyme, single-substrate system for the full range of enzyme activities has been derived. The time dependent analytical solution for substrate, enzyme-substrate complex and product concentrations are presented by solving system of non-linear differential equation. We employ He’s Homotopy perturbation method to solve the coupled non-linear differential equations containing a non-linear term related to basic enzymatic reaction. The time dependent simple analytical expressions for substrate, enzyme-substrate and free enzyme concentrations have been derived in terms of dimensionless reaction diffusion parameters ε, λ1, λ2 and λ3 using perturbation method. The numerical solution of the problem is also reported using SCILAB software program. The analytical results are compared with our numerical results. An excellent agreement with simulation data is noted. The obtained results are valid for the whole solution domain.

A Hybrid Neural Network and Box-Jenkins Models for Time Series Forecasting

Time series forecasting plays a significant role in numerous applications,including but not limited to,industrial planning,water consumption,medical domains,exchange rates and consumer price index.The main problem is insufficient forecasting accuracy.The present study proposes a hybrid forecastingmethods to address this need.The proposed method includes three models.The first model is based on the autoregressive integrated moving average(ARIMA)statistical model;the second model is a back propagation neural network(BPNN)with adaptive slope and momentum parameters;and the thirdmodel is a hybridization between ARIMA and BPNN(ARIMA/BPNN)and artificial neural networks and ARIMA(ARIMA/ANN)to gain the benefits of linear and nonlinearmodeling.The forecasting models proposed in this study are used to predict the indices of the consumer price index(CPI),and predict the expected number of cancer patients in the Ibb Province in Yemen.Statistical standard measures used to evaluate the proposed method include(i)mean square error,(ii)mean absolute error,(iii)root mean square error,and(iv)mean absolute percentage error.Based on the computational results,the improvement rate of forecasting the CPI dataset was 5%,71%,and 4%for ARIMA/BPNN model,ARIMA/ANN model,and BPNN model respectively;while the result for cancer patients’dataset was 7%,200%,and 19%for ARIMA/BPNNmodel,ARIMA/ANN model,and BPNNmodel respectively.Therefore,it is obvious that the proposed method reduced the randomness degree,and the alterations affected the time series with data non-linearity.The ARIMA/ANN model outperformed each of its components when it was applied separately in terms of increasing the accuracy of forecasting and decreasing the overall errors of forecasting.

Non-Linear Localization Algorithm Based on Newton Iterations

In order to improve the performance of time difference of arrival(TDOA)localization,a nonlinear least squares algorithm is proposed in this paper.Firstly,based on the criterion of the minimized sum of square error of time difference of arrival,the location estimation is expressed as an optimal problem of a non-linear programming.Then,an initial point is obtained using the semi-definite programming.And finally,the location is extracted from the local optimal solution acquired by Newton iterations.Simulation results show that when the number of anchor nodes is large,the performance of the proposed algorithm will be significantly better than that of semi-definite programming approach with the increase of measurement noise.

Duffing Oscillator’s Vibration Control under Resonance with a Negative Velocity Feedback Control and Time Delay

An externally excited Duffing oscillator under feedback control is discussed and analyzed under the worst resonance case.Multiple time scales method is applied for this system to find analytic solution with the existence and nonexistence of the time delay on control loop.An appropriate stability analysis is also performed and appropriate choices for the feedback gains and the time delay are found in order to reduce the amplitude peak.Different response curves are involved to show and compare controller effects.In addition,analytic solutions are compared with numerical approximation solutions using Rung-Kutta method of fourth order.

Application of retardation time spectra of asphalt

To improve the performance of asphalt pavement, the dynamic and static tests of asphalt were used to measure its viscoelastic properties under different time. Based on the obtained data of static creep compliances and dynamic compliances according to the static creep test and dynamic test of asphalt using the dynamic shear rheometer, the discrete retardation time spectra were attained using the non-linear regression method. All viscoelastic functions are mathematically equivalent and belong to the same retardation time spectra, so the dynamic compliances of asphalt were converted to the static creep compliance using the retardation time spectra. Good correlations were found between calculation results and measurement results. In accordance to these findings, the retardation time spectra can accurately transform static and dynamic viscoelastic functions. Therefore, we can obtain viscoelastic properties over much larger time or frequency region than measurement results.

Time-dependent water permeation behavior of concrete under constant hydraulic pressure

In the present work, a concrete permeability testing setup was designed to study the behavior of hydraulic concrete subjected to constant hydraulic pressure. The results show that when concrete is subjected to high enough constant hydraulic pressure, it will be permeated, and after it reaches its maximum permeation rate, the permeability coefficient will gradually decrease towards a stable value. A time-dependent model of permeability coefficient for concrete subjected to hydraulic pressure is proposed. It is indicated that the decrease of the permeability coefficient with permeation time conforms well to the negative-exponential decrease model.

Suppressive Influence of Time- Space White Noise on the Explosion of Solutions of Stochastic Fokker- Planck Delay Differential Equations

It is generally known that the solutions of deterministic and stochastic differential equations （SDEs） usually grow linearly at such a rate that they may become unbounded after a small lapse of time and may eventually blow up or explode in finite time. If the drift and diffusion functions are globally Lipschitz, linear growth may still be experienced, as well as a possible blow-up of solutions in finite time. In this paper, a nonlinear scalar delay differential equation with a constant time lag is perturbed by a multiplicative Ito-type time - space white noise to form a stochastic Fokker-Planck delay differential equation. It is established that no explosion is possible in the presence of any intrinsically slow time - space white noise of Ito - type as manifested in the resulting stochastic Fokker- Planck delay differential equation. Time - space white noise has a role to play since the solution of the classical nonlinear equation without it still exhibits explosion.

The Research of Fractal Characteristics of the Electrocardiogram in a Real Time Mode

The article presents the results of recent investigations into Holter monitoring of ECG, using non-linear analysis methods. This paper discusses one of the modern methods of time series analysis--a method of deterministic chaos theory. It involves the transition from study of the characteristics of the signal to the investigation of metric （and probabilistic） properties of the reconstructed attractor of the signal. It is shown that one of the most precise characteristics of the functional state of biological systems is the dynamical trend of correlation dimension and entropy of the reconstructed attractor. On the basis of this it is suggested that a complex programming apparatus be created for calculating these characteristics on line. A similar programming product is being created now with the support of RFBR. The first results of the working program, its adjustment, and further development, are also considered in the article.

设备故障下的零空闲多设备工作中心调度

设备故障是车间调度中最为常见的动态事件,易对原生产调度计划造成影响。为保证加工生产在遇到设备故障后能够快速地对原调度方案做出调整,降低设备故障所带来的负面影响,对设备故障下的零空闲多设备工作中心调度问题进行研究。建立了设备故障下考虑调整时间和搬运时间的零空闲多设备工作中心调度模型,优化目标为最小化最大完工时间、搬运次数和系统稳定性;设计NSGA-Ⅱ-V算法用于原调度和重调度的求解;基于NSGA-Ⅱ-V获得的静态调度结果与部分重调度策略的思想,进行设备故障算例测试。测试结果表明,所提模型和算法可较好地处理动态事件为设备故障的零空闲多设备工作中心调度问题。

考虑序列相关准备时间的分布式柔性作业车间调度研究

针对考虑序列相关准备时间的分布式柔性作业车间调度问题,提出以最小化最大完工时间为优化目标的混合整数线性规划模型,并提出一种改进遗传算法。采用基于负荷均衡的种群初始化方法提高初始种群质量,根据问题特性构造6个局部扰动算子,设计多重局部扰动策略提高算法的局部搜索能力。通过扩展柔性作业车间调度基准生成测试算例,使用正交实验确定算法参数。实验结果表明,所提改进策略能够有效提高算法性能,求解结果优于对比算法,验证了调度模型和所提算法的可行性和有效性。