Scheduling flexible flow lines with no in-process buffers

An heuristic algorithm is proposed for scheduling a flexible flow line with no intermediate buffers. The line is made up of several processing stages in series, where each stage has one or more identical parallel machines. In the line different part types can be manufactured simultaneously, each of which is processed by at most one machine in every stage. Intermediate queues of parts waiting between the stages for their next operations are not allowed. The problem objective is to minimize the makespan of the schedule for a set of part types selected for processing. The algorithm proposed is a part-by-part heuristic, in which during every iteration a complete processing schedule is determined for one part type selected for loading into the line. The selection of the part type and its complete schedule are based on the cumulative partial schedule obtained for all parts selected so far. The decisions in every iteration are made using a local optimization procedure aimed at minimizing total blocking and waiting time of the machines along the route of the selected part type. The efficiency of the algorithm is tested on several groups of random test problems     

Parallel-machine,multiple-product-type,continuous-time scheduling: decomposable cases

This paper considers a manufacturing system where multiple-product-types are produced on a set of parallel machines. The production quantity for each product-type in a planning horizon is predetermined. However, the planning horizon is not fixed, and a cost must be paid for each unit of time in the horizon. Inventory holding costs are incurred due to storing products in the buffer placed after each machine. In addition, a production cost is incurred if a machine is not idle. Our objective is to schedule the production so that inventory, production, and planning horizon costs are minimized. With the aid of the maximum principle, this continuous-time scheduling problem is studied, and the conditions such that the problem can be decomposed into a set of well-structured, discrete-time sub-problems are derived. Consequently, several solvable cases are identified, and their corresponding polynomial-time algorithms are suggested.     

Scheduling preventive maintenance on a single CNC machine

In this study we attempt to deal with process planning, scheduling and preventive maintenance (PM) decisions, simultaneously. The objective is to minimize the total completion time of a set of jobs on a CNC machine. During the process planning, we decide on the processing times of the jobs which are controllable (i.e. they can be easily changed) on CNC machines. Using shorter processing times (higher production rates) would result in greater deterioration of the machine, and we would need to plan more frequent PM visits to the machine, during which it would not be available. Therefore, the selected processing times determine not only the completion times but also the PM visit times. We first provide optimality properties for the joint problem. We propose a new heuristic search algorithm to determine simultaneously the processing times of the jobs, their sequence and the PM schedule.     

Parallel-machine scheduling with controllable processing times and rate-modifying activities to minimise total cost involving total completion time and job compressions

In this paper, we consider unrelated parallel-machine scheduling involving controllable processing times and rate-modifying activities simultaneously. We assume that the actual processing time of a job can be compressed by allocating a greater amount of a common resource to process the job. We further assume that each machine may require a rate-modifying activity during the scheduling horizon. The objective is to determine the optimal job compressions, the optimal positions of the rate-modifying activities and the optimal schedule to minimise a total cost function that depends on the total completion time and total job compressions. If the number of machines is a given constant, we propose an efficient polynomial time algorithm to solve the problem.     

Examining the use of dedicated and general purpose pallets in a dedicated flexible manufacturing system

This research describes one example of how the failure to understand the relationships between the flexibility associated with all resources within an FMS can be critical to overall performance. The need for such understanding is clearly spelled out by Jaikumar (1986). This research illustrates that even in situations where the demands placed upon the system are very well defined, tooling resources, such as pallets, may constrain overall system flexibility and subsequent system performance. In this paper, we simulate the operational performance of an existing FMS designed to manufacture a relatively small set of agricultural equipment components (only eight part types) over a known planning horizon using general purpose pallets and dedicated pallets. The simulation model is run under experimental conditions that include levels of: demand mix variability, number of each type pallet available to the system, and incremental loading time and scrap rate when general purpose pallets are used. In most cases, the results indicate a significant increase in system performance when using general purpose pallets. In general, while system performance decreases as the level of demand mix variability increases, relatively higher throughput is obtained using general purpose pallets except where the assumed incremental loading times and scrap rates associated with assembling the pallets are highest. System performance also improves as additional pallets are made available. In addition, overall system investment is impacted as fewer general purpose pallets are required to achieve a given level of performance compared to the use or dedicated pallets. As the overall system investment and scheduling restrictions associated with dedicated pallets would be expected to increase with the number of part types made in the system, the results found in this analysis for a dedicated FMS producing a small number of parts on a regular basis form a relative ‘lower bound’ on the scheduling and investment benefits of using general purpose pallets.     

