等待时间受限的置换流水车间调度启发式算法

针对等待时间受限的置换流水车间调度问题,分析了其可行解与流水车间调度最优解的关系,给出了计算最大完工时间的有向图,证明了等待时间受限的置换流水车间调度问题的可逆性,并以此为基础提出了一种启发式算法.算法首先根据等待时间受限约束与无等待(no-wait)约束的相似特征,生成初始工件序列集;然后利用问题可逆性给出了复杂度为O(n2m)的插入优化机制,进一步优化初始解.数据实验的结果验证了启发式算法的可行性和有效性.     

等待时间受限的置换流水车间调度启发式算法

为了繁荣发展哲学社会科学,推动我国学术期刊加强自身建设,提高学术水平,扩大学术影响,全国哲学社会科学规划办公室自2011年启动国家社会科学基金学术期刊资助项目,入选期刊每年资助40万元。2011年和2012年各有100种期刊获得资助,《管理科学》杂志获得国家社会科学基金第二批学术期刊资助。     

Decomposition algorithms for the integrated process planning and scheduling problem

There are several algorithms to solve the integrated process planning and scheduling (IPPS) problem (i.e., flexible job shop scheduling with process plan flexibility) in the literature. All the existing algorithms for IPPS are heuristic-based search methods and no research has investigated the use of exact solution methods for this problem. We develop several decomposition approaches based on the logic-based Benders decomposition (LBBD) algorithm. Our LBBD algorithm allows us to partition the decision variables in the IPPS problem into two models, master-problem and sub-problem. The master-problem determines process plan and operation-machine assignment, while the sub-problem optimizes sequencing and scheduling decisions. To achieve faster convergence, we develop two relaxations for the optimal makespan objective function and incorporate them into the master-problem. We analyze the performance and further enhance the algorithm with two ideas, a Benders optimality cut based on the critical path and a faster heuristic way to solve the sub-problem. 16 standard benchmark instances available in the literature are solved to evaluate and compare the performances of our algorithms with those of the state-of-the-art methods in the literature. The proposed algorithm either results in the optimal solution or improves the best-known solutions in all the existing instances, demonstrating its superiority to the existing state-of-the-art methods in literature.     

An integrated strategy for a production planning and warehouse layout problem: Modeling and solution approaches

We study a real-world production warehousing case, where the company always faces the challenge to find available space for its products and to manage the items in the warehouse. To resolve the problem, an integrated strategy that combines warehouse layout with the capacitated lot-sizing problem is presented, which have been traditionally treated separately in the existing literature. We develop a mixed integer linear programming model to formulate the integrated optimization problem with the objective of minimizing the total cost of production and warehouse operations. The problem with real data is a large-scale instance that is beyond the capability of optimization solvers. A novel Lagrangian relax-and-fix heuristic approach and its variants are proposed to solve the large-scale problem. The preliminary numerical results from the heuristic approaches are reported.     

Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N ² + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N ³) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal solution.     

A disaggregation problem for a multiplant,multiproduct scheduling application

Abstract

This paper discusses an integer programming technique for planning production when there are multiple plants involved in the production of a number of products and the plants are relatively close. This allows for the closing of one plant during a planning period with a shift of the mobile resources, mainly labour, to other plants. The model is introduced and then an example problem is given. Finally, there is a discussion of why this method improves upon other techniques proposed to solve this problem. Some actual case studies are cited.     

A multi-objective particle swarm for a flow shop scheduling problem

Flow shop problems as a typical manufacturing challenge have gained wide attention in academic fields. In this paper, we consider a bi-criteria permutation flow shop scheduling problem, where weighted mean completion time and weighted mean tardiness are to be minimized simultaneously. Since a flow shop scheduling problem has been proved to be NP-hard in strong sense, an effective multi-objective particle swarm (MOPS), exploiting a new concept of the Ideal Point and a new approach to specify the superior particle's position vector in the swarm, is designed and used for finding locally Pareto-optimal frontier of the problem. To prove the efficiency of the proposed algorithm, various test problems are solved and the reliability of the proposed algorithm, based on some comparison metrics, is compared with a distinguished multi-objective genetic algorithm, i.e. SPEA-II. The computational results show that the proposed MOPS performs better than the genetic algorithm, especially for the large-sized problems.     

