Scheduling a hybrid flowshop with batch production at the last stage

In this paper, we address the problem of scheduling n$n$ jobs in an s$s$-stage hybrid flowshop with batch production at the last stage with the objective of minimizing a given criterion with respect to the completion time. The batch production at stage s$s$ is referred to as serial batches by Hopp and Spearman where the processing time of a batch is equal to the sum of the processing times of all jobs included in it. This paper establishes an integer programming model and proposes a batch decoupling based Lagrangian relaxation algorithm for this problem. In this algorithm, after capacity constraints are relaxed by Lagrangian multipliers, the relaxed problem is decomposed based on a batch, unlike the commonly used job decoupling, so that it can be decomposed into batch-level subproblems, each for a specific batch. An improved forward dynamic programming algorithm is then designed for solving these subproblems where all operations within a batch form an in-tree structure and the precedence relations exist not only between the operations of a job but between the jobs in this batch at the last stage. A computational comparison is provided for the developed algorithm and the commonly used Lagrangian relaxation algorithm which, after capacity constraints and precedence relations within a batch are relaxed, decomposes the relaxed problem into job-level subproblems and solves the subproblems by using dynamic programming. Numerical results show that the designed Lagrangian relaxation method provides much better schedules and converges faster for small to medium sized problems, especially for larger sized problems.     

An improved meta-heuristic for makespan minimization of a single batch machine with non-identical job sizes

We consider the problem of minimizing the makespan on a single batch machine with non-identical job sizes, where several jobs can be simultaneously processed as a batch. We formulate makespan minimization as a problem of minimizing the wasted space. Applying a candidate set strategy to narrow the search space, combined with a wasted-space-based heuristic to update the pheromone information, an improved max–min ant system algorithm is presented. A specific local search method is incorporated to gain better performance. Appropriate parameter settings in the proposed algorithm are determined by extensive experiments. The experimental results show that the proposed algorithm outperforms several previously studied algorithms.     

Optimal control of rapid thermal annealing in a semiconductor process

This study focuses on the optimal control of rapid thermal annealing (RTA) used in the formation of ultrashallow junctions needed in next-generation microelectronic devices. Comparison of different parameterizations of the optimal trajectories shows that linear profiles give the best combination of minimizing junction depth and sheet resistance. Worst-case robustness analysis of the optimal control trajectory motivates improvements in feedback control implementations for these processes. This is the first time that the effects of model uncertainties and control implementation inaccuracies are rigorously quantified for RTA.     

间歇式本体法生产聚丙烯升温过程分析

优化间歇式本体法生产聚丙烯工艺对提高产品质量和降低生产能耗具有重要的意义。利用小波多尺度分析功能研究一家大型液相小本体法生产工艺的升温曲线,通过对其进行去噪、重构、分解得到更真实的升温曲线,并对信号的近似和细节部分进行区分,确定各频带的信号形式和发生时间,结合液相本体法的工艺,分析各层信号与实际聚合工艺之间的关系。运用MATLAB软件中的小波分解系数灰度图来确定信号的能量的分布,验证各层信号特征与聚合过程工艺之间的对应关系,为下一步实现工艺优化提供理论基础。     

集卡分批到达模式下的进口箱场桥作业调度优化

在进口箱疏港过程中, 服务于相同客户的若干集卡组成集卡组, 具有相同的抵港时间, 因此, 外部集卡抵港提箱呈现分批到达的特点. 集卡组内作业指派的优劣直接影响场桥的作业效率, 存在较大的优化空间. 对此, 基于翻箱作业不能跨贝进行的现实约束, 将场桥作业调度解构为场桥作业路径优化问题和贝内翻箱作业优化问题两部分并分别建立动态优化模型. 针对场桥作业路径优化问题, 提出一种多项式时间的精确算法并给以证明; 针对贝内翻箱作业优化问题, 设计一种基于MSA的双层启发式算法进行求解. 一系列数值实验的结果显示了所提出优化模型及算法的有效性和鲁棒性.

     

Aspen Dynamics simulation of a middle-vessel batch distillation process

Aspen Dynamics is a powerful dynamic simulator that is widely used to explore the dynamics and control of continuous processes around some steady-state design operating point. This paper explores its use to study the dynamics of a batch process. The example studied is a middle-vessel batch distillation system for separating a ternary mixture. The batch system is operated by adjusting the two reflux flowrates (one from the reflux drum to the top of the upper column and the second from the middle vessel to the top of the lower column). The liquid inventories in the three drums vary with time. This paper shows how this batch operation can be conveniently simulated by first using the steady-state simulator Aspen Plus to correctly size the equipment. Then the file is exported into Aspen Dynamics where a rigorous dynamic simulation can explore alternative control strategies by using the large library of control functions.     

Scheduling rules to minimize total tardiness in a parallel machine problem with setup and calendar constraints

