Open shops with jobs overlap––revisited

In this communication we consider a two machine open shop in which a job requires processing on both machines. However, in contrast to the classical open shop, the two operations of any given job may overlap in time. The objective function under consideration is the minimization of the total completion time. This model has been considered before by Wagneur and Sriskandarajah [Eur. J. Oper. Res. 71 (1993) 366] and they presented a proof showing that minimizing the total completion time in a two machine open shop with jobs overlap is strongly NP-hard. Their proof is based on a reduction of the numerical matching with target sums (NMTS) problem; however, their proof is unfortunately not correct. In this communication we provide a counterexample that shows that their reduction does not hold. Our counterexample implies that the complexity status of the two machine open shop with job overlap remains open.     

An iterated greedy metaheuristic for the blocking job shop scheduling problem

In this paper we consider a job shop scheduling problem with blocking (BJSS) constraints. Blocking constraints model the absence of buffers (zero buffer), whereas in the traditional job shop scheduling model buffers have infinite capacity. There are two known variants of this problem, namely the blocking job shop scheduling with swap allowed (BWS) and the one with no swap allowed (BNS). This scheduling problem is receiving an increasing interest in the recent literature, and we propose an Iterated Greedy (IG) algorithm to solve both variants of the problem. IG is a metaheuristic based on the repetition of a destruction phase, which removes part of the solution, and a construction phase, in which a new solution is obtained by applying an underlying greedy algorithm starting from the partial solution. A comparison with recent published results shows that the iterated greedy algorithm outperforms other state-of-the-art algorithms on benchmark instances. Moreover it is conceptually easy to implement and has a broad applicability to other constrained scheduling problems.     

基于Ordered-Probit模型对淘宝网店的综合分级评价

整理自作者2015年第四届全国大学生统计建模大赛市场调查类研究生组一等奖获奖论文.通过聚类分析、层次分析,给出从淘宝网上抽取样本网店的综合评级,并以此评价结果建立对淘宝网店进行综合分级评价的Ordered-Probit模型.     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

Lead time selection and the behaviour of work flow in job shops

Few studies in job shop scheduling consider dynamic shop load and work flow issues. However, these issues are of importance to management responsible for shop floor control. This research investigates relevant internal performance measures and their relationship to external measures. As well, a new dispatching mechanism that seeks to even out the distribution of jobs in queue is investigated. Results show that a shop load balance index, which takes both shop load levels and load variability into account, has a very strong relationship to the lead times required to maintain a desired level of delivery performance. It appears that good performance based on internal measures is consistent with good performance based on external measures.     

Manufacturing lead time estimation using data mining

We explore use of data mining for lead time estimation in make-to-order manufacturing. The regression tree approach is chosen as the specific data mining method. Training and test data are generated from variations of a job shop simulation model. Starting with a large set of job and shop attributes, a reasonably small subset is selected based on their contribution to estimation performance. Data mining with the selected attributes is compared with linear regression and three other lead time estimation methods from the literature. Empirical results indicate that our data mining approach coupled with the attribute selection scheme outperforms these methods.     

Heuristic and stochastic methods in optimization

The shifting bottleneck (SB) heuristic is among the most successful approximation methods for solving the job shop problem. It is essentially a machine based decomposition procedure where a series of one machine sequencing problems (OMSPs) are solved. However, such a procedure has been reported to be highly ineffective for the flow shop problems. In particular, we show that for the 2-machine flow shop problem, the SB heuristic will deliver the optimal solution in only a small number of instances. We examine the reason behind the failure of the machine based decomposition method for the flow shop. An optimal machine based decomposition procedure is formulated for the 2-machine flow shop, the time complexity of which is worse than that of the celebrated Johnson’s rule. The contribution of the present study lies in showing that the same machine based decomposition procedures which are so successful in solving complex job shops can also be suitably modified to optimally solve the simpler flow shops.     

基于排队论的内场维修设备数量确定方法

在内场车间维修设备配置研究中,为了科学合理地确定维修设备数量需求,运用排队论的基本方法,结合飞机内场维修工作特点,提出了基于排队论的内场维修设备数量确定方法,构建了相应的数量确定模型,结合实例验证了该方法可行有效.结果表明方法可以提高飞机基层级内场车间维修设备数量确定的准确性.     

考虑机器能耗的绿色作业车间调度问题

针对传统作业车间调度,在保证交货期的前提下,以机器能耗最小为目标研究带有关机/重启策略的绿色车间调度问题。首先建立数学规划模型,然后在遗传算法的框架下,根据问题特点提出了一种局部调整的解码方式,在排产时进行工序的移动并确定其开始加工时刻。最后进行小规模算例运算,验证数学规划模型的有效性,再利用算例对基于局部调整解码和顺序解码的遗传算法进行对比测试,结果表明提出的局部调整解码可以在降低机器能耗的同时提高求解效率。     

A Model for Shop Makespans and Lead Times

A model has been constructed which enables a component manufacturing shop to be interactively defined at a V.D.U., and used to calculate the average job makespan (time taken on the shop) under a variety of assumptions relating to work content, capacity and operational procedures. A second phase of the model allows the production controller to define a scheduling technique and lead-time assignment method, and provides guidance on how the makespan should be converted to lead times (time allowed on the shop). The model uses a mixture of queueing theory and simulation. This paper principally describes the methodology, but uses of the model are briefly discussed.     

考虑序列设置时间的混合流水车间多目标调度研究