A scatter search approach with dispatching rules for a joint decision of cell formation and parts scheduling in batches

A joint decision of cell formation and parts scheduling is addressed for a cellular manufacturing system where each type of machine and part may have multiple numbers and parts must require processing and transferring in batches. The joint decision problem is not only to assign batches and associated machine groups to cells, but also to sequence the processing of batches on each machine in order to minimise the total tardiness penalty cost. A nonlinear mixed integer programming mathematical model is proposed to formulate the problem. The proposed model, within nonlinear terms and integer variables, is difficult to solve efficiently for real size problems. To solve the model for practical purposes, a scatter search approach with dispatching rules is proposed, which considers two different combination methods and two improvement methods to further expand the conceptual framework and implementation of the scatter search so as to better fit the addressed problem. This scatter search approach interactively uses a combined dispatching rule to solve a scheduling sub-problem corresponding to each integer solution visited in the search process. A computational study is performed on a set of test problems with various dimensions, and computational results demonstrate the effectiveness of the proposed approach.     

Revising the master production schedule in a HPP framework context

This paper investigates the stability of the master production schedule (MPS) in a multi-product batch chemical plant, a typical example of manufacturing plants in the process industry. The effects of demand pattern, replanning periodicity, setup costs and unit production cost on the performance of the MPS in a rolling horizon situation are examined. Adopting the hierarchical production planning framework, a two-level mathematical model is developed to conduct the study. A comprehensive simulation work and statistical analyses are reported in this work. The results of the study show that replanning periodicity significantly influences the scheduling instability and the impact of setup cost on scheduling instability is dependent on the demand pattern and the unit production cost. Moreover, the findings indicate that replanning frequency does not affect the total cost of the system if the cost structures are not extreme. Finally, the results show that cost structures affect the batching of orders (converting production quantities into an optimal number of batches to be processed).     

A chromatic scheduling model with costs

An extension of a preemptive open-shop scheduling problem is introduced. All processing times are integral and in each period i there is a cost c_i, for each task which is processed in that period. Finding a schedule with minimum total cost is shown to be NP-hard; some solvable cases are discussed; bounds on the cost of an optimum schedule are computed. Finally, a special case is studied, namely where each job has at most three tasks and each processor has to work on at most three tasks. It is shown to have theoretical complexity equivalent to the general case.     

Rolling horizon production scheduling of multi-model PCBs for several assembly lines

The joint task of allocating several PCB assembly jobs to a set of production lines, load balancing of the line machines and job scheduling is considered. The production facility includes a number of assembly lines of different kinds, the PCB jobs are of different types and they should be allocated to suitable (i.e. feasible) lines. Scheduling of the production should respect the predefined release and due dates, and the objective is to minimise the sum of job tardy times. The scheduling is of the rolling-horizon-type where at the beginning of each planning period new jobs are inserted in the current non-preemptive production programme of unfinished jobs from the past planning periods. A mathematical formulation and a two-phase heuristic (including initial job-to-line allocation and schedule improving steps) are given for the problem. Experimental tests with jobs from practice were convincing.     

Advanced production scheduling for batch plants in process industries

An Advanced Planning System (APS) offers support at all planning levels along the supply chain while observing limited resources. We consider an APS for process industries (e.g. chemical and pharmaceutical industries) consisting of the modules network design (for long–term decisions), supply network planning (for medium–term decisions), and detailed production scheduling (for short–term decisions). For each module, we outline the decision problem, discuss the specifi cs of process industries, and review state–of–the–art solution approaches. For the module detailed production scheduling, a new solution approach is proposed in the case of batch production, which can solve much larger practical problems than the methods known thus far. The new approach decomposes detailed production scheduling for batch production into batching and batch scheduling. The batching problem converts the primary requirements for products into individual batches, where the work load is to be minimized. We formulate the batching problem as a nonlinear mixed–integer program and transform it into a linear mixed–binary program of moderate size, which can be solved by standard software. The batch scheduling problem allocates the batches to scarce resources such as processing units, workers, and intermediate storage facilities, where some regular objective function like the makespan is to be minimized. The batch scheduling problem is modelled as a resource–constrained project scheduling problem, which can be solved by an efficient truncated branch–and–bound algorithm developed recently. The performance of the new solution procedures for batching and batch scheduling is demonstrated by solving several instances of a case study from process industries.     

