A heuristic model for the sequence-dependent lot scheduling problem

This paper presents a heuristic algorithm for finding a good solution for the sequence-dependent lot scheduling problem. Unlike available methods, the algorithm eliminates the need for creating new artificial problems and implementing feasibility tests. It also eliminates the tedious task of translating setup relationships into a mathematical programming formulation. The result is a conceptually simple solution technique that is practically motivated and easily implemented for use on the shop floor. Comparison of algorithm performance with published results demonstrates the efficacy of the approach.     

Route‐Independent Analysis of Available Capacity in Flexible Manufacturing Systems

In a job shop, because of large setup times, each operation is assigned to only one machine. There is no alternative routing. In a flexible manufacturing system, each manufacturing operation can often be performed on several machines. Therefore, with automated equipment, the capacity of a machine to perform certain operations is not independent of the capacity of other machines. Often, however, operations managers can use a route‐independent answer to production planning questions. For example, how much can be produced of a certain part type and when are important capacity questions in business negotiations, when the detailed routing and scheduling are not yet of interest or cannot be known. This paper provides a mathematical model for the route‐independent analysis of the capacity of flexible manufacturing systems based on a concept of operation types. An example is provided both to illustrate the use of operation types and to highlight the differences between the traditional route‐dependent and the proposed route‐independent formulations of capacity constraints. Some computational results are also given. Finally, a sensitivity analysis is developed to analyze the feasibility of production plans when production requirements and machine capacities can change.     

Flexible home care scheduling

Home care services are in high demand given how they are steadily becoming the primary source of care for the elderly. Powerful decision support tools are indispensable for effectively managing available staff in the context of ever-increasing demand for care and limited caregiver availability. This paper advances home care literature by introducing flexible task durations, thereby enabling tasks to be completed faster and ultimately more care to be scheduled. This new concept, which originates from practice, introduces an additional decision to be made when creating a schedule, thereby greatly increasing the scheduling complexity. Consequently, this paper introduces a new optimization-based decision support model which allows for scheduling with flexible task duration, as well as other types of flexibility. A computational study quantifies the impact of: (i) scheduling with a finer task granularity thereby enabling accurate prioritization of high and low priority care, (ii) flexibility in task duration enabling tasks to be completed faster and more care to be scheduled, and (iii) increasing the number of different locations visited by a caregiver thereby enabling a trade-off between the number of serviced clients and caregiver workload. A new publicly available real-world data set is used, obtained directly from home care organizations operating in Flanders. Analysis of the computational results demonstrates that significant improvements in operational efficiency may be realized with minimal effort required by organizations. Furthermore, the proposed algorithm’s performance is confirmed by comparison against the bounds obtained by solving an integer programming formulation of the problem. Finally, a management policy scheme is proposed which, when gradually implemented in a home care organization, results in a more efficient and therefore cost-effective deployment of its workforce.     

Design Principles for Flexible Systems

A fundamental aspect of designing systems with dedicated servers is identifying and improving the system bottlenecks. We extend the concept of a bottleneck to networks with heterogeneous, flexible servers. In contrast with a network with dedicated servers, the bottlenecks are not a priori obvious, but can be determined by solving a number of linear programming problems. Unlike the dedicated server case, we find that a bottleneck may span several nodes in the network. We then identify some characteristics of desirable flexibility structures. In particular, the chosen flexibility structure should not only achieve the maximal possible capacity (corresponding to full server flexibility), but should also have the feature that the entire network is the (unique) system bottleneck. The reason is that it is then possible to shift capacity between arbitrary nodes in the network, allowing the network to cope with demand fluctuations. Finally, we specify when certain flexibility structures (in particular chaining, targeted flexibility, and the “N” and “W” structures from the call center literature) possess these desirable characteristics.     

A heuristic approach for component scheduling on a high-speed PCB assembly machine

The collect-and-place machine is one of the most widely used placement machines for assembling electronic components on the printed circuit boards (PCBs). Nevertheless, the number of researches concerning the optimisation of the machine performance is very few. This motivates us to study the component scheduling problem for this type of machine with the objective of minimising the total assembly time. The component scheduling problem is an integration of the component sequencing problem, that is, the sequencing of component placements; and the feeder arrangement problem, that is, the assignment of component types to feeders. To solve the component scheduling problem efficiently, a hybrid genetic algorithm is developed in this paper. A numerical example is used to compare the performance of the algorithm with different component grouping approaches and different population sizes.     

SIRALINA: efficient two-steps heuristic for storage optimisation in single period task scheduling

In this paper, we study the general problem of one-dimensional periodic task scheduling under storage requirement, irrespective of machine constraints. We have already presented in (Touati and Eisenbeis, Parallel Process. Lett. 14(2):287–313, 2004) a theoretical framework that allows an optimal optimisation of periodic storage requirement in a cyclic schedule. Since our optimisation problem is NP-hard (Touati, PhD thesis, 2002), solving an exact integer linear programming formulation is too expensive in practice. In this article, we propose an efficient two-steps heuristic using model’s properties that allows fast computation times while providing highly satisfactory results. This method includes the solution of an integer linear program with a totally unimodular constraints matrix in first step, then the solution of a linear assignment problem. Our heuristic is implemented for an industrial compiler for embedded VLIW processors.     

