Parallel machine scheduling about an unrestricted due date and additional resource constraints

This research considers the problem of schedulingjobs on parallel machines with an unrestricted due date and additional resources. The objective is to minimize the total absolute deviation of job completion times about the common due date. This problem is motivated by restrictions that occur in the handling and processing of jobs in certain phases of semiconductor manufacturing and other production systems. It is shown that the problem is polynomial when there exists one single type of additional resource and the resource requirements per job are zero or one.     

PRODUCTION PLANNING DECISIONS IN FLEXIBLE MANUFACTURING SYSTEMS WITH RANDOM MATERIAL FLOWS

In this paper, we consider the FMS planning problem of determining optimal machine workload assignments in order to rninimize mean part flow time. We decompose this problem into the subproblems of first forming machine groups and next assigning operations to these groups. Three types of grouping configurations—no grouping, partial grouping and total grouping—are considered. In both no grouping and partial grouping, each machine is tooled differently. While each operation is assigned to only one machine in no grouping, partial grouping permits multiple operation assignments. On the other hand, total grouping partitions the machines into groups of identically-tooled machines; each machine within a group is capable of performing the same set of operations. Within this grouping framework, we consider three machine loading objectives—minimizing the total deviation from the optimal group utilization levels, minimizing part travel and maximizing routing flexibility, for generating a variety of system configurations.

A queueing network model of an FMS is used to determine the optimal configurations and machine workload assignments for the no grouping and total grouping cases. It is shown that under total grouping, the configuration of M machines into G groups that minimizes flow time is one in which the sizes of the machine groups are maximally unbalanced and the workload per machine in the larger groups is higher. This extends previous results on the optimality of unbalancing both machine group sizes and machine workload to the mean flow time criterion.

A simulation experiment is next conducted to evaluate the alternative machine configurations to understand how their relative performance depends upon the underlying system characteristics, such as system utilization level and variation among operation processing times. We also investigate the robustness of these configurations against disruptions, such as machine unreliability and variation in processing batch sizes. While different configurations minimize mean flow time under different parameter values, partial grouping with state-dependent part routing performs well across a wide range of these values. Experimental results also show that the impact of disruptions can be reduced by several means, such as aggregating operations of a part to be performed at the same machine, in addition to providing routing flexibility.     

Minimizing total tardiness of orders with reentrant lots in a hybrid flowshop

This study focuses on a hybrid flowshop scheduling problem, in which there are serial stages, each with identical parallel machines. In the hybrid flowshop, each order is composed of multiple lots with the same due date, and each lot can be processed on any one of parallel machines at each stage. In addition, there are reentrant flows since lots of certain orders have to visit the stages twice. Heuristic algorithms are suggested for the scheduling problem with the objective of minimizing total tardiness of a given set of orders. In these algorithms, the list-scheduling method is employed, and lots are scheduled with priorities determined with a construction method. Computational experiments are performed on randomly generated test problems. Results show that the suggested algorithms perform better than well-known dispatching rules for various scheduling problems and an algorithm that is used in a real system.     

Policy mechanisms for supply chain coordination

The problem is to determine a review period and stocking policy that are mutually beneficial to a producer and a retailer. In our model, the retailer uses a periodic review, base stock policy for ordering the item from the producer's Distribution Center (DC). Excess customer demand is assumed to be lost. A make-to-order production system supplies to the DC. We show that given a review period, unless the manufacturer agrees to share the cost of carrying a fraction of the safety stocks at the retailer, the two will not agree upon the level of stocks to be carried in the store. We prove that there is an equilibrium value for this fraction, such that the retailer and the manufacturer are always in agreement with regard to the stocking level. We then show that complete coordination on the stocking level as well as the review period can be achieved solely through carrying out negotiations on credit terms. These theoretical results are used to construct an algorithm for calculating the optimal policy parameters for a supply chain. As part of the analysis we suggest a modification of the base stock policy for the positive lag lost sales case of periodic review inventory models that consistently outperforms the base stock policy in our numerical studies.     

Analysis of the Prediction Problem with Errors in the Variables