Single CNC machine scheduling with controllable processing times and multiple due dates

In this study, we solve the single CNC machine scheduling problem with controllable processing times. Our objective is to maximize the total profit that is composed of the revenue generated by the set of scheduled jobs minus the sum of total weighted earliness and weighted tardiness, tooling and machining costs. Customers offer multiple due dates to the manufacturer, each coming with a distinct price for the order that is decreasing as the date gets later, and the manufacturer has the flexibility to accept or reject the orders. We propose a number of ranking rules and scheduling algorithms that we employ in a four-stage heuristic algorithm that determines the processing times for each job and a final schedule for the accepted jobs simultaneously, to maximize the overall profit.     

Dynamic scheduling for complex engineer-to-order products

The current paper considers dynamic production scheduling for manufacturing systems producing products with deep and complex product structures and complicated process routings. It is assumed that manufacturing and assembly processing times are deterministic. Dynamic scheduling problems may be either incremental (where the schedule for incoming orders does not affect the schedule for existing orders) or regenerative (where a new schedule is produced for both new and existing orders). In both situations, a common objective is to minimize total costs (the sum of work-in-progress holding costs, product earliness and tardiness costs). In this research, heuristic and evolutionary-strategy-based methods have been developed to solve incremental and regenerative scheduling problems. Case studies using industrial data from a company that produces complex products in low volume demonstrate the effectiveness of the methods. Evolution strategy (ES) provides better results than the heuristic method, but this is at the expense of significantly longer computation times. It was found that performing regenerative planning is better than incremental planning when there is high interaction between the new orders and the existing orders.     

Robust scheduling of a two-machine flow shop with uncertain processing times

This paper focuses on manufacturing environments where job processing times are uncertain. In these settings, scheduling decision makers are exposed to the risk that an optimal schedule with respect to a deterministic or stochastic model will perform poorly when evaluated relative to actual processing times. Since the quality of scheduling decisions is frequently judged as if processing times were known a priori, robust scheduling, i.e., determining a schedule whose performance (compared to the associated optimal schedule) is relatively insensitive to the potential realizations of job processing times, provides a reasonable mechanism for hedging against the prevailing processing time uncertainty. In this paper we focus on a two-machine flow shop environment in which the processing times of jobs are uncertain and the performance measure of interest is system makespan. We present a measure of schedule robustness that explicitly considers the risk of poor system performance over all potential realizations of job processing times. We discuss two alternative frameworks for structuring processing time uncertainty. For each case, we define the robust scheduling problem, establish problem complexity, discuss properties of robust schedules, and develop exact and heuristic solution approaches. Computational results indicate that robust schedules provide effective hedges against processing time uncertainty while maintaining excellent expected makespan performance     

Optimal Scheduling of Multiple Feedstock Batch Biogas Production Systems

Biomass to methane production systems have the potential of supplying 25% of the yearly national natural gas demand. The production systems associated with this conversion process are anaerobic digestion facilities. The optimal operation of a batch biomass digester system requires the scheduling of all batches from multiple feedstocks during a fixed time horizon. A significant characteristic of these systems is that the feedstock decays in storage before use in the digester system. The optimal batch residence times in the digester must account for the production rate as well as the decay rate of stored biomass. The availability times, biomass quantities, biogas production rates and storage decay rates must all be taken into account for maximal biogas production to be achieved during the planning horizon. This paper addresses the scheduling of both single and multiple feedstocks in a single digester system. The single feedstock batch scheduling time problem is solved by a dynamic programming algorithm. The multiple feedstock problem is solved by a decomposition approach where the master level allocates time to each feedstock while the subproblems schedule batches within these time allocations.     

Job order releasing and throughput planning for multi-priority orders in wafer fabs

To meet the production target of multi-level (multiple priority rank) orders in wafer fabs, this paper uses a hierarchical framework based on a mathematical model, and without the assistance of any simulation tool, to build a production scheduling system to plan wafer lot releasing sequence and time. This system first applies capacity loading analysis to set up the batch policy for each level (rank) of orders. Next, the production cycle time of each product level is estimated with considerations of batching and loading factor. The cycle time is then used to derive system control parameters such as the most appropriate level of work in process (WIP) and the number of daily operations on the bottleneck workstation. Lastly, a Constant WIP mechanism is applied to establish a wafer release sequence table and a throughput timetable. The due date designation for each specific order can hence be confirmed. With the comparison with the result of simulation, it shows that under the designed system the performance and planning measures in the master production schedule can be drawn up quickly and accurately, and the system throughput target and due date satisfaction can be achieved. Overall, the proposed production scheduling system is both effective and practicable, and the planning results are supportive for good target planning and production activity control.     