A heuristic approach to n/ m job shop scheduling: fuzzy dynamic scheduling algorithms

n/m shop scheduling is a ‘ NP-Hard’ problem. Using conventional heuristic algorithms ( priority rules) only, it is almost impossible to achieve an optimal solution. Research has been carried out to improve the heuristic algorithms to give a near-optimal solution. This paper advocates a fuzzy logic based, dynamic scheduling algoridim aimed at achieving this goal. The concept of new membership functions is discussed in die algorithm as a link to connect several priority rules. The constraints to determine the membership function of jobs for a particular priority rule are established, and three membership functions are developed. In order to decide the weight vector of priority rules, an aggregate performance measure is suggested. The methodology for constructing the weight vector is discussed in detail. Experiments have been carried out using a simulation technique to validate the proposed scheduling algorithm.     

柔性制造系统中的结构柔性

根据柔性制造系统中生产线的结构特性,本文在考虑机器具有不同生产能力的情形下,提出了生产线结构柔性定义以及测度方法.在此基础上,本文提出了处理柔性能力扩充问题的近似规则.仿真结果表明了本文提出的结构柔性的定义以及近似规则的合理性,并对处理柔性扩充能力问题提供了有效的指导,具有理论意义以及实践价值.     

An exchange heuristic for resource constrained scheduling with consideration given to opportunities for parallel processing

This paper describes a heuristic which produces efficient makespans for resource-constrained scheduling problems with parallel processing capabilities. This heuristic was initially developed for the scheduling of army battalion training exercises. The original heuristic has also been successfully applied to solve problems in project scheduling with limited resources, generalized job shop scheduling, and resource-constrained scheduling. The exchange heuristic requires an initial feasible solution upon which it improves the makespan by efficiently and systematically shuffling activities while maintaining feasibility. The method has recently been modified twice, termed the intelligent version and naive version, respectively, such that its ability to reduce the initial makespan is enhanced. In this study     

A Flexible Evaluative Framework for Order Picking Systems

This paper develops a novel framework to evaluate the integral performance of order picking systems with different combinations of storage and order picking policies. The warehousing literature on order picking mostly considers minimizing either elapsed time or distance as the sole objective, whereas warehouse managers in a supply chain have to look beyond single‐dimensional performance and consider trade‐offs among different criteria. Thus managers still need a unified and efficient framework to select a portfolio of appropriate order picking policies from a multi‐criteria and contextual perspective. Our framework—combining data envelopment analysis, ranking and selection, and multiple comparisons—provides an efficient methodology to simultaneously analyze several interrelated problems in order picking systems with multiple performance attributes, such as service levels and operational costs. We demonstrate our approach through comprehensive evaluations of order picking policies in three low‐level, picker‐to‐parts rectangular warehouses facing demand variations.     

A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization

This article deals with the development of a heuristic for scheduling in a flowshop with the objective of minimizing the makespan and maximum tardiness of a job. The heuristic makes use of the simulated annealing technique. The proposed heuristic is relatively evaluated against the existing heuristic for scheduling to minimize the weighted sum of the makespan and maximum tardiness of a job. The results of the computational evaluation reveal that the proposed heuristic performs better than the existing one.     

Order Release in Automated Manufacturing Systems

Order release occurs when orders are released to the shop floor for processing. An order release mechanism (ORM) selectively releases orders to improve shop management and performance. This paper focuses on the question of how to select and develop better ORMs, providing guidelines for practice. We develop a number of propositions on how an ORM should be established and the impact of implementing an ORM. To test the validity of these propositions, we consider three real different automated manufacturing systems. For each system, ORMs are developed and implemented in simulation models. Analysis of the experimental results suggests that some propositions are true under all situations, whereas the degree of validity of others is dependent on variables like system type, and the levels of other design variables. We conjecture that all the propositions can be accepted when the volume of production is high. We use the analysis and the propositions to generate guidelines for practice and areas for future research.     

A New Framework for Manufacturing Planning and Control Systems*