In engineering and other scientific works variables are frequently measured with error, resulting in so-called errors-in-variables situations. The problem of estimating unknown parameters in an errors-in-variables model (EVM)has been extensively discussed in the literature while relatively little has been concerned with the prediction problem in the EVM context. In this paper the integrated mean square, error of prediction (TMSE) is developed for a multiple functional relationship model as a measure of the effect of errors in the variables on the predicted values. The IMSE may be used for assessing the severeness of measurement errors as well as for discriminating competing estimators. Relative performances of various estimation methods for a simple functional relationship are compared in terms of the IMSB, Proposed methods are illustrated with two examples, one from business forecasting and the other from work measurement.     

The interaction of location and inventory in designing distribution systems

Many companies face the strategic decision of deciding on the number of Distribution Centers (DCs), their location, and which customers they serve. One objective for a company facing this decision is to maintain acceptable service while minimizing the fixed costs of operating the DCs, inventory holding costs at the DCs, and transportation costs between plants and DCs, and DCs and customers. For insight into this problem, we develop an analytical model for a stylized version of it. However, since the general version of the problem is NP-Hard, we also develop heuristic procedures. We solve a variety of example problems to test the performance of these heuristics relative to optimal solutions and a lower bound based on a relaxation of the original problem. Managerial insight based on our computational studies is provided. We also present a small case-study example motivated by our interaction with Frito-Lay, Inc     

A branch-and-bound algorithm for the cell formation problem

The Cell Formation Problem (CFP) is an important optimisation problem in manufacturing. It has been introduced in the Group Technology (GT) and its goal is to group machines and parts processed on them into production cells minimising the movement of parts to other cells for processing and maximising for each cell the loading of its machines with operations on its parts. We consider one of the computationally hardest formulations of this problem – the CFP with a variable number of cells and the grouping efficacy objective, which is a fractional function. The CFP literature contains many heuristic algorithms, but only a small number of exact approaches especially for this formulation. In the current paper, we present an exact branch-and-bound algorithm for the same hard CFP formulation. To linearise the fractional objective function, we apply the Dinkelbach approach. We have been able to solve 24 of the 35 instances from the well known GT benchmark. For the remaining 11 instances, the difference in the grouping efficacy with the best known solutions is less than 2.6%.     

Mixed-model assembly line scheduling using the Lagrangian relaxation technique

The increasing market demand for product variety forces manufacturers to design mixed-model assembly lines on which different product models can be switched back and forth and mixed together with little changeover costs. This paper describes the design and implementation of an optimization-based scheduling algorithm for mixed-model compressor assembly lines at Toshiba with complicated component supply requirements. A separable integer optimization formulation is obtained by treating compressor lots going through a properly balanced line as undergoing a single operation, and the scheduling goal is to delivery products just in time while avoiding possible component shortage. The problem is solved b y using Lagrangian Relaxation (LR). Several generic defects of LR leading to slow algorithm convergence are identified based on geometrical insights, and are overcome by perturbing/ changing problem parameters. Numerical testing shows that near-optimal schedules are efficiently obtained, convergence is significantly improved, and the method is effective for practical problems. The system is currently under deployment at Toshiba     

Pull-type manufacturing systems with multiple product types

A multiple-product facility consisting of a manufacturing process and a finished product warehouse for several types of products is considered. An (R, r) continuous-review inventory control policy is applied to each type of product in the warehouse. The demand arrival process of each type is assumed to be Poisson. The processing times and the set-up times are arbitrarily distributed. We have developed an iterative procedure to approximately compute the average inventory level of each product in the warehouse under different priority schemes     

Parallel machine scheduling considering a job-splitting property

This paper focuses on the problem of scheduling jobs on parallel machines considering a job-splitting property. In this problem, it is assumed that a job can be split into a discrete number of subjobs and they are processed on parallel machines independently. A two-phase heuristic algorithm is suggested for the problem with the objective of minimizing total tardiness. In the first phase, an initial sequence is constructed by an existing heuristic method for the parallel-machine scheduling problem. In the second phase, each job is split into subjobs considering possible results of the split, and then jobs and subjobs are rescheduled on the machines using a certain method. To evaluate performance of the suggested algorithm, computational experiments are performed on randomly generated test problems. Results of the experiments show that the suggested algorithm performs better than an existing one.     

Tooling choices and product performance

