Under Construction: Annotated Bibliography

This List of Research contains abstracts or brief descriptions of some of my papers.

Iravani, S.M.R., K.T. Sims, and M.P. Van Oyen, “Structural flexibility: A new perspective on the design of manufacturing and service operations,” Management Science, Feb. 2004.   Also, Click here for the Appendix

This paper presents a new method of characterizing flexibility in manufacturing and service operations with multi-purpose resources (e.g. cross-trained labor, multi-product factories, multi-functional machines, etc.). Before performing this work, we would have thought it a bit crazy to suggest that a single number computed only from the structure of multi-functionality (e.g., cross-training pattern) could predictively rank the performance of queueing network models without regard to their level of variability or their parallel or serial structure; however, that is what we are able to do with a 90% success rate on a challenging test suite. Although structural flexibility is not a panacea for designing for flexibility, we believe that it offers an important contribution to current thinking on flexibility in a number of ways: 1. This paper introduces a new concept that we term “structural flexibility.” This approach to flexibility is based upon the structure of the capability/skill sets of the production sources/workers. Roughly analogous to the concept of structural reliability, we specifically show how insight and understanding can be gained by removing the capacity and demand information from the problem and isolating the structural features. It can provide managers with a deeper understanding of the factors that contribute to the flexibility of their systems, and strengthen their judgment in evaluating how to best enhance flexibility. 2. We develop a new structural flexibility methodology that can be used for production systems with serial, parallel, or network flow. We develop analyses to show that this method has intuitively desirable properties and that it provides insight into why “skill chains” are so effective. 3. Our structural flexibility method, which boils the system down to a single index using a (deterministic) maxflow optimization algorithm, is very effective in predicting performance rankings in queueing network models of production systems. We have devoted considerable effort to creating a test suite with both serial and parallel systems. The test suite isolates variability effects from capacity effects, and method is able to predict the correct performance ranking in about 91% of the pairwise comparisons.

Sennott, L., M.P. Van Oyen, and S.M.R. Iravani, “Optimal dynamic assignment of a flexible worker on an open production line with specialists,” accepted subject to minor revision. European Journal of Operations Research (EJOR), 2004.

Abstract: This paper models and analyzes serial production lines with specialists at each station and a single, cross-trained floating worker who can work at any station. We formulate Markov decision process models of K-Station production lines in which (1) workers do not collaborate on the same job, and (2) two workers can work at the same task/workstation on different jobs at the same time. Our model includes holding costs, set-up costs, and set-up times at each station. We rigorously compute finite-state regions of an optimal policy that are valid with an infinite state space, as well as an optimal average cost and the worker utilizations. We also perform a numerical study for lines with two and three stations. Computations and bounds insightfully expose the performance opportunity gained through capacity balancing and variability buffering. Keywords: Control of queueing networks, labor cross-training, floating workers, production flexibility, Markov decision processes

Hopp, W.J., E. Tekin, and M.P. Van Oyen, “Benefits of skill chaining in production lines with cross-trained workers,” Management Science, Vol. 50:1, 2004, 83-98.

Comments: This paper tackles a very relevant design issue in serial production systems (manufacturing or service) and makes significant claims that break with the majority of conventional practice and teaching. In this paper, we examined the conventional wisdom of focusing on management of the production bottleneck in the context of the use of worker cross-training as a mechanism for increasing the bottleneck capacity and balancing a production line’s capacity. In stark contrast to this commonly practiced approach (which we term cherry-picking), our paper considers a cross-training strategy based on the notion of intentionally investing in system flexibility using a cross-training strategy termed skill chaining. The latter has a high level of flexibility while being frugal with the number of skills added to the line. Our comparison shows that skill chaining strategies have the potential to be robust and efficient methods for implementing workforce agility in serial production lines, and they are usually preferable to the conventional approach of cherry-picking. Skill chaining performs well across a variety of simple queue-length based worker coordination policies. This suggests that the coordination policy can be selected to fit worker preferences or other practical system considerations without significant performance loss. The flexibility created by skill chaining is so substantial that the throughput for a given WIP level does not exhibit only diminishing returns to the number of skills added. Instead, skill chaining frequently yields the greatest marginal benefit from the addition of the final skill required to complete the chain, even though this skill trains the bottleneck worker to help out at a non-bottleneck station. While interesting and a departure from traditional thinking, this approach is not a panacea, because it is limited to systems for which a chaining pattern of cross-training is practical. Nevertheless, the approach is likely to find many applications.

