Assembly Line Balancing Using Genetic Algorithms with Heuristic-Generated Initial Populations and Multiple Evaluation Criteria*

We use genetic algorithms (GA) to solve the assembly line balancing (ALB) problem. Inparticular, we show how this technique can be used to generate feasible line balances, improve upon solutions obtained by other heuristics reported in the literature, and utilizeany one or more evaluation criteria that can be expressed in functional form. The procedure is demonstrated with two examples: (1) intimating the improvement of heuristic-generated ALB solutions by including them in the GA initial population, and (2) the possibility of balancing assembly lines with multiple criteria and side constraints. These examples suggest that GA can be a powerful tool in ALB. To investigate the utility of GA on single-criterion problems, an experiment is conducted that compares both the GA approach and conventional heuristics. Results indicate that the GA solutions are significantly improved over the heuristic solutions under the conditions studied. It is also found that the presence of heuristic-generated conventional solutions in the GA initial population leads to statistically preferred results.     

EFFICIENT MODULAR IMPLEMENTATION OF BRANCH-AND-BOUND ALGORITHMS*

This paper demonstrates how branch-and-bound algorithms can be modularized to obtain implementation efficiencies. For the manager, this advantage can be used to obtain faster implementation of algorithm results; for the scientist, it allows efficiencies in the construction of similar algorithms with different search and addressing structures for the purpose of testing to find a preferred algorithm. The demonstration in part is achieved by showing how the computer code of a central module of logic can be transported between different algorithms that have the same search strategy. Modularizations of three common searches (the best-bound search and two variants of the last-in-first-out search) with two addressing methods are detailed and contrasted. Using four assembly line balancing algorithms as examples, modularization is demonstrated and the search and addressing methods are contrasted. The application potential of modularization is broad and includes linear programming-based integer programming. Benefits and disadvantages of modularization are discussed. Computational results demonstrate the viability of the method.     

Application of the Back Propagation Neural Network Algorithm with Monotonicity Constraints for Two-Group Classification Problems*

Neural network techniques are widely used in solving pattern recognition or classification problems. However, when statistical data are used in supervised training of a neural network employing the back-propagation least mean square algorithm, the behavior of the classification boundary during training is often unpredictable. This research suggests the application of monotonicity constraints to the back propagation learning algorithm. When the training sample set is preprocessed by a linear classification function, neural network performance and efficiency can be improved in classification applications where the feature vector is related monotonically to the pattern vector. Since most classification problems in business possess monotonic properties, this technique is useful in those problems where any assumptions about the properties of the data are inappropriate.     

DYNAMIC LOCATION MODELING FOR PUBLIC-SECTOR FACILITIES: A MULTICRITERIA APPROACH*

A major complication in the planning of facility systems and in the analysis of their locational configurations is the fluctuating nature of the systems they serve. Locations identified now, based on current conditions, may be undesirable in the future, and those based on future conditions may be undesirable now. This paper proposes a general methodology using multiobjective analysis to plan public-sector facility systems operating in a dynamic environment. A model is developed for the specific case of locating emergency services and an illustrative example is presented.     

Refining Two-Group Multivariable Classification Models Using Univariate Optimal Discriminant Analysis*

Fisher's discriminant analysis (FDA) is often used to obtain a prediction model for dichotomous classifications on the basis of two or more independent variables. FDA provides an equation whereby values on independent variables are combined into a single predicted value (Y*) that is compared against a cutpoint and direction in order to make classifications. Theoretically, univariate optimal discriminant analysis employed on these Y* will maximize training classification accuracy. This methodology is illustrated using three examples.     

Equivalent Alternate Solutions for the Tour Scheduling Problem*

Achieving minimum staffing costs, maximum employee satisfaction with their assigned schedules, and acceptable levels of service are important but potentially conflicting objectives when scheduling service employees. Existing employee scheduling models, such as tour scheduling or general employee scheduling, address at most two of these criteria. This paper describes a heuristic to improve tour scheduling solutions provided by other procedures, and generate a set of equivalent cost feasible alternatives. These alternatives allow managers to identify solutions with attractive secondary characteristics, such as overall employee satisfaction with their assigned tours or consistent employee workloads and customer response times. Tests with both full-time and mixed work force problems reveal the method improves most nonoptimal initial heuristic solutions. Many of the alternatives generated had more even distributions of surplus staff than the initial solutions, yielding more consistent customer response times and employee workloads. The likelihood of satisfying employee scheduling preferences may also be increased since each alternative provides a different deployment of employees among the available schedules.     

Tour Scheduling and Task Assignment of a Heterogeneous Work Force: A Heuristic Approach