This paper presents a new framework for manufacturing planning and control systems which we call iterative manufacturing planning in continuous time (IMPICT) that appears to have several advantages over the well-known material requirements planning (MRP) framework. IMPICT explicitly considers capacity constraints and total system cost (including tardiness) to determine order sizes, order release/due dates, and operation schedules in a deterministic, multi-level, finite horizon, dynamic demand environment. Continuous time scheduling variables allow setups to be carried over from one period to the next. Three new heuristics built on the IMPICT framework are presented and tested in a simulation-based, full-factorial experiment with a wide variety of problem environments. The benchmark for the experiment was materials requirements planning with operations sequencing (MRP/OS) implemented with best-case, fixed planned lead times. The experiment showed that all three heuristics were statistically better than MRP/OS. The total cost for the order merging (OM) heuristic was 25 percent better than the total cost for MRP/OS. Computational times for OM were substantially larger than for MRP/OS; however, the computational times in the experiment suggest that OM is still computationally viable for large-scale batch manufacturing environments found in industry. IMPICT is superior to standard MRP systems because it explicitly considers capacity constraints and total system costs when it creates a materials plan. IMPICT is superior to linear programming-based approaches to finite loading and scheduling found in the literature because it allows setups to be carried over from one period to another and because it is computationally viable for realistic-sized problems.     

Flexible multi-manned assembly line balancing problem: Model,heuristic procedure,and lower bounds for line length minimization

Assembly lines dedicated to the production of large products often allow multiple workers to perform tasks simultaneously on the product. Previous works on such multi-manned lines define workstations with fixed, discrete, and restrictive frontiers, despite commonly considering continuous paced line control. This paper proposes flexible station frontiers for multi-manned lines and shows that such innovation allows significantly shorter line lengths. A new Mixed Integer Linear Programming model and a novel model-based heuristic procedure are presented to describe and optimize lines. Algorithmic lower bounds are also introduced for the problem. The formulation was compared to a literature benchmark of regular multi-manned solutions. These experiments showed that flexible multi-manned formulations can lead to line length reductions of up to 42%. Such reductions were obtained for most instances (81 out of 88), with an average value of 18%. The relationship between cycle time and minimal line length is also analyzed, demonstrating that efficient solution sets can be continuous or discrete, depending on the instance.     

The Use of Flexible Manufacturing Capacity in Pharmaceutical Product Introductions*

This work considers the value of the flexibility offered by production facilities that can easily be configured to produce new products. We focus on technical uncertainty as the driver of this value, while prior works focused only on demand uncertainty. Specifically, we evaluate the use of process flexibility in the context of risky new product development in the pharmaceutical industry. Flexibility has value in this setting due to the time required to build dedicated capacity, the finite duration of patent protection, and the probability that the new product will not reach the market due to technical or regulatory reasons. Having flexible capacity generates real options, which enables firms to delay the decision about constructing product‐specific capacity until the technical uncertainty is resolved. In addition, initiating production in a flexible facility can enable the firm to optimize production processes in dedicated facilities. The stochastic dynamic optimization problem is formulated to analyze the optimal capacity and allocation decisions for a flexible facility, using data from existing literature. A solution to this problem is obtained using linear programming. The result of this analysis shows both the value of flexible capacity and the optimal capacity allocation. Due to the substantial costs involved with flexibility in this context, the optimal level of flexible capacity is relatively small, suggesting products be produced for only short periods before initiating construction of dedicated facilities.     

A linear programming based heuristic algorithm for charge and discharge scheduling of electric vehicles in a building energy management system

Electric vehicles (EVs) are becoming an attractive alternative to gasoline vehicles owing to the increase of greenhouse gas emissions and gasoline prices. EVs are also expected to function as battery storages for stabilizing large fluctuations in the power grid through the vehicle-to-grid power system, which requires smart charge and discharge scheduling algorithms. In this paper, we develop a linear programming based heuristic algorithm on a time–space network model for charge and discharge scheduling of EVs. We also develop an improved two-stage heuristic algorithm to cope with uncertain demands and departure times of EVs, and evaluate the effect of the smart charge and discharge scheduling of EVs on a peak load reduction in a building energy management system.     

Order Dispatching and Labor Assignment in Cellular Manufacturing Systems

Although order and labor dispatching in the job shop manufacturing setting have been investigated extensively over the last three decades, its representation of actual processes found in practice today is limited due to the move to cellular manufacturing (CM). Manufacturing cells have become an important approach to batch manufacturing in the last two decades, and their layout structure provides a dominant flow structure for the part routings. The flow shop nature of manufacturing cells adds a simplifying structure to the problem of planning worker assignments and order releases, which makes it more amenable to the use of optimization techniques. In this paper we exploit this characteristic and present two mathematical modeling approaches for making order dispatching and labor assignment/reassignment decisions in two different CM settings. The two formulations are evaluated in a dynamic simulation setting and compared to a heuristic procedure using tardiness as the primary performance measure. The formulations are superior to the heuristic approach and can be incorporated into detail scheduling systems that are being implemented by corporations employing enterprise resource planning (ERP) systems today.     

过程系统管理与技术的综合集成

在激烈的市场竞争中,过程企业不仅要重视技术、更要加强管理,实现全局优化运行。提高过程企业的市场竞争能力必须全面综合集成人、组织、战略管理、经营管理、过程管理及信息自动化技术等因素。本文以石化企业为背景,对过程企业面临的问题及发展趋势进行了分析,并且对过程企业管理模式、过程企业的体系结构以及过程集成与优化技术进行了探讨。