Parallel-machine scheduling with an availability constraint

e consider two parallel machines scheduling problem where one machine is not available in a specified time period. The unavailable time period is fixed and known in advance. The objective is to minimize the total weighted completion time. The problem is known to be NP-hard. We give a fully polynomial-time approximation scheme (FPTAS) for the problem. We then generalize the results to the case with m parallel machines.     

Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability

This article considers the unrelated parallel machine scheduling problem with sequence- and machine-dependent setup times and machine-dependent processing times. Furthermore, the machine has a production availability constraint to each job. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the total completion time. To solve the problem, a mathematical model for the optimal solution is derived, and hybrid genetic algorithms with three dispatching rules are proposed for large-sized problems. To assess the performance of the algorithms, computational experiments are conducted and evaluated using several randomly generated examples.     

Criterion of calibration for transductive confidence machine with limited feedback

This paper is concerned with the problem of on-line prediction in the situation where some data are unlabelled and can never be used for prediction, and even when the data are labelled, the labels may arrive with a delay. We construct a modification of randomised transductive confidence machine for this case and prove a necessary and sufficient condition for its predictions being calibrated, in the sense that in the long run they are wrong with a prespecified probability under the assumption that the data are generated independently by the same distribution. The condition for calibration turns out to be very weak: feedback should be given on more than a logarithmic fraction of steps.     

Minimizing the makespan in the non-preemptive job-shop scheduling with limited machine availability

This paper addresses the makespan minimization in a job-shop environment where the machines are not available during the whole planning horizon. The disjunctive graph model is used to represent the schedules and the concept of blocks is generalized to include the unavailability periods of machines. To solve the problem, we develop a taboo thresholding heuristic that uses a new block-based neighborhood function. Some sufficient conditions to eliminate the evaluation of non-improving moves are proposed. Experiments performed on existing problem instances of the literature show the efficiency of the proposed heuristic.     

Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints

One of the common assumptions in the field of scheduling is that machines are always available in the planning horizon. This may not be true in realistic problems since machines might be busy processing some jobs left from previous production horizon, breakdowns or preventive maintenance activities. Another common assumption is the consideration of setup times as a part of processing times, while in some industries, such as printed circuit board and automobile manufacturing, not only setups are an important factor but also setup magnitude of a job depends on its immediately preceding job on the same machine, known as sequence-dependent setup times. In this paper, we consider hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints caused by preventive maintenance. The optimization criterion is the minimization of makespan. Since this problem is NP-hard in the strong sense, we propose three heuristics, based on SPT, LPT and Johnson rule and two metaheuristics based on genetic algorithm and simulated annealing. Computational experiments are performed to evaluate the efficiencies of the algorithms.     

Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine

The scheduling problem with deteriorating jobs to minimize the makespan on a single machine where the facility has an availability constraint is studied in this paper. By a deteriorating job we mean that the processing time for the job is a function of its starting time. Even with the introduction of the availability to a facility, the linear deteriorating model can be solved using the 0-1 integer programming technique if the actual job processing time is proportional to the starting time.     

Parallel machine scheduling problem with preemptive jobs and transportation delay

In this research the parallel machine scheduling problem with preemption by considering a constant transportation delay for migrated jobs and minimization of makespan as the criterion i.e., P_m|pmtn(delay)|C_max is investigated. It is assumed that when a preempted job resumes on another machine, it is required a delay between the processing time of the job on these two machines. This delay is called transportation delay. We criticize an existing mathematical model for the research problem in the literature [Boudhar M, Haned A. Preemptive scheduling in the presence of transportation times. Computers & Operations Research 2009; 36(8):2387–93]. Then, we prove that there exists an optimal schedule with at most (m−1) preemptions with transportation among machines for the problem. We also propose a linear programming formulation and an exact algorithm for the research problem in case of equal transportation delay. The experiments show that the proposed exact algorithm performs better than the proposed mathematical model.     

Sensitivity analysis of the machine repair problem with general repeated attempts

In this paper, we propose a machine repair problem with constant retrial policy, wherein if a failed machine finds the repairman busy upon arrival, it enters into an orbit. The machines in the orbit form a single waiting line, and only the one at the head of the orbit repeats its request for repair. The failure times of operating machines and the repair times of failed machines follow exponential distributions. It is assumed that retrial times are generally distributed. We used the supplementary variable technique to obtain explicit expressions for the steady-state probabilities of the number of failed machines in the orbit. We performed sensitivity analysis of the machine availability and operative efficiency with respect to system parameters and the number of machines in operation. The analysis of the busy period and the waiting time were also presented. Finally, we developed a cost model and formulated a cost minimization problem.     

