重入排序问题综述

重入排序问题打破传统假设：工件在加工过程中不止一次地访问某台机器,是一种新型的排序问题. 重入的特点源于半导体生产, 并广泛存在于其他领域. 对重入排序问题已有文献中的成果进行梳理和分析,按问题所处机器环境的不同, 对内容和方法进行分类介绍和总结：包括单机问题、流水作业问题、混合流水作业问题及其他机器环境下的重入排序问题. 最后展望未来的趋势和研究方向.     

带强制工期的可中断单机排序问题

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了—个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序.     

极小化最大提前完工时间的两平行机排序问题

讨论了在两台同型平行机上,加工带截止期限的n个工件,在机器可空闲条件下,确定一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会无可行排序.先讨论问题的可行性,通过子集和问题归约,证明了判定问题的可行性是NP-complete的.如果问题可行,接着讨论了问题的复杂性,通过划分问题归约,证明了其是NP-complete的.最后,考虑了工件加工时间相等的特殊情形,提出了一个算法在多项式时间内获得最优排序.     

带强制工期的可中断平行机排序问题

讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.     

机器带准备时间的同类机分批排序算法

讨论了两类机器带准备时间的同类机分批排序问题.对工件无到达时间及有常数个到达时间,目标函数为极小化加权总完工时间这两类问题进行研究,给出了两个最优算法,并对算法及其计算复杂性给予了分析与证明.     

装配系统的供应链排序问题

在装配系统中,有多个供应商向同一个制造商提供零部件,仅当一个产品的所有零部件都送到后,制造商才进行最后的组装与发送.假设制造商为非瓶颈式生产.研究目标为工件带权完工时间和及最大延误的装配系统供应链排序问题,利用排序的理论和方法,分别设计多项式时间算法,并分析算法的性能比.     

一个具有退化的两个代理的排序问题

考虑两个代理的带有退化的单机排序问题.第一个代理J以完工时间和为目标函数,第二个代理J以最大延迟为目标函数,并且两个代理的加工时间是按时间退化的,所谓按时间退化就是每个工件的加工时间是其开始加工时间的函数.问题的目标是寻找一种排序,使得两个代理的目标函数之和达到最小.证明该问题可在O(n_1n_2(n_1+n_2))时间内求解.     

带调整时间的一类排序问题

进一步讨论带磨损因子的排序问题,在相应问题中对工件j,j=1,2,…,n,引入了调整时间sj,它同磨损因子bj一样同该工件何时加工无关.要求适当排列这n个工件的加工顺序,使目标函数值达最小.给出了加工全程、完工时间之和及JIT问题在引入调整时间下的最优算法.     

一个具有两类工件的多目标排序的多项式时间算法

本文考虑具有两个工件集的单机排序问题.第一个工件集J1以完工时间和为目标函数,第二个工件集J2以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得两个目标函数的加权和达到最小.本文证明该问题可在O(n1n2(n1 n2))时间内求解.     

带机器准备时间的m台平行机在线和半在线排序

本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.     

Optimal deteriorating items production inventory models with random machine breakdown and stochastic repair time

This study develops deteriorating items production inventory models with random machine breakdown and stochastic repair time. The model assumes the machine repair time is independent of the machine breakdown rate. The classical optimization technique is used to derive an optimal solution. A numerical example and sensitivity analysis are shown to illustrate the models. The stochastic repair models with uniformly distributed repair time tends to have a larger optimal total cost than the fixed repair time model, however the production up time is less than the fixed repair time model. Production and demand rate are the most sensitive parameters for the optimal production up time, and demand rate is the most sensitive parameter to the optimal total cost for the stochastic model with exponential distribution repair time.     

Travel time models for automated warehouses with aisle transferring storage and retrieval machine

This paper presents analytical travel time models for the computation of travel time for automated warehouses with the aisle transferring S/R machine (in continuation multi-aisle AS/RS). These models consider the operating characteristics of the storage and retrieval machine such as acceleration and deceleration and the maximum velocity. Assuming uniform distributed storage rack locations and pick aisles and using the probability theory, the expressions of the cumulative distribution functions with which the mean travel time is calculated, have been determined. The computational models enable the calculation of the mean travel time for the single and dual command cycles, from which the performance of multi-aisle AS/RS can be evaluated. A simulation model of multi-aisle AS/RS has been developed to compare the performances of the proposed analytical travel time models. The analyses show that regarding all examined types of multi-aisle AS/RS, the results of proposed analytical travel time models correlate with the results of simulation models of multi-aisle AS/RS.     

Time and inventory dependent optimal maintenance policies for single machine workstations: An MDP approach

In this work the problem of obtaining an optimal maintenance policy for a single-machine, single-product workstation that deteriorates over time is addressed, using Markov Decision Process (MDP) models. Two models are proposed. The decision criteria for the first model is based on the cost of performing maintenance, the cost of repairing a failed machine and the cost of holding inventory while the machine is not available for production. For the second model the cost of holding inventory is replaced by the cost of not satisfying the demand. The processing time of jobs, inter-arrival times of jobs or units of demand, and the failure times are assumed to be random. The results show that in order to make better maintenance decisions the interaction between the inventory (whether in process or final), and the number of shifts that the machine has been working without restoration, has to be taken into account. If this interaction is considered, the long-run operational costs are reduced significantly. Moreover, structural properties of the optimal policies of the models are obtained after imposing conditions on the parameters of the models and on the distribution of the lifetime of a recently restored machine.     