An intelligent workstation controller for integrated planning and scheduling of FMS cell

This paper presents an experimental design developed to determine a combination of robust planning and scheduling rules for an intelligent workstation controller (IWC). The IWC is used as part of the control system for an automated flexible manufacturing system. A three-level hierarchical control structure (shop, workstation and equipment)is adopted in order effectively to control a shop-floor. At the top level is a shop controller which receives orders and their associated manufacturing information, and manages interactions among workstations. The IWC defines and resolves the production control activities necessary to coordinate a group of equipment controllers so as to ensure the completion of orders. Specifically, the IWC is responsible for selecting a specific process routeing for each part, allocating resources, scheduling and coordinating the activities across the equipment, monitoring the progress of activities, detecting and recovering from errors, and preparing reports. These activities are accomplished using planning, scheduling, and execution functions. In order to demonstrate the effectiveness and robustness of the IWC, all the controllable and uncontrollable factors need to be identified and detailed. Controllable factors are those which are set by the controller and cannot be directly affected by the production environment. Uncontrollable factors are those which vary with the production environment and cannot be directly changed by the controller developer. The objective of the paper is to illustrate how a good set of controllable factors that dictate the IWC's effectiveness and robustness over various uncontrollable factors can be determined. Due to the number of possible combinations of all the factors, a complete validation of the effectiveness and robustness of the IWC is extremely time consuming and far beyond the scope of this paper. Therefore, a few planning and scheduling strategies are selected and a formal experiment is conducted. The experiment illustrates how significant performance dependencies for various planning and scheduling strategies can be identified.     

A harmony search-based memetic optimization model for integrated production and transportation scheduling in MTO manufacturing

This paper investigates an integrated production and transportation scheduling problem in an MTO supply chain. A harmony search-based memetic optimization model is developed to handle this problem, in which certain heuristic procedures are proposed to convert the investigated problem into an order assignment problem. A novel improvisation process is also proposed to improve the optimum-seeking performance. The effectiveness of the proposed model is validated by numerical experiments. The experimental results show that (1) the proposed model can solve the investigated problem effectively and that (2) the proposed memetic optimization process exhibits better optimum-seeking performance than genetic algorithm-based and traditional memetic optimization processes.     

A comparative analysis of two different approaches to scheduling in flexible flow shops

This work is an investigation about the relative effectiveness of two approaches to scheduling in flexible flow shops: one approach advocating the possible use of different dispatching rules at different stages of the flow shop, and the other suggesting the use of the same dispatching rule at all the stages of the flow shop. In the latter approach, the dispatching rule contains the information related to both process time and duedate. Both approaches aim at the minimization of measures related to flowtime and tardiness of jobs. This paper essentially is an attempt at exploring the relative effectiveness of these two approaches to scheduling.     

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.     

Approaches to solve the fleet-assignment,aircraft-routing,crew-pairing and crew-rostering problems of a regional carrier

This paper presents the results of a research project funded by a regional carrier operating inter-island services within the Canary Islands (Spain) in addition to services to Morocco and Portugal. It operates between 100 and 150 flights a day using three airline operators. The main scope of the project was to solve fleet-assignment, aircraft-routing, crew-pairing and crew-rostering problems on real-world data. The special characteristics of the carrier, flying between 7 am and 11 pm every day, have motivated us to design models and algorithms that are different than the ones addressed in the literature, typically built for large airline companies. This paper shows a solution approach for an integrated fleet-assignment, aircraft-routing and crew-pairing problem covering the flights of a single day. This is a new combinatorial problem that can be considered as a 2-depot vehicle routing problem with driver changes, where the vehicles represent aircrafts and the drivers represent crews. Adapting approaches from the vehicle routing literature, this paper describes a heuristic algorithm based on an integer programming model. In a similar way, this paper also addresses the rostering problem. This problem can be decomposed in smaller problems taking into account operators, bases and crew groups. These problems admit a compact formulation through mixed integer linear programming models which can be tracked by modern general-purpose solvers. This paper illustrates the success of our solution approaches on real-world instances. The airline carrier is currently using these approaches.     