The dual problem of work tour scheduling and task assignment involving workers who differ in their times of availability and task qualifications is examined in this paper. The problem is presented in the context of a fast food restaurant, but applies equally well to a diverse set of service operations. Developing a week-long labor schedule is a nontrivial problem, in terms of complexity and importance, which a manager spends as much as a full workday solving. The primary scheduling objective (the manager's concern) is the minimization of overstaffing in the face of significant hourly and daily fluctuations in minimum staffing requirements. The secondary objective (the workers’ concern) is the minimization of the sum of the squared differences between the number of work hours scheduled and the number targeted for each employee. Contributing to scheduling complexity are constraints on the structure of work tours, including minimum and maximum shift lengths and a maximum number of workdays. A goal programming formulation of a representative problem is shown to be too large, for all practical purposes, to be solved optimally. Existing heuristic procedures related to this research possess inherent limitations which render them inadequate for our purposes. Subsequently, we propose and demonstrate a computerized heuristic procedure capable of producing a labor schedule requiring at most minor refinement by a manager.     

IMPLICIT OPTIMAL AND HEURISTIC LABOR STAFFING IN A MULTIOBJECTIVE,MULTILOCATION ENVIRONMENT*

This paper presents a tractable set of integer programming models for the days-off scheduling of a mix of full- and part-time employees working α to β days/week (cycle) in a multiple-objective, multiple-location environment. Previous models were formulated to specifically schedule part-time employees working either two or three days per week. These models were intractable because they required complete employee schedule information. The new models are deemed implicit optimal since they are required to supply only essential information. While the number of variables in previous models is an exponential increasing function of β-α, the size of three of the new models is independent of α and β. The first three models developed here (as in [18]) deal with the trade-offs between idle time, the number of employees required to work at multiple “locations,” and the size of the total labor pool. The inherent flexibility of the implicit modeling approach is illustrated by the presentation of various modifications of the basic models. These modifications permit the use of preference weights on the number of employee work days/week (cycle) or the minimization of payroll costs where differential pay rates exist. These latter models may also be formulated such that idle time is ignored, constrained or minimized. The execution time for the implicit models (on a CDC CYBER 730 computer with commercially available software) averaged well under five seconds on 1200 trial problems for the type of application considered in [18]. A solution was obtained in less than 46 seconds of CPU time for a trial problem which would have required over 1.4 million integer variables with previous models. The availability of optimal solutions was invaluable in the development of two heuristics designed to deal with the trade-offs of [16]. In an experimental analysis a previous heuristic produced results which averaged from 74 to 508 percent above optimum across six experimental conditions. The comparable new heuristic produced results which averaged from 3 to 8 percent above optimum for the same experimental conditions. The paper concludes by developing a framework to integrate the results of this research with the tour scheduling problem and by identifying several other areas for related research.     

Service Package Switching in Hotel Revenue Management Systems

Revenue Management Systems (RMS) are commonly used in the hotel industry to maximize revenues in the short term. The forecasting‐allocation module is a key tactical component of a hotel RMS. Forecasting involves estimating demand for service packages across all stayover nights in a planning horizon. A service package is a unique combination of physical room, amenities, room price, and advance purchase restrictions. Allocation involves parsing the room inventory among these service packages to maximize revenues. Previous research and existing revenue management systems assume the demand for a service package to be independent of which service packages are available for sale. We develop a new forecasting‐allocation approach that explicitly accounts for this dependence. We compare the performance of the new approach against a baseline approach using a realistic hotel RMS simulation. The baseline approach reflects previous research and existing industry practice. The new approach produces an average revenue increase of at least 16% across scenarios that reflect existing industry conditions.     

Vendor Selection with Bundling*

Product bundling has become increasingly prevalent not only in consumer goods but also in the industrial sector. We study a purchasing problem in which a buyer must obtain necessary numbers of various stock items from a variety of vendors who charge different prices, have limited capacities and different levels of quality, and offer bundled products at discounted prices. We examine relationships among different bundling scenarios and show that the most general scenario is one in which free items are given to the buyer when sufficient quantities are purchased. We develop a mixed integer linear program that finds the purchasing strategy for the buyer that minimizes the total purchase cost. We present computational results which indicate that the problem is very tractable to solve optimally on a personal computer with standard optimization software. Finally, three extensions of the model are discussed.     

Analyzing and Modeling the Maximum Diversity Problem by Zero-One Programming*

The problem of maximizing diversity deals with selecting a set of elements from some larger collection such that the selected elements exhibit the greatest variety of characteristics. A new model is proposed in which the concept of diversity is quantifiable and measurable. A quadratic zero-one model is formulated for diversity maximization. Based upon the formulation, it is shown that the maximum diversity problem is NP-hard. Two equivalent linear integer programs are then presented that offer progressively greater computational efficiency. Another formulation is also introduced which involves a different diversity objective. An example is given to illustrate how additional considerations can be incorporated into the maximum diversity model.     

Modelbase Construction with Object-Oriented Constructs*

This paper proposes modelbase construction mechanisms in a decision support system (DSS) for representing and managing models of diverse management science/operations research modeling paradigms, using object-oriented database management systems (ODBMS) constructs. It focuses on the construction of a modelbase that maintains logical independence among the DSS components including modelbase, database, and solvers, but relieves the mismatching characteristics by facilitating intelligent and stabilized integration of them. As a conceptual framework to build such a modelbase, this research uses generic model concepts, and adopts structured modeling language (SML) as a paradigm-neutral model representation sublanguage. In the modelbase, three model abstraction layers including model type, model structure, and model instance are devised to facilitate the capture of multiple modeling paradigms and specific application models in different instantiation levels. The constructs and methods discussed are flexible enough to be applied to a wide variety of decision-making and problem-solving paradigms. A prototype system is developed under a commercial ODBMS called OBJECTSTORE with the C++ programming language, and diverse model manipulation commands are illustrated by an object-oriented structured query language (OSQL).     

MODELS OF PARTS-ORIENTING SYSTEMS*

An analytical model to estimate, evaluate, and compare the behavior and performance of parts-orienting systems for automated manufacturing systems is developed. The model can be applied to parts-orienting systems for both traditional series-structured manufacturing systems and nontraditionally structured flexible manufacturing systems. Numerical examples are given for typical system configurations such as the pure series system, the pure parallel system, and the pure feedback system.     

Notes and Communications ON SENSITIVITY ANALYSIS IN DECISION THEORY*

This note points out a crucial flaw in Evans's recent article [1] on decision sensitivity analysis which was published in this journal. This flaw leads to errors in the majority of his formulae and examples. Correct distance formulae in “probability space,” easily computed from the problem data, are provided. After a critical discussion of some of the concepts Evans employed, we bring to the reader's attention a body of prior work in this area that apparently was overlooked.     

Scheduling in a Management Context: Uncertain Processing Times and Non-Regular Performance Measures*

Decision makers often face scheduling problems in which processing times are not known with certainty. Non-regular performance measures, in which both earliness and tardiness are penalized, are also becoming more common in both manufacturing and service operations. We model a managerial environment with task processing times (which include sequenceindependent set-up times) prescribed by three-parameter lognormal distributions. Upon completion, each task derives a reward given by a particular piecewise-linear reward function. The objective is to select a sequence of tasks maximizing the expected total reward. The relative generality of the problem renders many enumerative methods inapplicable or computationally intractable. To overcome such difficulties we develop efficient priorityinduced construction (PIC) heuristics which build up a complete schedule by inserting tasks (singly from a list) into a partial sequence of tasks. In each partial and complete sequence a period of idle time is permitted prior to the first task. Performance on realistic-sized problems is very encouraging, with cost penalties averaging less than one percent.     

Concepts,Theory, and Techniques PRINCIPLES OF MULTIOBJECTIVE OPTIMIZATION*

This paper attempts to isolate and analyze the principal ideas of multiobjective optimization. We do this without casting aspersions on single-objective optimization or championing any one multiobjective technique. We examine each fundamental idea for strengths and weaknesses and subject two—efficiency and utility—to extended consideration. Some general recommendations are made in light of this analysis. Besides the simple advice to retain single-objective optimization as a possible approach, we suggest that three broad classes of multiobjective techniques are very promising in terms of reliably, and believably, achieving a most preferred solution. These are: (1) partial generation of the efficient set, a rubric we use to unify a wide spectrum of both interactive and analytic methods; (2) explicit utility maximization, a much-overlooked approach combining multiattribute decision theory and mathematical programming; and (3) interactive implicit utility maximization, the popular class of methods introduced by Geoffrion, Dyer, and Feinberg [24] and extended significantly by others.     

Minimizing Misclassifications in Linear Discriminant Analysis*

A procedure is developed for determining two-group linear discriminant classifiers that misclassify the fewest number of observations in the training sample. An experimental study confirms the value of this approach.     

Solving Resource Allocation Problems When Earning Effects Are Present

Learning effects play an important role in certain resource allocation problems, and several authors have proposed models for these problems that capture the relevant relationships. However, the models may be difficult to implement or have shortcomings in the prescribed solution procedures. In this paper, we selectively review the work to date and present a simple reformulation that facilitates solution by off-the-shelf software.     

Integrative Cycle Scheduling Approach for a Capacitated Flexible Assembly System*

This study revisits the traditional single stage, multi-item, capacitated lot-sizing problem (CLSP) with a new integrative focus on problem structuring. Unlike past research, we develop integrative cycle scheduling approaches which simultaneously address lot-sizing, capacity, and sequencing issues. Our purposes are to (1) explore the effect of sequencing on inventory levels, (2) examine the problem of infeasibility in the economic lot scheduling problem (ELSP), and (3) provide a simple methodology of generating low-cost cycle schedules in an environment with discrete shipping, dynamic demands, limited capacity, zero setup cost, and sequence-independent setup times. Our procedures are compared to benchmark cycle scheduling approaches in terms of both inventory cost and computation time under different demand scenarios, using the operating data from a flexible assembly system (FAS) at the Ford Motor Company's Sandusky, Ohio plant.     

Theoretical Distributions of Optima for Univariate Discrimination of Random Data*

Optimal linear discriminant models maximize percentage accuracy for dichotomous classifications, but are rarely used because a theoretical framework that allows one to make valid statements about the statistical significance of the outcomes of such analyses does not exist. This paper describes an analytic solution for the theoretical distribution of optimal values for univariate optimal linear discriminant analysis, under the assumption that the data are random and continuous. We also present the theoretical distribution for sample sizes up to N= 30. The discovery of a statistical framework for evaluating the performance of optimal discriminant models should greatly increase their use by scientists in all disciplines.