One of the dilemmas that manufacturers face involves the tradeoff between the cost of maintaining a variety of production processes, and the cost of not having the ideal process for every product that they produce. This issue is continuing to become more of a problem as manufacturers are forced by market conditions to offer a wider selection of products. We study an instance of this problem in the manufacture of sheet metal parts. We model the problem of selecting and/or designing tools to punch holes in these parts. The cost of not having an “ideal process” is the cost of not having a tool that precisely matches a hole's design diameter. We consider both general “process deviation” costs as well as the Taguchi loss function. Solution procedures are provided for several versions of the problem.     

Optimal Selection of Machinable Volumes

A brief review of the process planning literature is provided. One of the basic issues in process planning is the feature recognition. In the paper rather than representing a part with features, the representation using machinable volumes is emphasized. A model for the selection of machinable volumes with minimum corresponding machining costs, fixture and tool utilization costs is formulated. The model is illustrated with a numerical example. Computational results for five existing parts are presented.     

Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times

This paper focuses on an identical parallel machine scheduling problem with minimising total tardiness of jobs. There are two major issues involved in this scheduling problem; (1) jobs which can be split into multiple sub-jobs for being processed on parallel machines independently and (2) sequence-dependent setup times between the jobs with different part types. We present a novel mathematical model with meta-heuristic approaches to solve the problem. We propose two encoding schemes for meta-heuristic solutions and three decoding methods for obtaining a schedule from the meta-heuristic solutions. Six different simulated annealing algorithms and genetic algorithms, respectively, are developed with six combinations of two encoding schemes and three decoding methods. Computational experiments are performed to find the best combination from those encoding schemes and decoding methods. Our findings show that the suggested algorithm provides not only better solution quality, but also less computation time required than the commercial optimisation solvers.     

Reacting to Scheduling Exceptions in FMS Environments

Uncertainties in the production environment and modelling limitations inevitably result in operational deviations from schedules generated using predictive models. A production control mechanism monitors the environment for exceptions, and takes corrective actions, with the objective of adhering closely to planned objectives. This paper proposes a knowledge based (KB) methodology to perform such control in FMS environments. Use of KB techniques is motivated by the observation that control knowledge has a high heuristic content. A PROLOG implementation of this methodology, that generates automatic response to machine failures, dynamic introduction of new jobs, and dynamic increase in job priority, is presented. Experimental results appear to show that simple and generic design strategies for the KB can provide the basis for effective and robust control behavior.     

Dynamic Operational Policies in an Automated Warehouse

In this paper we consider the optimal relocation of pallets with a high expectancy of retrieval within each storage rack of an automated warehouse to meet the fluctuating, short-term throughput requirements imposed on the automated storage-retrieval machines. The prepositioning of these pallets closer to the input/output point of each rack during off-peak periods will reduce the expected travel time for the storage/retrieval machines during future peak periods of the planning horizon.

As the model has been abstracted from an actual operating environment, we first describe the environment in which the problem has been posed. We then exploit the special structure of the problem to develop conditions that an optimal relocation policy should satisfy. Based on these optimality conditions, we develop a very efficient optimal relocation algorithm. Finally, we present the performance of several relocation policies in the warehouse studied.     

Production data based similarity coefficient for machine-component grouping decisions in the design of a cellular manufacturing system

This paper presents a similarity coefficient based approach to the problem of machine-component grouping. The proposed method incorporates relevant production data such as part type production volume, routing sequence and unit operation time in the early stages of grouping decisions for cellular manufacturing. The algorithm also suggests a methodology for evaluating alternative solutions from different algorithms on a quantitative basis using a modified version of an existing coefficient. The modified quantitative measure is a comprehensive indicator for the goodness of a grouping solution. The algorithm then identifies bottleneck machines and corresponding cell candidates for their duplication using percentage utilization in each cell as a criterion. Finally, additional constraints can be applied to determine the best grouping solution among alternative solutions generated by the algorithm. A software package has been developed to verify the implementation.     

Role of similarity measures in PCB grouping procedures

