Estimating Moments of the Effective Lead Time for a Stock Control Model with Independent Normal Lead Times

In multiple sourcing, replenishment orders for one stock item may be placed at the same time with several suppliers. In order to determine the re-order level and the size of the buffer stock, we then need to estimate the mean and variance of the effective lead time, i.e. the smallest of the lead times. Previous work on this topic has assumed that the mean and variance are either known or may be estimated from large samples, but the number of observations typically available is small. This paper presents a Bayesian approach to the problem when the lead times are independent and normally distributed, although it is shown that the method may be used in more general circumstances. The computational procedures are described and illustrated with an example.     

A 3/2 Algorithm for Two-Machine Open Shop with Route-Dependent Processing Times

This paper considers the problem of minimizing the schedule length of a two-machine shop in which not only can a job be assigned any of the two possible routes, but also the processing times depend on the chosen route. This problem is known to be NP-hard. We describe a simple approximation algorithm that guarantees a worst-case performance ratio of 2. We also present some modifications to this algorithm that improve its performance and guarantee a worst-case performance ratio of 3/2.     

二台机器的流水作业中存在调整时间的LOT—STREAMING问题

对二台机器流作业中的Ｌｏｔ－Ｓｔｒｃａｍｉｎｇ问题（简称ＬＳ），以往的研究多为固定分批数寻找各批大小，或对二台机器引入相同的调整时间，寻找量优分批数及和批大小，本文对机器１，２每生产一个新的子批量分别引入一独立的调整时间Ｓ１，Ｓ２，研究同时决定最优分批数和最优分批大小，并给出相应的最优算法。     

A Heuristic for a Resource-capacitated Multi-stage Lot-sizing Problem with Lead Times

In this paper we propose a heuristic for the resource-capacitated multi-stage lot-sizing problem with general product structures, set-up costs and resource usage, work-in-process inventory costs and lead times. To facilitate the functioning of the heuristic, we use the formulation of the problem based on Echelon Stock in a rolling horizon scheme. The heuristic first obtains a reasonable solution to the corresponding uncapacitated problem and then tries to attain capacity feasibility by shifting production backwards in time. The concept of echelon stock makes the task of checking the inventory feasibility of proposed shifts easier than would be the case with conventional installation stock. The heuristic is first tested computationally for problems with a five-component product structure over a 12 period planning horizon for which optimal solutions were available and for which optimality precision guarantees were also obtained via Lagrangian Relaxation. The heuristic's performance is also explored with two different 40-component product structures, with high and low set-up costs, and is compared with the Lagrangian precision guarantees.     

A Model for Predicting the Performance of a Job Shop

This paper is concerned with presenting a method of modelling a job shop based on queueing theory. The model is very flexible and may be used to explore the relationships between the resources available in the shop (numbers and characteristics of machines, manpower levels and skills), the workload in the shop, the mode of operation of the shop (labour allocation and priority schemes) and the resulting level of congestion within the shop.A range of results is presented, based on the application of the model to a real environment, where good agreement with the observed performance was obtained.     

依赖机器的两台机自由作业排序问题

文章研究加工时间仅依赖于机器的两台机自由作业排序问题 O2 | pij = pi, p2 < p1 < 2p2, Non-Idle | ΣCj。项思明和唐国春(1998)证明了可将该问题转化成指派问题。俞文ci 和应刚(1998)给出了这一问题的显式解,并用较长的篇幅证明其显式解的正确性;他们还举例说明所给出的显式最优排序并不排除其他形式的最优解的存在;但他们未说明所给出的显式解何时才是唯一最优解。本文将给出问题 O2 | pij = pi, p2 < p1 < 2p2, Non-Idle | ΣCj的显式解的直观的最优性证明,并讨论问题显式解何时是唯一的最优解。     

Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times

In this work a new heuristic solution technique for the Resource-Constrained Project Scheduling Problem (RCPSP) is proposed. This technique is a hybrid multi-pass method that combines random sampling procedures with a backward–forward method. The impact of each component of the algorithm is evaluated through a step-wise computational analysis which in addition permits the value of their parameters to be specified. Furthermore, the performance of the new technique is evaluated against the best currently available heuristics using a well known set of instances. The results obtained point out that the new technique greatly outperforms both the heuristics and metaheuristics currently available for the RCPSP being thus competitive with the best heuristic solution techniques for this problem.     

模糊置换流水车间调度的多目标模型

为了求解同时考虑模糊加工时间和模糊交货期的多目标置换流水车间调度问题,提出一种模糊多目标调度模型。针对目标之一的最大化满意度,考虑决策者偏好,建立基于悲观准则的偏好满意度模型,并在此基础上,兼顾考虑可信度,对满意度模型进行改进;针对Pareto最优解的选取,引入模糊集理论和概率论,运用面积补偿法将最大模糊完工时间去模糊化,便于可行解之间进行比较。最后,采用随机系列算例以及典型算例进行优化计算,计算结果验证了模型的有效性。     

A Note on Exact Moment Computation for Normal Lead Times in the Two-Supplier Case

