Survey of resource allocation methods for distributed manufacturing systems

Distributed manufacturing systems are more flexible in their arrangement and use of their resources. This permits a more dynamic and opportunistic allocation of manufacturing resources to work elements than is possible with today's centralized allocation systems. However, unlike solving the problem from a single solver view, there is no absolute control or tight coordination over how and when to decompose the problem, when to undertake a solution or the procedure for verifying consistency. Such activities will largely be left to the distributed entities to decide either individually or jointly. As a consequence the resulting allocations may suffer and induce myopic behaviour lacking in stability and regularity in the performance of the total system. Thus, the issues connected with solving the problem often move beyond the pure algorithmic focus of computation to include how the problem is decomposed, how or to whom it is assigned, and the organization for solving the subproblems, strategies used for resolving conflicts, the manner in which communication is conducted, etc. These issues, in fact, highlight the holistic nature of the solution and are used here as parameters to compare and contrast the approaches reported in the literature.     

Production stage allocation problem in large corporations

This paper studies a strategic-level decision problem on assigning production stages to geographically distributed subsidiaries in a large corporation so as to minimize the fixed cost and the expected value of the production/transportation costs under stochastic demands of customers. The influence of the economies and diseconomies of scale on unit production cost is considered. A nonlinear mixed integer programming model is designed for this problem. A local branching based solution method and a particle swarm optimization based solution method are developed for solving the model. Computational tests on real world data of Shanghai Volkswagen Auto Corp. are conducted. The results show that the proposed model can save about 2.5% of its revenue by comparing with the current decisions.     

A flight scheduling model for Taiwan airlines under market competitions

In this research, we develop a short-term flight scheduling model with variable market shares in order to help a Taiwan airline to solve for better fleet routes and flight schedules in today's competitive markets. The model is formulated as a non-linear mixed integer program, characterized as an NP-hard problem, which is more difficult to solve than the traditional fixed market share flight scheduling problems, often formulated as integer/mixed integer linear programs. We develop a heuristic method to efficiently solve the model. The test results, mainly using the data from a major Taiwan airline's operations, show the good performance of the model and the solution algorithm.     

Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities

This paper considers a single-machine scheduling with a position-dependent aging effect described by a power function under maintenance activities and variable maintenance duration considerations simultaneously. We examine two models of the maintenance duration in this study. The objective is to find jointly the optimal maintenance frequency, the optimal maintenance positions, and the optimal job sequences to minimize the makespan of all jobs. We provided polynomial time solution algorithms for all the studied problems.     

一种基于Hopfield模型的流水作业排序方法

根据Hopfield模型求解优化问题的原理,提出了一种用于求解流水作业排序问题的算法。计算和比较结果表明,这种算法在收敛速度和计算准确性方面可获得较好的结果。     

Intelligent scheduling model and algorithm for manufacturing

This paper puts forward an intelligent scheduling model based on Hopfield neural network and a unified algorithm for manufacturing. The energy computation function and its dynamic state equation are derived and discussed in detail about their coefficients (parameters) and steps (Delta t) in iteration towards convergence. The unified model is focused on the structure of the above function and equation, in which the goal and penalty items must be involved and meet different schedule models. The applications to different schedule mode including jobshop static scheduling, scheduling with due-date constraint or priority constraint, dynamic scheduling, and JIT (just in time) scheduling are discussed, and a series of examples with Gantt charts are illustrated.     

OMEGa: an optimistic most energy gain method for minimum energy multicasting in wireless ad hoc networks

In wireless ad hoc networks where every device runs on its own battery, the energy consumption is critical to lengthen the network lifetime. The communication among devices in the network can be categorized as unicasting and multicasting (including broadcasting). For the case of unicasting, computing the energy optimal path between the two communicating nodes is polynomially solvable by computing the shortest path. But for the case of multicasting, shortest path or minimum spanning tree does not guarantee an energy optimal communication. In this paper, we present our novel approach, Optimistic Most Energy Gain (OMEGa) method, for the minimum energy multicasting in wireless ad hoc networks. OMEGa aims at maximum utilization of Wireless Multicast Advantage (WMA), which essentially means covering more nodes by using larger energy. Both theoretical and experimental analysis shows OMEGa method performs very well. Research is partially supported by NSF and Air Force grants.     

Inter-city bus scheduling under variable market share and uncertain market demands

Bus scheduling is essential to a carrier's profitability, its level of service and its competitiveness in the market. In past research most inter-city bus scheduling models have used only the projected (or average) market share and market demand, meaning that the variations in daily passenger demand that occur in actual operations are neglected. In this research, however, we do not utilize a fixed market share and market demand. Instead, passenger choice behaviors and uncertain market demands are considered. Stochastic and robust optimizations and a passenger choice model are used to develop the models. These models are formulated as a nonlinear integer program that is characterized as NP-hard. We also develop a solution algorithm to efficiently solve the models. They are tested using data from a major Taiwan inter-city bus operation. The results show the good performance of the models and the solution algorithm.     