Optimal and Heuristic Models for Lot Splitting in a Flow Shop

This paper investigates optimal lot-splitting policies in a multiprocess flow shop environment with the objective of minimizing either mean flow time or makespan. Using a quadratic programming approach to the mean flow time problem, we determine the optimal way of splitting a job into smaller sublots under various setup times to run time ratios, number of machines in the flow shop, and number of allowed sublots. Our results come from a deterministic flow shop environment, but also provide insights into the repetitive lots scheme using equal lot splits for job shop scheduling in a stochastic environment. We indicate those conditions in which managers should implement the repetitive lots scheme and where other lot-splitting schemes should work better.     

A note on the complexity of the problem of two-agent scheduling on a single machine

We consider a two-agent scheduling problem on a single machine, where the objective is to minimize the total completion time of the first agent with the restriction that the number of tardy jobs of the second agent cannot exceed a given number. It is reported in the literature that the complexity of this problem is still open. We show in this paper that this problem is NP-hard under high multiplicity encoding and can be solved in pseudo-polynomial time under binary encoding. When the first agent's objective is to minimize the total weighted completion time, we show that the problem is strongly NP-hard even when the number of tardy jobs of the second agent is restricted to be zero.     

A model for an integrated manufacturing system implementation in China: a case study

This paper describes a process which a company adopted to enhance her manufacturing system in a step-by-step manner. In order to increase the competitiveness of the company, the authors have identified a number of improvement strategies which were specific to the economic and political environment in China. The center of the strategies is a vision of an integrated manufacturing strategy. The detailed design and implementation of this vision is conducted through the proposed systematic manufacturing strategic analysis. The integration process encompasses various elements such as Total Quality Management (TQM), Manufacturing Resources Planning (MRPII) and Real-Time Monitoring System (RTMS), it emphasises not only the use of appropriate modern technology but also the management of technology change. In this paper, a concept model is used to describe the integration process, the detailed implementation is also elaborated using a proposed implementation process model. By adopting the integrated manufacturing system, and through continuing improvement, the productivity and hence the profitability of the company is increased. It is anticipated that the integrated approach to the design and implementation of manufacturing systems will be an important contribution towards the manufacturing strategy in a labour intensive environment such as China.     

Heuristic Estimation of the Efficient Frontier for a Bi-Criteria Scheduling Problem

We examine a single-machine scheduling problem where the objective is to minimize the mean and the variance of the job completion times simultaneously. We seek to identify the efficient frontier which is obtained by parametrically solving a weighted combination of the two criteria. The identification of the true efficient frontier for this problem is notoriously difficult. To estimate the frontier, we propose a heuristic procedure which is quite general and can be applied to other bi-criteria problems as well. It involves repeated applications of a relatively new technique called beam search in an adaptive manner. To evaluate the proposed procedure, we introduce two measures of performance and conduct a computational study. The results of the study indicate that the procedure is highly effective.     

Design and implementation of an integrated production planning system for a pharmaceutical manufacturing concern in India

SmithKline Beecham (SBPI) is a major player in the Indian pharmaceutical industry. Though relatively small in terms of turnover, it has performed Pharmaceuticals (India) exceptionally well in terms ofprofitability and growth rate. The firm has substantial cash reserves. However, the firm operates in 'mass production' mode at present, with the established finished goods inventory norms being in the range of 1 to 1.5 months. Competitive pressure on the firm is now forcing it to move towards world class manufacturing and the application of concepts from MRP II, JIT and OPT is under consideration. This paper describes the considerations that went into the justification, design and implementation of an integrated production planning and control system in this situaion.     

Evaluation of heuristics for scheduling in a flowshop: a case study

The problem of finding the best permutation schedule for a flowshop has engaged the attention of researchers for almost four decades. In view of its NP-completeness, the problem is not amenable to the development of efficient optimizing algorithms. A number of heuristics have been proposed, most of which have been evaluated by using randomly generated problems for a single measure of performance. However, real-life problems often have more than one objective. This paper discusses a live flowshop problem that has the twin objectives of minimizing the production run-time as well as the total flowtime of jobs. Five heuristics are evaluated in this study and some interesting findings are reported.