Quality control lead times are one of most significant causes of loss of time in the pharmaceutical and cosmetics industries. This is partly due to the organization of laboratories that feature parallel multipurpose machines for chromatographic analyses. The testing process requires long setup times and operators are needed to launch the process. The various controls are non-preemptive and are characterized by a release date, a due date and available routings. These quality processes lead to significant delays, and we therefore evaluate the total tardiness criterion. Previous heuristics were defined for the total tardiness criterion, parallel machines, and setup such as apparent tardiness cost (ATC) and ATC with setups (ATCS). We propose new rules and a simulated annealing procedure in order to minimize total tardiness.     

Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing

This paper aims at minimizing the makespan of two batch-processing machines in a flow shop. The processing times and the sizes of the jobs are known and non-identical. The machines can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time among all the jobs in that batch. The problem under study is NP-hard for makespan objective. Consequently, a heuristic based on Johnson's algorithm and a simulated annealing (SA) algorithm is proposed. Random instances were generated to verify the effectiveness of the proposed approaches. The results obtained from SA were compared with the proposed heuristic and a commercial solver. The SA outperformed both the heuristic and the commercial solver. On larger problem instances, the heuristic outperformed the commercial solver.     

Online monitoring of batch processes using multi-phase principal component analysis

Unfold Principal Component Analysis (u-PCA) has been successfully applied in the monitoring of batch processes. The traditional online monitoring strategy is based on the same unfolding procedure used for end-of-batch monitoring. This procedure may distort the interval where the process is out of normal operation, with delays in the detection of a fault or in the return to normal operation of a faulty batch. In this paper, a new strategy for the generation of a model specially suited for on-line monitoring is presented. This method is based on the combination of four ideas: mean trajectory subtraction and auto-scaling as preprocessing, variable-wise unfolding, addition of lagged variables to fit the dynamics and multi-phase modelling with multi-phase PCA. Evolving and local models have been included in the comparative analysis of the different approaches.     

Iterative learning control-based batch process control technique for integrated control of end product properties and transient profiles of process variables

Importance of batch processes has grown recently with the increasing economic competition that has pushed the manufacturing industries to pursue small quantity production of diverse high value-added products. Accordingly, systems engineering research on advanced control and optimization of batch processes has proliferated. In this paper, we examine the potentials of ‘iterative learning control (ILC)’ as a framework for industrial batch process control and optimization. First, various ILC rules are reviewed to provide a historical perspective. Next it is shown how the concept of ILC can be fused with model predictive control (MPC) to build an integrated end product and transient profile control technique for industrial chemical batch processes. Possible extensions and modifications of the technique are also presented along with some numerical illustrations. Finally, other related techniques are introduced to note the similarities and contemplate the opportunities for synergistic integration with the current ILC framework.     

Experiences in batch trajectory alignment for pharmaceutical process improvement through multivariate latent variable modelling

The primary objective of batch data as trajectory alignment (or synchronization) is to standardize the data sampling per batch according to the evolution of the process, and secondarily to homogenize the samples per run. The use of an indicator variable performs both objectives well. Two examples from the pharmaceutical sector are discussed to illustrate the different ways to deal with uneven samples across batches and across variables in the same batch. Since trajectory alignment requires large time investment, a simple triage approach is proposed to assess the need to analyze the dynamics of a given process and hence perform alignment. The presented examples are representative of a broad variety of batch processes that are operated by recipe in the pharmaceutical sector. In our experience, the variables associated with the automation triggers in these recipes are the best indicator variables to use for alignment. This is due to (i) the fact that the trigger variables are easy to identify from the automation of the recipe, (ii) operators are familiar with these, (iii) the target values for triggers are known a priori and hence the resulting alignment scheme can be performed in real-time for monitoring applications and (iv) it makes the monitoring scheme easy to understand and justify around the design-space since the design-space may originally be defined in terms of the trigger variables for each phase of the batch.     

A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals

In this paper, we consider a single batch machine scheduling problem with incompatible job families and dynamic job arrivals. The objective is to minimize the total completion time. This problem is known to be strongly NP-hard. We present several dominance properties and two types of lower bounds, which are incorporated to construct a basic branch and bound algorithm. Furthermore, according to the characteristics of dynamic job arrivals, a decomposed branch and bound algorithm is proposed to improve the efficiency. The proposed algorithms are tested on a large set of randomly generated problem instances.     

LRD and SRD traffic: review of results and open issues for the batch renewal process

The batch renewal process is the least-biased choice of process given only the measures of count correlation and interval correlation at all lags.

This paper reviews the batch renewal process, both for LRD (long-range-dependent) traffic and for SRD (short-range-dependent) traffic in the discrete space–discrete time domain, and in the wider context of general traffic in that domain. It shows some applications of the batch renewal process in simple queues and in queueing network models. The paper concludes with open research problems and issues arising from the discussion.     

间歇过程生产调度建模的研究