Network availability prediction with hidden context

Modern mobile devices are increasingly capable of simultaneously connecting to multiple access networks with different characteristics. Restricted coverage combined with user mobility will vary the availability of networks for a mobile device. Most proposed solutions for such an environment are reactive in nature, such as performing a vertical handover to the network that offers the highest bandwidth. But the cost of the handover may not be justified if that network is only available for a short time. Knowledge of future network availability and their capabilities are the basis for proactive schemes which will improve network selection and utilization. We have previously proposed a prediction model that can use any available context such as GSM Location Area, WLAN presence or even whether the power cable is plugged in, to predict network availability.As it may not be possible to sense all of the context variables that influence future network availability, in this paper we introduce a generic, new model incorporating a hidden variable to account for this. Specifically, we propose a Dynamic Bayesian Network based context prediction model to predict network availability. Predictions performed for WLAN availability with the real user data collected in our experiments show 20% or more improvement compared to both of our earlier proposals of order 1 and 2 semi-Markov models.     

Algorithms for scheduling incompatible job families on single batching machine with limited capacity

Motivated by applications in food processing and semiconductor manufacturing industries, we consider the scheduling problem of a batching machine with jobs of multiple families. The machine has a limited capacity to accommodate jobs. The jobs are in arbitrary sizes and multiple families. Jobs from different families cannot be processed in a batch. We show the problems of minimizing makespan and total batch completion time are both NP-hard in the strong sense. We present a mixed integer programming model for the problems. Then we propose two polynomial time heuristics based on longest processing time first rule and first fit rule. For the special case where a larger job also has a longer processing time, the heuristic for minimizing makespan is optimal. For the general case, we show the performance guarantee of the methods for the two objectives respectively.     

Multiobjective pseudo‐variable neighborhood descent for a bicriteria parallel machine scheduling problem with setup time

A multiobjective variable neighborhood descent (VND) based heuristic is developed to solve a bicriteria parallel machine scheduling problem. The problem considers two objectives, one related to the makespan and the other to the flow time, where the setup time depends on the sequence, and the machines are identical. The heuristic has a set of neighborhood structures based on swap, remove, and insertion moves. We propose changing the local search inside the VND to a sequential search through the neighborhoods to obtain nondominated points for the Pareto‐front quickly. In the numerical tests, we consider a single‐objective version of the heuristic, comparing the results on 510 benchmark instances to show that it is quite effective. Moreover, new instances are generated in accordance with the literature for the bicriteria problem, showing the ability of the proposed heuristic to return an efficient set of nondominate solutions compared with the well‐known nondominated sorting genetic algorithm II.     

Enhancing Java server availability with JAS

The Java programming language is increasingly used in the implementation of servers with stringent availability, reliability, and performance requirements. Our Java Application Supervisor (JAS) software system is an attachment to a Java runtime environment that enhances the availability of a target Java program. To this end, JAS automatically detects and resolves certain reliability and performance problems during the execution of the target program. JAS does not require any source or byte code modifications in the target program. Instead, JAS is configured for a target program by supplying simple policies that determine how JAS reacts to problems during the target program execution. JAS typically imposes little execution time and memory overhead on the target program. We describe an experiment with a Web proxy that exhibits reliability and performance problems under heavy load. In this experiment, running the proxy in conjunction with JAS increased the rate of successful requests to the proxy by 33% and decreased the averagerequest processing time by 22%. JAS was also used successfully in two Java servers at Bell Labs to monitor server reliability and performance and ensure long‐term availability. Copyright © 2001 John Wiley & Sons, Ltd.     

计算机应用系统可用性预测方法

随着银行业务领域的拓展,与之对应支持的科技应用系统也越来越多,如何根据当前系统的使用情况,对系统未来性能进行预测,从而很好的指导各个应用系统的维护工作成为当前亟待解决的问题.通过引入可靠性关于时间t的指数分布,对计算机系统未来的可靠性进行预测,从而获得系统可用性、和平均故障间隔的预测值.     

A hybridization of simulated annealing and electromagnetic-like mechanism for job shop problems with machine availability and sequence-dependent setup times to minimize total weighted tardiness