政府干预、资本投向与结构效率

基于不同投资形态对经济、社会与政治目标的贡献差异,研究了政府干预下的资本投向选择效应,及其导致的投资结构异化对总体效率的影响.研究发现,(1)地方政府有动机干预国企增加固定资产、股权并购和垄断资产投资,削减技术资产投资.(2)在政府干预程度较大的地区,国资委直属企业的固定资产投资规模和增速最大;企业集团所属企业的股权投...     

收入共享契约下价格歧视及配置效率分析

与供应链管理中研究收入共享契约如何实现供应链协调不同,主要研究其实现供应链协调时对上游供应商的定价行为、配置效率和社会福利的影响。研究发现: 在收入共享契约协调的供应链内,上游供应商对效率不同的下游厂商实施歧视定价,其与下游厂商生产效率、产品替代性一起影响着配置效率和社会福利,虽然收入共享契约通过实现供应链协调能够增加各厂商的总利润,但对消费者剩余的影响取决于多种因素,具有不确定性,因此对于社会总福利的影响也具有不确定性。还进一步讨论了供应链厂商之间的讨价还价能力对收入共享契约分配系数的影响,识别出影响收入共享分配系数的一些重要因素。根据分析结果认为: 收入共享契约作为纵向约束协议,对其进行反垄断审查应该适用“合理推定原则”而不是“本身违法原则”。     

Replanning the Master Production Schedule for a Capacity-Constrained Job Shop

This research examines the use of both frozen and replanning intervals for planning the master production schedule (MPS) for a capacity-constrained job shop. The results show that forecast error, demand lumpiness, setup time, planned lead time, and order size have a greater impact on the mean total backlog, total inventory, and number of setups than the frozen and replanning intervals. The study also shows that a repetitive lot dispatching rule reduces the importance of lot sizing, and a combination of repetitive lot dispatching rule and single-period order size consistently produces the lowest mean total backlog and total inventory. The results also indicate that rescheduling the open orders every period produces a lower mean total backlog and total inventory when the forecast errors are large relative to the order sizes. This result suggests that the due date of an open order should be updated only when a significant portion of the order is actually needed on the new due date.     

Solution Procedures for the Lot-Streaming Problem

Lot streaming is the process of splitting a job into sublots so its operations can be overlapped and its progress accelerated. We present a computationally efficient procedure for solving the m-machine, two-sublot problem, and we discuss the bottleneck insights that emerge from the analysis. We also examine heuristic approaches for more than two sublots and discuss computational results for these procedures.     

Production planning for remanufactured products

This paper presents a methodology for production planning within facilities involved in the remanufacture of products. Remanufacturing refers to the process of accepting inoperable units, salvaging good and repairable components from those units, and then re-assembling good units to be re-issued into service. These types of facilities are common, yet many suffer from the unpredictability of good and repairable component yields, as well as processing time variation. These problems combine to make it extremely difficult to predict whether overall production output will be sufficient to meet demand. Low yields of key components can lead to shortages which require the facility to purchase new components for legacy systems, often with long lead times, thus causing overall delays. The approach developed here is a probabilistic form of standard material requirements planning (MRP), which considers variable yield rates of good, bad, and repairable components that are harvested from incoming units, and probabilistic processing times and yields at each stage of the remanufacturing process. The approach provides estimates of the expected number of remanufactured units to be completed in each future period. In addition, we propose a procedure for generating a component purchase schedule to avoid shortages in periods with a low probability of meeting demand. The proposed methodology is applied to an antenna remanufacturing process at the Naval Surface Warfare Center (NSWC). In this case study the proposed methodology identifies a potential shortage of a key component and suggests a corrective action to avoid significant delay in the delivery of remanufactured units.     

Total energy optimal multicasting in wireless ad hoc networks

In this paper, we present our novel algorithm, SOR (Shrinking Overlapped Range), for the minimum energy multicasting in wireless ad hoc networks. The heuristics in the literature have not considered changing the intermediate tree structure and this may result in worse performance even after local improvements at the end. In SOR, we extensively change the intermediate tree structure to maintain tighter structure in terms of energy consumption. We do so by shrinking the overlapped transmission range following the idea of WMA (wireless multicast advantage) property and by allowing the selection of internal transmissions which further changes the tree structure. Both theoretical analysis and experimental results show SOR outperforms other heuristics in the literature. Research is partially supported by NSF and Air Force grants.     

An efficient scheduling algorithm for the hot coil making in the steel mini-mill