Hopp, W.J. and M.P. Van Oyen, “Agile workforce evaluation: A framework for cross-training and coordination,” Forthcoming,  IIE Transactions, 36, 2004, 22 pages.

Abstract: This paper outlines approaches for assessing and classifying manufacturing and service operations in terms of their suitability for use of cross-trained (flexible) workers. We refer to our overall framework as Agile Workforce Evaluation (AWE). The primary contributions of this paper are: (1) a strategic assessment framework that structures the key mechanisms by which cross-training can support organizational strategy, (2) a tactical framework that identifies key factors to guide the selection of an architecture and worker coordination policy for implementing workforce agility, (3) a classification of workforce agility architectures, (4) a survey of a broad range of archetypical classes of worker coordination policies, (5) a survey of the literature with an operational perspective on workforce agility, and (6) identification of opportunities for research and development of architectures for specific production environments.   Keywords: cross-training, worksharing, teams, division of labor, work design.

Comments: At its heart, this paper provides a conceptual framework for justifying and designing investments in workforce agility. Beginning with a definition of fundamental terms and a new perspective on the nature of cross-training, work, and production, we contribute a pair of frameworks for assessing the need for and use of cross-training in applications. First, we offer a strategic framework based on a “strategy matrix” that identifies the connection of cross-training to the organization’s objectives. Second, our tactical framework links the strategic objectives to the tactical-level implementation of cross-training in a manner appropriate to the idiosyncrasies of the application. The paper also spends considerable energy on a classification of canonical approaches to cross-training and a survey of a broad range of literature through this perspective. Finally, we illustrate the propositions of the paper using a variety of brief industrial cases studies. The breadth of this paper required the support of the National Science Foundation under grants DMI-9732868 and DMI-0099821 and the assistance of American Steel Foundries, Bell + Howell Corp. (UMI), GE Financial Assurance, Hewitt Associates, IBM, John Deere Co., Northwestern Memorial Hospital, R.R. Donnelley & Sons Co., Ruud Lighting Corporation, TCS (Aspect Communications), and United Airlines. 

Gel, E.G.S., W. J. Hopp, and M. P. Van Oyen, “Factors affecting opportunity of worksharing as a dynamic line balancing mechanism,” IIE Transactions, 34, 2002, 847-863.

Abstract: We consider the problem of optimal worksharing between two adjacent workers each of whom processes a fixed task in addition to their shared task(s). We use a Markov Decision Process (MDP) model to compute optimal policies and provide a benchmark for evaluating threshold policy heuristics. Our approach differs from previous studies of dynamic line balancing in that we focus on system architecture factors that affect the performance improvement opportunity possible through worksharing relative to a traditional static worker allocations, as well as practical heuristics for worksharing. We find that three such factors are significant whether we use an optimal or a heuristic control policy: ability to preempt the shared task, granularity of the shared task and overall variability of the task times. Understanding the role of these factors in a given production environment provides a means for determining where and how worksharing can have significant logistical benefits.

Comments: One of the most studied and important problems of operations management and industrial engineering is that of production line balancing, where the main objective is to evenly distribute work over the line. However, even if a line is balanced with regard to average loads, variability in processing times can cause the workloads of the stations to become out of balance in the short term. A recent trend in industry to combat variability involves the use of cross-trained workers to shift work (or workers) from one station to another to dynamically balance the load at the workstations.