The problem of grouping printed circuit boards (PCBs) for simultaneous assembly on electronic assembly machines is an extension of the set-covering problem. A general approach based on cluster analysis and measure of similarity between PCBs is suggested as a basis of PCB grouping. The approach is independent of the specific similarity measure used. We show that, due to the analogy between this problem and the problem of machine cell formation in group technology, similarity measures developed for the second problem are useful as building blocks in a general framework that solves the PCB grouping problem.     

Cell design and multi-period machine loading in cellular reconfigurable manufacturing systems with alternative routing

This paper deals with the design and loading of Cellular Reconfigurable Manufacturing Systems in the presence of alternative routing and multiple time periods. These systems consist of multiple reconfigurable machining cells, each of which has Reconfigurable Machine Tools and Computer Numerical Control (CNC) machines. Each reconfigurable machine has a library of feasible auxiliary machine modules for achieving particular operational capabilities, while each CNC machine has an automatic tool changer and a tool magazine of a limited capacity. The proposed approach consists of two phases: the machine cell design phase which involves the grouping of machines into machine cells, and the cell loading phase that determines the routing mix and the tool and module allocation. In this paper, the cell design problem is modelled as an Integer Linear Programming formulation, considering the multiple process plans of each part type as if they were separate part types. Once the manufacturing cells are formed, a Mixed Integer Linear Programming model is developed for the cell loading problem, considering multi-period demands for the part types, and minimising transportation and holding costs while keeping the machine and cell utilisations in each period, and the system utilisation across periods, approximately balanced. An illustrative problem and experimental results are presented.     

Comparative study of simulated annealing,genetic algorithms and tabu search for solving binary and comprehensive machine-grouping problems

Machine/part grouping problems have proven to be NP-complete and cannot be solved in polynomial time. Solving such problems of reasonable size often relies on heuristic approaches. Recently, several metaheuristic approaches have emerged as efficient tools for solving such problems. However, the development and implementation of such meta-heuristics have not been a trivial issue. The merits of each method and the problems involved in implementation may not be easily apprehended by practitioners, thereby posing difficulties in the selection of an efficient heuristic for industrial applications. For this reason, a comparative study of three important metaheuristic approaches--simulated annealing, genetic algorithms and tabu search for both binary (considering only machines and part types) and comprehensive (involving machine/part types, processing times, lot sizes, and machine capacities) machine grouping problems--was carried out. To test the performance of the three metaheuristics, two binary performance indices and two generalized performance indices were respectively used for binary and comprehensive machine/part grouping problems. The comparisons were made in terms of solution quality, search convergence behaviour and presearch effort. The results indicate that simulated annealing outperforms both genetic algorithm and tabu search particularly for large problems. The genetic algorithm seems slightly better than the tabu search method for the comprehensive grouping problems.     

Automatic segmentation of digitized data for reverse engineering applications

Reverse engineering is the process of developing a Computer Aided Design (CAD)model and a manufacturing database for an existing part. This process is used in CAD modeling of part prototypes, in designing molds, and in automated inspection of parts with complex surfaces. The work reported in this paper is on the automatic segmentation of 3-Dimensional (3-D) digitized data captured by a laser scanner or a Coordinate Measuring Machine (CMM) for reverse engineering applications. Automatic surface segmentation of digitized data is achieved using a combination of region and edge based approaches. It is assumed that the part surface contains planar as well as curved surfaces that are embedded in a base surface. The part surface should be visible to a single scanning probe (21/2D object). Neural network algorithms are developed for surface segmentation and edge detection. A back propagation network is used to segment part surfaces into surface primitives which are homogenous in their intrinsic differential geometric properties. The method is based on the computation of Gaussian and mean curvatures of the surface. They are obtained by locally approximating the object surface using quadratic polynomials. The Gaussian and mean curvatures are used as input to the neural network which outputs an initial region-based segmentation in the form of a curvature sign map. An edge based segmentation is also performed using the partial derivatives of depth values. Here, the output of the Laplacian operator and the unit surface normal are computed and used as input to a Self-Organized Mapping (SOM) network. This network is used to find the edge points on the digitized data. The combination of the region based and the edge based approaches, segment the data into primitive surface regions. The uniqueness of our approach is in automatic calculation of the threshold level for segmentation, and on the adaptability of the method to various noise levels in the digitized data. The developed algorithms and sample results are described in the paper