This paper investigates and suggests an efficient solution to the problem of scheduling the steel making line in the Mini Steel Mill, which consists of three major processes: molten steel making, continuous slab casting, and hot charged rolling. Careful synchronization of these processes is a key productivity factor, since a very limited amount of work-in-process inventory is allowed. Since each process must run in batch, the schedule for the Mini-Mill consists of grouping and sequencing of lots for each process. However, each process has its own criteria for judging the quality of its lot grouping, which often conflicts with other processes. An efficient scheduling algorithm for the Mini-Mill is proposed. Numerical experiments with real world data suggest that the proposed algorithm yield satisfactory schedules very efficiently. The algorithm is currently used for the actual scheduling of a Mini-Mill in Korea.     

Knowledge-based system for selection of an AGV and a workcentre for transport of a part in on-line scheduling of FMS

The operational level of flexible manufacturing systems FMS is concerned with the detailed decision making required for real-time operation. The real-time control of FMS is extremely complex. On-line scheduling is referred to as real-time control of FMS. On-line scheduling of an FMS requires decision making in various scheduling problems such as selection of an AGV and a workcentre from a set of workcentres simultaneously requesting the service for transport of a part, selection of a new part type to be released into the system, etc. This paper describes a prototype knowledge-based system for selection of an AGV and a workcentre from a set of workcentres simultaneously requesting the service for transport of a part in on-line scheduling of FMS. The knowledge-based system is evaluated by the empirical approach. On-line scheduling of FMS gives potential advantages such as productivity and low throughput time.     

Comparative evaluation of genetic algorithms for job-shop scheduling

Many optimization problems from the industrial engineering world, in particular the manufacturing systems, are very complex in nature and quite hard to solve by conventional optimization techniques. There has been increasing interest in imitating living beings to solve such kinds of hard optimization problems. Simulating the natural evolutionary process of human beings results in stochastic optimization tech niques called evolutionary algorithms, which can often outperform conventional optimization methods when applied to difficult real-world problems. There are currently three main avenues of this research: genetic algorithms (GAs), evolutionary programming (EP) and evolution strategies (ESs). Among them, genetic algorithms are perhaps the most widely known types of evolutionary algorithms today. During the past years, several GAs for the job-shop scheduling problems have been proposed, each with different chromosome representation. In this paper, the different GAs are collected from the literature and an attempt has been made to evaluate them. The benchmark problems available in open literature are used for evaluation and the performance measure considered is makespan. The algorithms are coded in C+ +.     

炼钢连铸计划调度优化系统

钢铁企业的炼钢连铸计划调度问题一直是学术界和企业界研究的热门课题.炼钢连铸生产计划调度系统是钢铁企业制造执行系统的重要组成部分,在企业的生产管理中起着承上启下的作用.本文首先简述了炼钢连铸计划调度理论的发展历程和生产工艺流程,并进一步描述了炼钢连铸计划编制的流程.针对炼钢连铸计划调度的现场要求,架构了炼钢连铸计划调度优化系统的功能模块,并较详细地说明了各功能模块的功能特点.该系统不仅能对静态调度计划应用多种优化方法进行编制,而且对复杂生产环境的各类响应事件可以做到快速响应,满足动态调度的要求,保证生产的稳定顺行.     

New high performing heuristics for minimizing makespan in permutation flowshops

The well-known NEH heuristic from Nawaz, Enscore and Ham proposed in 1983 has been recognized as the highest performing method for the permutation flowshop scheduling problem under the makespan minimization criterion. This performance lead is maintained even today when compared against contemporary and more complex heuristics as shown in recent studies. In this paper we show five new methods that outperform NEH as supported by careful statistical analyses using the well-known instances of Taillard. The proposed methods try to counter the excessive greediness of NEH by carrying out re-insertions of already inserted jobs at some points in the construction of the solution. The five proposed heuristics range from extensions that are slightly slower than NEH in most tested instances to more comprehensive methods based on local search that yield excellent results at the expense of some added computational time. Additionally, NEH has been profusely used in the flowshop scheduling literature as a seed sequence in high performing metaheuristics. We demonstrate that using some of our proposed heuristics as seeds yields better final results in comparison.     

Effect of forecast errors on rolling horizon master production schedule cost performance for various replanning intervals

Master production schedules are usually updated by the use of a rolling schedule. Previous studies on rolling schedules seem to form the consensus that frequent replanning of a master production schedule (MPS) can increase costs and schedule instability. Building on previous research on rolling schedules, this study addresses the impact of overestimation or underestimation of demand on the rolling horizon MPS cost performance for various replanning frequencies. The MPS model developed in this paper is based on actual data collected from a paint company. Results indicate that under both the forecast errors conditions investigated in this study, a two-replanning interval provided the best MPS cost performance for this company environment. However, results from the sensitivity analysis performed on the MPS model indicate that when the setup and inventory carrying costs are high, a 1-month replanning frequency (frequent replanning) seems more appropriate for both of the above forecast error scenarios.