Several types of systems with cross-trained or flexible workers have been studied in the literature. However, the vast majority of the studies have focused on establishing the effectiveness of a specific type of policy (such as a bucket brigade, team production, craft production, or half-full buffer rules) in a given, well defined environment. While this is an important and logical place to start studying workforce agility, the system architecture is not fixed in the long term and their reality motivates our work to better understand the design principles of effective worksharing in production. The novel contributions of this paper can be summarized in three groups as follows. ” Operationally-oriented guidelines: We provide insights into the structure of an optimal policy as well as the conditions under which a particular heuristic will be effective. ” Issues in design: We identify system architecture factors that significantly affect the limits of the performance improvement achievable through worksharing and illuminate key factors that make a given production system an attractive candidate for worksharing. ” Performance opportunity: We demonstrate that under effective control policies, partial cross-training can achieve significant logistical benefits. Furthermore, more cross-training may not always yield better performance, counter to the intuition of many.

This paper studies the fundamental problem of effective worksharing between two neighboring workers who are cross-trained to share an overlapping task in addition to their unique tasks. The approach we take in this paper is significantly different than that taken in the previous work on the subject. First, using Markov Decision Process (MDP) formulations, we take a control-oriented approach to study worksharing between two workers rather than assuming a certain structure for the worksharing policy. The performance of the optimal policy is used to answer two important questions: (1) How well do practical heuristics work? and (2) How much performance improvement is possible through worksharing, compared to an optimal policy for specialists? Second, we examine the effect of three important system architecture factors on the answers to questions (1) and (2): preemption of the shared task (i.e., whether a task that is already started can be transferred to the downstream station), granularity of the shared task (i.e., whether a non-preemptive shared task can be transferred at certain break points during processing), and processing time variability.

  •     W.J. Hopp, M.P. Van Oyen, E. Tekin, “Cross-training strategies for dynamic line balancing,” Proc. of 2002 NSF Design Grantees Conference, San Juan, 2002.
  •     Hopp, W.J., and Van Oyen, M.P., “Agile Workforce Evaluation: A Framework for Cross-training and Coordination,” Proc. 2001 NSF  Design and Manufacturing Grantees ConferenceTampa, FL (Jan. 2001) 21 pages.
  •     Hopp, W.J., and M.P. Van Oyen, “Toward a taxonomy of agile worksystems,” 2000 NSF Design & Manufacturing Grantees Conf., Vancouver, BC, 2000, 6 pages.
  •     Van Oyen, M.P., “Stochastic scheduling methods for queueing systems,” 2000 NSF Design & Manufacturing Grantees Conf., Vancouver, BC, 2000, 7 pages.

Van Oyen, M.P. and J. Pichitlamken, “Properties of Optimal-Weighted Flowtime Policies with a Makespan Constraint and Set-up Times,” Manuf. and Service Op’s. Mgmt. (M&SOM), 2:1, 2000 84-99.  (see also the earlier version “Allocating a Server to Job Families with Set-Up Times,” Appeared in Proc. 1998 Manufacturing and Service Operations Management (MSOM) Conf., June 1998, 6 pages.)

Abstract:  We characterize optimal policies for the problem of allocating a single server to a set of jobs from N families. Each job is an instance of demand for an item and is associated with a family, a holding cost rate, and a mean processing time. Set-up times are required to switch from one family to another, but are not required to switch within a family. We consider the case in which the order of jobs within the family is unconstrained, and a variation in which the order is fixed. The optimization is with respect to the weighted flowtime, and we treat problems both with and without a makespan-constraint. Practical examples based on this model are described. We partially characterize an optimal policy by means of a Gittins reward rate index and a similar switching index derived from multi-armed bandit theory. For deterministic problems with a makespan constraint, we present an optimization algorithm for the special case of two families and at most three set-ups . Without a makespan constraint and without preemption, we prove that our analysis of a deterministic model extends to stochastic set-up and processing times without loss of optimality. Managerial insights based on our technical results are provided. (Keywords: Job Scheduling; Job Families; Multi-armed Bandit; Group Technology; Weighted Flowtime; Makespan; Set-up Time)