In the stochastic lead time inventory model with two suppliers and different normal lead times, the mean and variance of the lead-time demand distribution are traditionally computed using numerical integration. Tables are made available to help practitioners determine the minimum size of replenishments when orders to the suppliers are placed at the same time. This paper presents closed-form solutions to evaluate the required quantities of interest and tries to correct some mistakes in the existing tables. The expressions given here may also provide insight into the choice of sole versus dual suppliers.     

A Markov Type Model for Systems with Tolerable Down Times

This paper provides a modelling framework for the use of non-homogeneous Markovian techniques for components and systems, where the sojourn time at a state, or a class of states, may be limited by a given value. This approach is useful, for example, to build component models with constant repair times, and to model systems or components with tolerable down times. Tolerable down time models have appeared in the field of Boolean techniques for 10 years. A systematic Markovian approach applied to systems composed of several components, allows the interdependencies among the components to be precisely treated, which may cause large conservativeness, if the Boolean modelling technique is applied.     

A Linear Model for Estimating Project Resource Levels and Target Completion Times

Selecting target completion time and appropriate resource availabilities for projects is not easy. In this paper a simple relationship is established to aid the planner in this task. The relationship is based on experiments involving 4942 different network/resource configurations. The relationship can be used to select the best balance between the cost of over-runs and the cost of resources.     

An Enhanced TSP-Based Heuristic for Makespan Minimization in a Flow Shop with Setup Times

This paper presents an enhanced heuristic for minimizing the makespan of the flow shop scheduling problem with sequence-dependent setup times. The procedure transforms an instance of the problem into an instance of the traveling salesman problem by introducing a cost function that penalizes for both large setup times and bad fitness of schedule. This hybrid cost function is an improvement over earlier approaches that penalized for setup times only, ignoring the flow shop aspect of the problem. To establish good parameter values, each component of the heuristic was evaluated computationally over a wide range of problem instances. In the testing stage, an experimental comparison with a greedy randomized adaptive search procedure revealed the conditions and data attributes where the proposed procedure works best.     

Stock Control with Two Suppliers and Normal Lead Times

This paper helps practitioners to compute the mean and variance of the lead time demand distribution when two suppliers are used simultaneously to replenish stock of a single item. The lead times of each supplier are assumed to be normally distributed and two replenishment orders are placed, one with each supplier, at the same time. The results indicate that the reorder level required to give a specific probability of no stock-out during replenishment is lower when using two suppliers simultaneously. Tables have also been prepared to help practitioners determine the minimum sizes of replenishment orders when two suppliers are used and replenishment orders are placed at the same time.     

Inventory Control with Normal Demand and Gamma Lead Times

An exact expression for protection and potential lost sales is obtained for a reorder level system of inventory control in which the demand is normally distributed and the lead time gamma distributed. The accuracy of an approximate method is explored.     

机器具有优势关系下的工件加工时间可控的流水作业排序问题

本文主要研究机器具有优势关系下的工件加工时间可控的流水作业排序问题.我们主要对以下两种情形进行了讨论:工件加工时间为线性恶化和线性学习.对于每一种加工模型,我们分别研究了几类不同的优势机器,并且对每种情况均给出了多项式时间算法.     

The Significance of Correlated Demands and Variable Lead Times for Stock Control Policies

The current assumptions in stock control policies of independent demands and constant lead times are relaxed to include the case of first order autoregressive demand patterns and three different distributions of lead time. It is shown that where there is negative serial correlation, assumption of independence might lead to over provision of stock, whereas in cases of positive correlation the under provision will be very significant. This is aggravated as the expected lead time increases. These effects are illustrated by some numerical results.     

Lot Streaming in a Two-stage Flow Shop with Set-up,Processing and Removal Times Separated

This paper considers the job (lot) scheduling problem for two-stage flow shops in which the movement of transfer batches (sublots) from the first stage to the next are allowed. Set-up, processing and removal times are considered as separable and independent of the order in which jobs are processed at any of two stages. An optimal transfer batch sizing and scheduling algorithm which has an objective of minimizing the maximum flow time (makespan) is developed and demonstrated by a numerical example.     

遗传算法对车间作业调度的研究

应用遗传算法对车间作业调度问题进行研究,针对ＪＳＳＰ的具体特性,文中提出变异函数和二次编码的思想,获得较好的仿真结果。     

A Rollout Metaheuristic for Job Shop Scheduling Problems

In this paper we deal with solution algorithms for a general formulation of the job shop problem, called alternative graph. We study in particular the job shop scheduling problem with blocking and/or no-wait constraints. Most of the key properties developed for solving the job shop problem with infinite capacity buffer do not hold in the more general alternative graph model. In this paper we report on an extensive study on the applicability of a metaheuristic approach, called rollout or pilot method. Its basic idea is a look-ahead strategy, guided by one or more subheuristics, called pilot heuristics. Our results indicate that this method is competitive and very promising for solving complex scheduling problems.     

加权完工时间和的调整时间可分离Flow shop排序问题

讨论了2台机器调整时间可分离的FlowShop排序问题,目标函数为极小化加权完工时间和.给出了对于一种特殊情况,问题存在多项式最优算法的充分条件.接着又给出了求解该问题的一个分枝定界法.