In this paper, we explore job shop problems with two recently popular and realistic assumptions, sequence-dependent setup times and machine availability constraints to actualize the problem. The criterion is a minimization of total weighted tardiness. We establish a simple criterion to integrate machine availability constraints and scheduling decisions simultaneously. We propose a hybrid meta-heuristic to tackle the given problem. This meta-heuristic method, called EMSA, is a combination of two meta-heuristics: (1) Electromagnetic-like mechanism (EM); and (2) simulated annealing (SA). The hybridization is done to overcome some existing drawbacks of each of these two algorithms. To evaluate the proposed hybrid meta-heuristic method, we carry out a benchmark by which the proposed EMSA is compared with some existing algorithms as well as simulated annealing and electromagnetic-like mechanism alone in a fixed given computational time. All the related results and analysis obtained through the benchmark illustrate that our proposed EMSA is very effective and supersedes the foregoing algorithms.     

保障服务可用性的多阶段动态冗余策略

现有关于服务冗余策略的研究工作侧重于研究冗余服务池模型和服务选择机制,过度冗余或服务池频繁调整的开销较大。为了降低冗余服务的开销,提出了服务的多阶段动态冗余策略,在分析服务可用性波动特性的基础上,采用灰模型获取可用性突变点,并根据突变点对可用性进行阶段划分,根据动态多阶段规划确定服务冗余度。实验结果表明提出的多阶段动态冗余策略能够保障可用性并有效降低开销。     

基于虚拟化技术的有效提高系统可用性的方法

针对安全攸关的客户机在安全工具发生警报时往往会进行暂停、检测、恢复等操作,而安全工具误报（虚报、漏报）的发生和发现存在延迟,从而对客户机造成可用性影响的问题,提出一种基于虚拟化技术的有效解决方案。在误报发生时,首先正确控制可疑进程行为,避免该进程对系统造成实质性影响。其次记录可疑进程行为,并根据其与系统其他进程的交互行为形成进程间依赖关系。当误报被发现时,以记录的进程行为及进程间依赖关系为依据,对可疑进程及与其存在依赖关系的相关进程采取恢复进程行为、杀死相关进程等措施,使系统快速达到正确运行状态。实验结果表明,所提方案能够在安全工具发生误报时,避免回滚、恢复等操作带来的时间开销,相对于未采取措施的情况,所提方案将误报存在时的处理时间减少20%~50%。所提方案能够有效降低安全工具误报对客户机可用性造成的影响,可应用在安全攸关的客户机所在的云平台之上。     

通讯受限条件下的机器人编队算法

针对通讯受限条件下大规模移动机器人编队任务,本文提出了基于行为的分布式多机器人线形编队控制和避障算法.机器人个体无需获得群体中所有机器人的信息,而是根据传感器获取的环境信息和局部范围内的机器人信息对其自身的调整方向进行预测,并最终很好地完成了设定的编队及避障任务.由于本文方法需求的通讯量不大,并且采用分布式控制,因此该...     

Two–machine flowshop minimum–length scheduling problem with random and bounded processing times

We address the two–machine flowshop scheduling problem to minimize makespan where jobs have random and bounded processing times. The probability distributions of job processing times are unknown and only the lower and upper bounds of processing times are given before scheduling. In such cases there may not exist a unique schedule that remains optimal for all possible realizations of processing times, and therefore, a set of schedules has to be considered which dominates all other schedules. In this paper, we find some sufficient conditions for the considered problem.     

Scheduling optimization of a stochastic flexible job-shop system with time-varying machine failure rate

Due to environmental circumstances encountered in manufacturing processes, operating machines need to be maintained preventively, so as to ensure satisfactory operating condition. This paper investigates a scheduling problem in a flexible job-shop system with maintenance considerations where each operation can be processed by a machine out of a set of capable machines, and so, jobs may have alternative routes. Machine failure rates are assumed to be time-varying. This is a real assumption comes from a fact in realistic environments, where failure rate of a machine is variable when environmental situations like shop temperature, shop light, shop humidity or even worker skill change significantly. Moreover, in order to more close the addressed problem into the situations encountered in real world, the processing times and due dates are considered to be stochastic parameters. A mixed integer linear programming (MILP) model is constructed for addressed problem with the objective of number of tardy jobs and a minimum total availability constraint. Then a simulation-optimization framework based on a simulated annealing (SA) optimizer and Monte Carlo (MC) simulator is presented to solve the problem.     

缓冲区有限的流水车间调度问题的启发式算法

针对缓冲区有限的流水车间调度问题,分析了目标函数的特征,及目标函数与工件空闲时间之间的关系,设计开发了启发式算法。算法将以Makespan为目标函数转化成以最小化机器空闲时间为目标函数,并以此为基础构造初始加工序列,再通过贪婪排序与插入寻优消除缓冲区受限约束并寻找问题的近优解。仿真实验结果表明,算法在求解质量和计算时间方面明显优于其他几种排序规则,并体现了目标函数表达式结构的特性及对解的适应性。