Comments:  This paper considers the multi-family production scheduling problem for a single fully-flexible server (machine or worker) subject to product family-based set-up times and holding costs for work in process. Each family may have multiple subtypes, but switches among subtypes within a family are costless. With stochastic processing and set-up times, we develop results for scheduling the production server to optimize weighted flowtime (and we also address the inclusion of an additional makespan constraint).

The paper shows that the stochastic model can be analyzed via an associated deterministic model. We partially characterize an optimal policy by means of a Gittins reward rate index and a similar switching index derived from multi-armed bandit theory. In this way the set of possible batches is limited to a set of candidates defined by “switching indices.”

This paper was the first to develop reward-rate based switching indices appropriate to problems with job families. Our innovative approach is effective for understanding and proving the structure of optimal policies. We innovate with two new formulations of the problem: First, we introduce the “static” problem (S), which constrains the order of job service within a family. Second, we identify the need to consider an additional makespan constraint to enable the results to be heuristically applied in problems with job arrivals.

These results can be useful in a number of ways. If one desires to compute an optimal policy, our structural properties of an optimal policy greatly narrow down the scope of the search. We present an example of the use of the stopping time index in developing an algorithm for the case of makespan-constrained two-family problems. Because our main results dramatically reduce the amount of search required to find an optimal policy, they form an excellent basis for a heuristic policy.

By integrating the effects of holding costs, set-up times, and processing times through reward rate indices, the benefits of different production scheduling strategies can be better compared. We further establish the appropriateness of reward rate measures as the key to understanding these problems and thereby serve to enhance managerial understanding. Furthermore, the reward rate indices provide insight into when (based on job priorities, service times, and set-up times) sophisticated scheduling can improve upon the standard, simplistic Group Technology solution.

Van Oyen, M.P., E. Senturk-Gel, and W.J. Hopp, “Performance Opportunity for Workforce Agility in Collaborative and Noncollaborative Work Systems,” IIE Transactions, 33, 2001, 761-777.

Abstract: To gain insight into the potential logistical benefits of worker cross-training and agile workforce policies, we study simple models of flexible workers in serial production systems. The primary control issue is how to assign workers to jobs/stations over time. Under assumptions of complete worker flexibility and collaborative work, we prove that a simple expedite policy minimizes along each sample path the cycle time (delay) for each job. Therefore, the expedite policy also minimizes work in process and maximizes throughput along every sample path for any time t. We also consider the optimal static allocation of effort (workers) and use it to compute the performance improvement opportunity achievable using flexible workers. This enables us to examine the factors that make workforce agility a potentially attractive strategy. We extend our analysis to the noncollaborative work environment by presenting evidence for the effectiveness of a common policy we call the pick-and-run policy, but demonstrate by counterexample that it is not always optimal. Finally, we extend some of our insights from a push to a pull environment operating under a constant-WIP (CONWIP) protocol.

  •     Hopp, W.J., M.P. Van Oyen, and E.G.S. Gel “Workforce Agility: Classification and Modeling, Part I,” 1999 NSF Design & Manufacturing Grantees Conf., Long Beach, CA, Jan. 5-8, 1999.(in .html file format)

Kim, E. and M.P. Van Oyen, “Finite-capacity Multi-class Production Scheduling with Setup Times,” IIE Transactions, 32, 2000, 807-818.  (for a previous version of the paper with complete proofs and a heuristic for problems without rejection costs, Click Here.)  Won “Best Paper Award” for Operations Engineering focused issues for 2000-2001.