Pooling设计在数控机床可靠性方面的应用

利用随机pooling设计的理论和方法,建立了数控机床可靠性筛选的定量分析数学模型,在统计分析观察工作时间段的基础上,可以筛选出可靠性差的数控机床,为数控机床的改进,产品质量的提高,提供理论依据.     

A generic approach to measuring the machine flexibility of manufacturing systems

Despite extensive studies on the flexibility of manufacturing systems over the last two decades, a unified measurement approach has not been developed. To this end, we integrate two domains of machine flexibility models from the literature: operational capability-based machine flexibility and time and cost-based machine flexibility, and propose a generic model to measure machine flexibility with consideration of uncertainties in the system. Furthermore, in our approach we include part characteristics such as processing time and processing cost, the number of operations that a machine can perform, and uncertainties in demand and machine-part assignment. The resulting framework to measure machine flexibility is a two-stage model: a super efficiency Data Envelopment Analysis Model and a flexibility model. The results show that the marginal system machine flexibility does not always increase as the number of operations that a machine can perform increases, and the system machine flexibility depends on the demand uncertainty.     

Numerical study of learning algorithms on Stiefel manifold

Convex optimization methods are used for many machine learning models such as support vector machine. However, the requirement of a convex formulation can place limitations on machine learning models. In recent years, a number of machine learning methods not requiring convexity have emerged. In this paper, we study non-convex optimization problems on the Stiefel manifold in which the feasible set consists of a set of rectangular matrices with orthonormal column vectors. We present examples of non-convex optimization problems in machine learning and apply three nonlinear optimization methods for finding a local optimal solution; geometric gradient descent method, augmented Lagrangian method of multipliers, and alternating direction method of multipliers. Although the geometric gradient method is often used to solve non-convex optimization problems on the Stiefel manifold, we show that the alternating direction method of multipliers generally produces higher quality numerical solutions within a reasonable computation time.     

Optimal design of unreliable production–inventory systems with variable production rate

In this article, we study an economic manufacturing quantity (EMQ) problem for an unreliable production facility where the production rate is treated as a decision variable. As the stress condition of the machine changes with the production rate, the failure rate of the machine is assumed to be dependent on the production rate. The unit production cost is also taken as a function of the production rate, as the machine can be operated at different production rates resulting in different unit production costs. The basic EMQ model is formulated under general failure and general repair time distributions and the optimal production policy is derived for specific failure and repair time distributions viz., exponential failure and exponential repair time distributions. Considering randomness of the time to machine failure and corrective repair time, the model is extended to the case where certain safety stocks in inventory may be useful to improve service level to customers. Optimal production policies of the proposed models are derived numerically and the sensitivity of the optimal results with respect to those parameters which directly influence the machine failure and repair rates is also examined.     

Learning and forgetting effects on a group scheduling problem

This paper proposes to investigate learning and forgetting effects on the problem of scheduling families of jobs on a single machine to minimize total completion time of jobs. A setup time is incurred whenever the single machine transfers job processing from a family to another family. To analyze the impact of learning and forgetting on this group scheduling problem, we structure three basic models and make some comparisons through computational experiments. The three models, including no forgetting, total forgetting and partial forgetting, assume that the processing time of a job is dependent on its position in a schedule. Some scheduling rules and a lower bound are derived in order to constitute our branch-and-bound algorithm for searching an optimal sequence. In addition, an efficient and simply-structured heuristic is also built to find a near-optimal schedule.     

Using ARMA models to forecast workpiece roundness error in a turning operation

The paper describes the methodology for developing autoregressive moving average (ARMA) models to represent the workpiece roundness error in the machine taper turning process. The method employs a two stage approach in the determination of the AR and MA parameters of the ARMA model. It first calculates the parameters of the equivalent autoregressive model of the process, and then derives the AR and MA parameters of the ARMA model. Akaike's Information Criterion (AIC) is used to find the appropriate orders m and n of the AR and MA polynomials respectively. Recursive algorithms are developed for the on-line implementation on a laboratory turning machine. Evaluation of the effectiveness of using ARMA models in error forecasting is made using three time series obtained from the experimental machine. Analysis shows that ARMA(3,2) with forgetting factor of 0.95 gives acceptable results for this lathe turning machine.     

Clustered flow shop models

This paper deals with flow-shop models where n items are grouped in fixed sequences, called clusters. The clusters are to be processed on m machines in the same technological order. Each machine handles the clusters in the same order. Each completed item is available for processing on the next machine. The question is how to arrange the clusters to minimize the completion time. Models that include setup times for clusters with identical items are also examined. Approximate solutions along with new lower bounds are presented. Those solutions are optimal for the two machine case.