柔性制造系统生产中的零件分批算法

根据ＦＭＳ资源、加工任务、零件工艺提出了零件分批算法，该算法在零件交货期的束下，以机床负荷平衡为目标，搜索零件集合，找出最合适的零件组合形成零件加工批。此算法为简化ＦＭＳ的动态调度和提高系统生产率创造了条件。仿真结果表明分批算法是行之有效的。     

A rolling horizon approach for material requirement planning under fuzzy lead times

This paper proposes a fuzzy multi-objective integer linear programming (FMOILP) approach to model a material requirement planning (MRP) problem with fuzzy lead times. The objective functions minimise the total costs, back-order quantities and idle times of productive resources. Capacity constraints are included by considering overtime resources. Into the crisp MRP multi-objective model, we incorporate the possibility of occurrence of each uncertain lead time using fuzzy numbers. Then FMOILP is transformed into an auxiliary crisp mixed-integer linear programming model by a fuzzy goal programming approach for each fuzzy lead time combination. In order to defuzzify the set of solutions associated with each fuzzy lead time combination, a solution method based on the centre of gravity concept is addressed. Model validation with a numerical example is carried out by a novel rolling horizon procedure where uncertain lead times are updated during each planning period according to the centre of gravity obtained. For illustration purposes, the proposed solution approach is satisfactorily compared to a rolling horizon approach in which lead times are allocated when the possibility of occurrence is established at one.     

Integrated model for supplier selection and negotiation in a make-to-order environment

The paper deals with the development of an integrated supplier selection and negotiation process for multiple parts/materials procurement. The main objective is to integrate decisions in the internal supply chain of a make-to-order manufacturer. Two main decisions during the negotiation process are considered: (1) the manufacturing planning decision responsible for determining the production schedule and fabrication lot size and (2) the supplier selection decision concerning which suppliers are selected for company business and the order volume allocated to each selected supplier. The model is designed to support the negotiation process by generating a set of effective alternatives in each negotiation period. Its structure is multi-objective and non-linear. The combination of the interactive weighted Tchebycheff method and Benders decomposition method is applied to generate a set of effective alternatives to support the decision-maker in each negotiation period.     

Sensitivity analysis of a fuzzy multiobjective scheduling problem

This paper concerns sensitivity analysis of a class of complex job shop scheduling problems which are characterized by: (1) a large number of jobs and machines, (2) uncertain jobs processing times, and (3) multiple measures of schedule performance including average weighted tardiness, the number of tardy jobs, the total setup times, the total idle time of machines, and the total flow times of jobs. The base schedule is generated by applying a new fuzzy multiobjective genetic algorithm which takes into consideration batching of the jobs of a similar type, jobs’ lots sizing and load balancing of the machines. The aim of the proposed sensitivity analysis of a generated schedule is to investigate the consequences of prolongations of job processing times on the measures of schedule performance. The processing times are described by triangular fuzzy numbers and their prolongation is done by expanding the supports of fuzzy numbers. The sensitivity analysis is performed through a series of numerical experiments. The effects of prolongations of job processing times on the measures of performance of a generated schedule are recorded and analysed. It is shown that the sensitivity analysis is among the primaries in evaluating the quality of a generated schedule. The sensitivity analysis is used in identifying the critical jobs and the critical machines which have the properties that the prolongations of their processing times produce the largest deteriorations of the performance measures and the overall quality of a generated schedule.     

A note on 'deliberately slowing down output in a family production context'

In this paper, we consider the economic lot scheduling problem with controllable production rates and imperfect quality. The problem is to schedule the production of several different items in the same facility on a repetitive basis. The facility is such that only one item can be produced at a time and the demand rate for each item is constant over an infinite planning horizon. We focus on the case where quality is imperfect and yield rates decrease with increased production rates and lot sizes. We show that the resulting lot sizes under the proposed extension are smaller. Also, we show that the production rates for some products can be considerably different from the case of perfect quality.