Abstract: We treat the scheduling of a single server in a finite buffer capacity, multi-class, make-to-order production system subject to inventory holding costs, set-up times, and customer rejection costs. We employ theoretical and numerical analysis of a Markov decision process model to investigate the structure of optimal policies and the performance of heuristic policies. We establish the monotonicity of optimal performance with respect to the system parameters. Based on our insights, we provide a heuristic policy called the Capacitated Modified Index Rule (CMIR) for capacitated scheduling with customer loss penalties. The CMIR heuristic can easily be precomputed and stored for real-time control. Numerical benchmarking with respect to the optimal performance as well as an existing heuristic suggests that CMIR is very effective. Keywords: Polling system, Finite buffer, Capacitated production scheduling, near-optimal heuristic scheduling.

Kim, E., M.P. Van Oyen, and M. Rieders, “General Dynamic Programming Algorithms Applied to Polling Systems,” Communications in Statistics: Stochastic Models, Vol. 14:5, 1998.

Abstract:  We formulate the problem of scheduling a single server in a multi class queueing system as a Markov decision process under the discounted cost and the average cost criteria.  We develop a new implementation of the modified policy iteration (MPI) dynamic programming algorithm to efficiently solve problems with large state spaces and small action spaces.  This implementation has an enhanced policy evaluation (PE) step and an adaptive termination test.  To numerically evaluate various solution approaches, we implemented value iteration and forms of modified policy iteration, and we further developed and implemented aggregation disaggregation based (replacement process de composition and group scaling) algorithms appropriate to controlled queueing system models.  Tests provide evidence that MPI outperforms the other algorithms for both the discounted cost and the average cost optimal polling problems.  In light of the complexity of implementation for the aggregation disaggregation based algorithms and their performance, we cannot recommend them for problems with a sparse transition probability matrix structure.  Our new implementation of MPI is effective in discounted problems and better than previous implementations under the average cost per stage criterion.  Keywords: Markov decision process algorithms, dynamic programming, value iteration, modified policy iteration, polling systems, control of queues

Kim, E. and M.P. Van Oyen, “Dynamic Scheduling to Minimize Lost Sales Subject to Set-up Costs,” Queueing Systems (QUESTA),29, 193-229, 1998. (For a brief version from the ’97 IEEE CDC, click here)

Abstract: We consider scheduling a shared machine in a two-class make-to-stock system subject to switching costs and lost sales costs for lost jobs. If the switching costs are negligible, the optimal policy has a monotonic threshold type of switching curve provided that the service times are identical. For completely symmetric systems without set-ups, it is optimal to serve the longer queue. Using simple analytical models as approximations, we derive a heuristic scheduling policy. Numerical results demonstrate the effectiveness of our heuristic, which is typically within 10% of optimal. We also develop and test a heuristic policy for a model in which the shared resource is part of a series network under a CONWIP release policy.

Kim, E. and M.P. Van Oyen, “Beyond the c mu Rule: Dynamic Scheduling of a Two-class Loss Queue,” Mathematical Methods of Operations Research, Vol. 48:1, 1997.

Abstract: We consider scheduling a single server in a two-class M/M/1 queueing system with finite buffers subject to holding costs and rejection costs for rejected jobs. We use dynamic programming to investigate the structural properties of optimal policies. Provided that the delay of serving a job is always less costly than rejecting an arrival, we show that the optimal policy has a monotonic threshold type of switching curve; otherwise, numerical analysis indicates that the threshold structure may not be optimal.  Keywords: polling system, stochastic scheduling, finite buffer loss penalty, threshold policy