生产调度是为实现某一目的而对共同使用的资源进行时间上的分配.调度中存在大量的模糊因素,将模糊的思想运用到调度领域可以帮助决策者进行有效决策.本文提出一种基于模糊规划的间歇过程生产调度建模方法及其模糊优化的新算法.应用模糊集合论的方法,在已有模糊规划模型的基础上,针对间歇生产过程,分析调度中存在的模糊信息以及出现的形式和方式,将确定型生产调度模型的约束条件和目标方程中的参数模糊化,采用非精确的量化形式,以隶属函数来表示,建立基于模糊参数的生产调度模糊线性规划模型MIFCLP.通过对一个调度问题实例进行了仿真,仿真结果证明,采用模糊模型更容易得到可行解,采用模糊线性规划解决间歇生产调度问题是一种有效方法.     

An effective neighborhood search algorithm for scheduling a flow shop of batch processing machines

This paper considers scheduling problem of flow shop with many batch processing machines and objective of maximum lateness. An effective neighborhood search algorithm (NSA) is proposed for the problem, in which a job permutation and a batch permutation are used to indicate the solution of two sub-problems, respectively. Each job permutation consists of several family-permutations for the representation of jobs from the same family. Two swaps are applied to two permutations to produce new solutions. NSA is applied to a number of instances and compared with some methods, and computational results validate the good performance of NSA.     

实时系统调度算法综述

在多道程序环境下,主存中有多个进程,其数目往往多于处理机数目。操作系统通过处理机调度程序,按照某种调度算法动态地把处理机分配给就绪队列中的一个进程,使之执行。处理机是重要的计算机资源,提高处理机的利用率及改善系统性能（吞吐量、响应时间）,很大程度上取决于处理机调度性能的好坏,因而操作系统的调度算法是非常重要的。通过研究基本的操作系统作业（进程）调度算法,详尽分析和对比这些调度算法的优势和劣势。最后对新兴的实时系统研究现状进行介绍和展望,为以后实时系统调度算法研究提供了有效的参考价值。     

Loss behavior in space priority queue with batch Markovian arrival process — discrete-time case

This paper applies matrix-analytic approach to the examination of the loss behavior of a space priority queue. In addition to the evaluation of the long-term high-priority and low-priority packet loss probabilities, we examine the bursty nature of packet losses by means of conditional statistics with respect to critical and non-critical periods that occur in an alternating manner. The critical period corresponds to having more than a certain number of packets in the buffer; non-critical corresponds to the opposite. Hence there is a threshold buffer level that splits the state space into two. By such a state-space decomposition, two hypothesized Markov chains are devised to describe the alternating renewal process. The distributions of various absorbing times in the two hypothesized Markov chains are derived to compute the average durations of the two periods and the conditional high-priority packet loss probability encountered during a critical period. These performance measures greatly assist the space priority mechanism for determining a proper threshold. The overall complexity of computing these performance measures is of the order O(K²m₁³m₂³), where K is the buffer capacity, and m₁ and m₂ are the numbers of phases of the underlying Markovian structures for the high-priority and low-priority packet arrival processes, respectively. Thus the results obtained are computationally tractable and numerical results show that, by choosing a proper threshold, a space priority queue not only can maintain the quality of service for the high-priority traffic but also can provide the near-optimum utilization of the capacity for the low-priority traffic.     

间歇精馏过程的模糊逻辑与增益自调整PID混合控制

针对间歇精馏过程的强非线性和非平稳时变特性,结合模糊逻辑控制和增益自调整PID控制的优点,提出了一种模糊逻辑和增益自调整PID混合控制的先进控制策略,详细推导了其控制算法,设计了相应的控制器,并在EuroBEEB工控机上用实时BASIC语言编程实现,对一套甲醇/水二元间歇精馏塔的塔顶浓度进行了推断控制实验,获得了比单独采用模糊逻辑控制时更好的控制结果。这说明,模糊逻辑和增益自调整PID混合控制是强非线性和非平稳时变过程的一种有效控制策略。     

分布式实时系统的容错调度算法

提出了两种分布式实时容错调度算法：副版本后调度算法（ＢＫＣＬ）及无容错需求后调度算法（ＮＦＲＬ）,并研究了算法的时间复杂度,这两种容雕工算法能同时调度具有容错需求的实时任务和无容错需求的实时任务,ＢＫＣＬ和ＮＦＲＬ所产生的调度可保证：在分布式系统中一个节点机失效的情况下,具有容错需求的实时任务仍然可在截止时间内完成,在描述了两个实时容错调度算法之后,分别证明了这两个算法的容错调度正确性。接着,阐述     

一种实时操作系统的进程优先级检索算法研究

进程调度是影响操作系统实时性的一个重要的因素,而很多主流操作系统(如:Linux)都是采用基于优先权的进程调度算法,该调度算法就是遍历就绪队列中的所有进程,找出优先级最高的进程,并交给处理器执行。通常情况下,该算法的时间复杂度为O(n),而这样的时间复杂度不能很好地满足实时系统的要求。该文将对一种新的进程优先级检索方法进行研究分析,并给出该方法时间复杂度的分析过程。