基于混合流水车间多品种的特性,序列设置时间和工序跳跃是很多车间在调度时需要考虑的两个重要问题,论文充分考虑这两种生产约束,建立了以最大完工时间和负荷均衡指标为双目标的混合流水车间多目标调度数学模型,并运用改进的NSGA-II算法对基于实际企业生产数据假设的算例进行仿真求解,结果表明求解的调度方案符合实际需求,能够为企业的实际调度提供有效的方案。     

Analysis of Job Flow-Time in a Job Shop

This paper is concerned with analytical determination of the mean and standard deviation of the job flow-time in a job shop in which the F.C.F.S. dispatching rule is in use. A hypothetical job shop is constructed to generate simulation results for comparison with the analytical results. Consistency of the results reveals the validity of the analytical model. It is also shown that the model is quite robust at a low level of shop load. So the model can be applied to analyze certain types of actual shops.     

改进的混合算法求解车间作业调度问题

车间作业调度问题是个典型的NP-hard问题,为了更有效的解决车间作业调度问题,提出了一种改进的混合算法(IGASA).算法设计了一种基于当前最优解的免疫算子,算子对当前最优个体中选取运行时间最少的一台机器上的工件顺序当作疫苗,并用车间调度问题的图论模型解释了此算子的合理性.最后通过大量实验证明改进的混合算法的性能的优越性,从而证明设计的免疫算子是有意义的.     

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

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

A Simulation Study of Due-date Assignment Rules in a Dynamic Job Shop

This paper is a report of a simulation study that investigates a dynamic approach to scheduling jobs in a multi-machine job shop. The workload information of a job is used in different forms to evaluate the shop performance based on three measures: mean job lateness, percentage of tardy jobs and lateness variance. Different combinations of due-date assignment methods and sequencing rules are compared based on specific performance criteria. The results indicate that using the cumulative distribution function of workload information can yield a better performance than using a proportional function of workload information or ignoring shop congestion information. A few situations are identified in which workload information is not critical.     

Flow shop scheduling with heterogeneous workers

We propose an extension to the flow shop scheduling problem named Heterogeneous Flow Shop Scheduling Problem (Het-FSSP), where two simultaneous issues have to be resolved: finding the best worker assignment to the workstations, and solving the corresponding scheduling problem. This problem is motivated by Sheltered Work centers for Disabled, whose main objective is the labor integration of persons with disabilities, an important aim not only for these centers but for any company desiring to overcome the traditional standardized vision of the workforce. In such a scenario the goal is to maintain high productivity levels by minimizing the maximum completion time, while respecting the diverse capabilities and paces of the heterogeneous workers, which increases the complexity of finding an optimal schedule. We present a mathematical model that extends a flow shop model to admit a heterogeneous worker assignment, and propose a heuristic based on scatter search and path relinking to solve the problem. Computational results show that this approach finds good solutions within a short time, providing the production managers with practical approaches for this combined assignment and scheduling problem.     

Examination of flexibility acquisition policies in dual resource constrained job shops with simultaneous worker learning and forgetting effects

This study investigates worker training related issues in dual resource constrained (DRC)job shop environments with the simultaneous presence of learning, forgetting (which causes relearning) and worker attrition effects. Learning and forgetting occurs as workers are trained in different departments on the shop floor. A recent survey of job shops based in the US indicates that firms are concerned about the relearning losses that accompany worker transfers, and are using a variety of strategies to reduce the effects of relearning. This study uses the learn-forget-learn (LFL) model to capture different learning and forgetting environments in order to understand whether up-front training can be used to reduce relearning and realize the benefits of worker flexibility. Results show that the existing forgetting rate has a significant impact on inventory and customer service performance. Extensive up-front training helps reduce relearning, however, it does not always help improve performance.     

A Lot-sizing Model for Just-in-time Manufacturing

We consider the problem of determining lot sizes of multiple items that are manufactured by a single capacitated facility. The manufacturing facility may represent a bottleneck processing activity on the shop floor or a storeroom that provides components to the shop floor. Items flow from the facility to a downstream facility, where they are assembled according to a specified mix. Just-in-time (JIT) manufacturing requires a balanced flow of items, in the proper mix, between successive facilities. Our model determines lot sizes of the various items based on available capacity and four attributes of each item: demand rate, holding cost, set-up time and processing time. Holding costs for each item accrue until the appropriate mix of items is available for shipment downstream. We develop a lot-sizing heuristic that minimizes total holding cost per time unit over all items, subject to capacity availability and the required mix of items.     

基于遗传算法的多目标柔性工作车间调度问题求解

本文针对柔性工作车间调度问题给出了一个有意义的综合目标尽可能缩短制造周期的同时尽可能的减少机器负荷。由于传统遗传算法在多目标柔性工作车间调度问题上的局限性，我们提出了一种改进遗传算法：首先，我们给出了针对综合目标的工序调度算法获得初始集合；接着，针对柔性工作车间调度问题的特点，我们在常用的基于工序顺序的编码方法上融入了基于机器分配的编码方法，并据此设计了相应的交叉变异操作；最后借鉴了物种进化现象中的环境迁移思想设计了解决多目标优化问题的迁移操作。实验结果表明，改进的遗传算法在多目标柔性工作车间调度问题的解决上要优于传统遗传算法。     

Unit Load Size Determination Based on Economic Move Quantity

Material handling in job shop environments is accomplished through the transfer of parts between work centres. Parts that are grouped together prior to transfer form a unit load. A new method is proposed for determining the unit load size, called the economic move quantity (EMQ), based on cost considerations during the design phase of the production system. EMQ takes into account system performance through the use of a queueing network model.