Van Oyen, M.P., I. Duenyas, and C.-Y. Tsai, “Stochastic Sequencing with Job Families, Set-up Times, and Due Dates,” Int`l. Journal of Systems Science, 30:2, 1998, 175–181.

Abstract: We consider the problem of allocating a single server to families of jobs with random service times and due dates. Furthermore, a setup is required when the server switches from one job family to another. We address the problems of minimizing expected weighted flow time, expected maximum lateness, and total weighted tardiness with emphasis on problems for which it is assumed that each family can be set up only once (the Group Technology assumption). We derive conditions under which simple sequencing rules are optimal for each of these problems with group technology.

Van Oyen, M.P., “Monotonicity of Optimal Performance Measures for Polling Systems ,” Probability in the Engineering and Informational Sciences, Vol. 11:2, 1997, 219-228.

Abstract: We consider scheduling a single server in a multi-class queue subject to set-up times and set-up costs. We examine the issue of whether or not reductions in the mean and variance of the set-up time distributions can lead to degraded system performance. Provided that set-ups are reduced according to a stochastically smaller ordering, we show that if an optimal policy is used both for the original system as well as for the system with reduced set-up times, then an improvement in performance is guaranteed. Even in cases for which a truly optimal policy is unknown, idling can be employed to avoid degradation of performance as set-up times are cut. We extend this approach to show that system performance is monotonic with respect to service time distributions, switching costs, holding costs, and uniform reductions in the arrival rates. Extensions to sequence-dependent set-ups and job feedback are noted.

Van Oyen, M.P. and D. Teneketzis, “Optimal Batch Service of a Polling System Under Partial Information,” ZOR: Methods and Models of Operations Research, Vol. 44:3, 1996, 401–419.

Abstract:  We consider the optimal scheduling of an infinite capacity batch server in a N-node ring queueing network, where the controller observes only the length of the queue at which the server is located. For a cost criterion that includes linear holding costs, fixed dispatching costs, and linear service rewards, we prove optimality and monotonicity of threshold scheduling policies.

Duenyas, I. and M.P. Van Oyen, “Heuristic Scheduling of Parallel Heterogeneous Queues with Set-Ups,” Management Science, Vol. 42:6, 1996, 814-829.

Abstract:  We consider the problem of allocating a single server to a system of queues with Poisson arrivals. Each queue represents a class of jobs and possesses a holding cost rate, general service distribution, and general set-up time distribution. The objective is to minimize the expected holding cost due to the waiting of jobs. A set-up time is required to switch from one queue to another.  We provide a limited characterization of the optimal policy and a simple heuristic scheduling policy for this problem. Simulation results demonstrate the effectiveness of our heuristic over a wide range of problem instances.

Duenyas, I. and M.P. Van Oyen, “Stochastic Scheduling of Parallel Queues with Set-Up Costs,” Queueing Systems (QUESTA), Vol. 19, 1995, 421-444.

Van Oyen, M.P. and D. Teneketzis, “Optimal Stochastic Scheduling of Forest Networks with Switching Penalties,” Advances in Applied Probability, Vol. 26, 1994, pp. 474-479.

Abstract:  We present structural properties of optimal policies for the problem of scheduling a single server in a forest network of N queues (without arrivals) subject to switching penalties. In addition to linear holding costs, we impose either lump sum switching costs or batch set-up delays which are incurred at each instant the server processes a job in a queue different than the previous one. We use reward rate notions to unearth conditions on the holding costs and service distributions for which an exhaustive policy is optimal. For the case of two nodes connected probabilistically in tandem, we explicitly define an optimal policy under similar conditions.

Van Oyen, M.P., D.G. Pandelis, and D. Teneketzis, “Optimality of Index Policies for Stochastic Scheduling with Switching Penalties,” Journal of Applied Probability, Vol. 29, 1992, pp. 957-966.

Van Oyen, M.P. and D. Teneketzis, “Optimal Scheduling of a Finite Capacity Shuttle Under Delayed Information,” Probability in the Engineering and Informational Sciences, Vol. 6, 1992, pp. 29-61.

Dr. Mark P. Van Oyen
University of Michigan

Some of this material is based upon work supported by the National Science Foundation under Grant No’s. DMI-95227965, 9732868,0099821, CMMI 1068638, 1161439  as well as Northwestern University and Loyola University Chicago. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, Northwestern University, or Loyola University Chicago.