Search

The effect of workers' learning curves on the production rate in manual assembly lines is significant when producing relatively small batches of different products. This research studies this effect and suggests applying a work-sharing mechanism among the workers to improve the makespan (time to complete the batch). The proposed mechanism suggests that adjacent cross-trained workers will help each other in order to reduce idle times caused by blockage and starvation. The effect of work sharing and buffers on the makespan is studied and compared with a baseline situation, where the line does not contain any buffers and work sharing is not applied. Several linear programming and mixed-integer linear programming formulations for makespan minimization are presented. These formulations provide optimal work allocations to stations and optimal parameters of the work-sharing mechanism. A numerical study is conducted to examine the effect of buffers and work sharing on the makespan reduction in different environment settings. Numerical results are given along with some recommendations regarding the system design and operation. [ABSTRACT FROM AUTHOR]

In this work, we examine a staff scheduling problem in a governmental food safety center that is responsible for the surveillance of imported food at an international airport. In addition to the fact that the staff have different levels of efficiency and have different preference for work shifts, the Operations Manager of the food safety center would like to balance the dissimilarities of workers in order to provide unbiased work schedules for staff members. We adopt a two-phase approach, where the first phase is to schedule the work shifts of food safety inspectors (including rest days and shift types) with schedule fairness and staff preference taken into account and the second phase is to best-fit them to tasks in terms of skill-matches and create diversity of team formations. We also provide polyhedral results and devise valid inequalities for the two formulations. For the first-phase problem, we relax some constraints of the fairness criteria to reduce the problem size to reduce computational effort. We derive an upper bound for the objective value of the relaxation and provide computational results to show that the solutions devised from our proposed methodology are of good quality. For the second-phase problem, we develop a shift-by-shift assignment heuristic to obtain an upper bound for the maximum number of times any pair of workers is assigned to the same shift at the same location. We propose an enumeration algorithm, that solves the problems for fixed values of this number until an optimality condition holds or the problem is infeasible. Computational results show that our proposed approach can produce solutions of good quality in a much shorter period of time, compared with a standalone commercial solver. [ABSTRACT FROM AUTHOR]

This article treats a scheduling problem where timely departures of vehicles executing Just-In-Time (JIT) deliveries between a single supplier and a single receiver along with the assignment of supplies to vehicles are to be determined. This problem, for instance, arises in the automotive industry where parts are to be delivered JIT from a central distribution center to a car manufacturer. We define different subproblems and provide an analysis of computational complexity along with suitable solution procedures. Furthermore, we apply these procedures to an industry case, so that managerial implications are revealed; e.g., with regard to the impact of standardized containers on delivery costs. [ABSTRACT FROM AUTHOR]

Production systems with closed-loop facilities must deal with the problem of sequencing batches in consecutive loops. This article studies a problem encountered in a production facility in which plastic parts of several shapes must be painted with different colors to satisfy the demand given by a set of production orders. The shapes and the colors produce a dual-setup problem that to the best of our knowledge has not been considered in the literature. The problem is formulated as a mixed-integer program and the limitations of this approach as a viable solution method are discussed. Two alternative solution approaches are described that are heuristic in nature: one specialized procedure developed from scratch and the other one built in the framework of commercial software. The presented computational experiments were designed to assess the advantages and disadvantages of both approaches. [ABSTRACT FROM AUTHOR]

In order to process a product in a semiconductor back-end facility, a machine needs to be qualified, first by having product-specific software installed and then running test wafers through it to verify that the machine is capable of performing the process correctly. In general, not all machines are qualified to process all products due to the high machine qualification cost and tool set availability. The machine qualification decision affects future capacity allocation in the facility and subsequently affects daily production schedules. To balance the tradeoff between current machine qualification costs and future potential backorder costs due to not enough machines qualified with uncertain demand, a stochastic product–machine qualification optimization model is proposed in this article. The L-shaped method and acceleration techniques are proposed to solve the stochastic model. Computational results are provided to show the necessity of the stochastic model and the performance of different solution methods. [ABSTRACT FROM AUTHOR]

In the context of multi-channel call centers with inbound calls and emails, this article considers a threshold policy on the reservation of agents for the inbound calls. We study a general non-stationary model where calls arrive according to a non-homogeneous Poisson process. The optimization problem consists in maximizing the throughput of emails under a constraint on the waiting time of inbound calls. An efficient adaptive threshold policy is proposed that is easy to implement in the automatic call distributor. This scheduling policy is evaluated through a comparison with the optimal performance measures found in the case of a constant arrival rate and also with other intuitive adaptive threshold policies in the general non-stationary case. [ABSTRACT FROM PUBLISHER]

This article analyzes a complex scheduling problem at a company that uses a continuous chemical production process. A detailed mixed-integer linear programming model is developed for scheduling the expansive product line, which can save the company an average of 1.5% of production capacity per production run. Furthermore, through sensitivity analysis of the model, key independent variables are identified, and regression equations are created that can estimate both the capacity usage and material waste generated by the product line complexity of a particular production run. These regression models can be used to estimate the complexity costs imposed on the system by any particular product or customer order. Such cost estimates can be used to properly price new customer orders and to most economically assign them to the production runs with the best fit. The proposed approach may be adapted for other long-production-run manufacturing companies that face uncertain demand and short customer lead times. [ABSTRACT FROM PUBLISHER]

This article presents a three-phase methodology for scheduling assembly and test operations for semiconductor devices. The facility in which these operations are performed is a re-entrant flow shop consisting of several dozen to several hundred machines and up to a 1000 specialized tools. The semiconductor devices are contained in lots, and each lot follows a specific route through the facility, perhaps returning to the same machine multiple times. Each step in the route is referred to as a “pass.” In the first phase of the methodology an extended assignment model is solved to simultaneously assign tooling and lots to the machines. Four prioritized objectives are considered: minimize the weighted sum of key device shortages, maximize the weighted sum of lots processed, minimize the number of machines used, and minimize the makespan. In the second phase, lots are optimally sequenced on their assigned machines using the same prioritized objectives. Due to the precedent relations induced by the pass requirements, some lots may have to be delayed or removed from the assignment model solution to ensure that no machine runs beyond the planning horizon. In the third phase, machines are reset to allow additional lots to be processed when tooling is available. The methodology was tested using data provided by the Assembly and Test facility of a leading manufacturer. The results indicate that high-quality solutions can be obtained within 1 hour when compared with those obtained with a greedy randomized adaptive search procedure. Cost reductions were observed across all objectives and averaged 62% in the aggregate. [ABSTRACT FROM AUTHOR]

This article addresses an integrated lot-sizing and scheduling problem that arises in the primary manufacturing phase of a pharmaceutical supply chain. Multiple pharmaceutical ingredients and their intermediate products are to be scheduled on parallel and capacitated bays for production in batches. Sequence-dependent setup times and costs are incurred when cleaning a bay during changeovers between different product families. The problem also contains a high multiplicity asymmetric traveling salesman-type of substructure because of sequence-dependent setups and special restrictions. Mixed-integer programming formulations are proposed for this problem and several valid inequalities are developed to tighten the model. A column generation method along with a decomposition scheme and an advanced-start solution are designed to efficiently derive good solutions to this highly complex problem. A computational investigation is performed, based on instances that closely follow a real-life application, and it demonstrates the efficacy of the proposed solution approach. [ABSTRACT FROM AUTHOR]

An instance of the operational fixed job scheduling problem arises when open work caused by unplanned events such as bus breakdowns, inclement weather, and driver (operator) absenteeism need to be covered by reserve (extraboard) drivers. Each work-piece, which is referred to as a job, requires one operator who must work continuously between specified start and end times to complete the job. Each extraboard operator may be assigned up towhours of work, which may not to be continuous so long as the total work time is within as-hour time window of that operator’s shift start time. Parameterswandsare called allowable work-time and spread-time, respectively. The objective is to choose operators’ shift start times and work assignments, while honoring work-time and spread-time constraints, such that the amount of work covered as part of regular duties is maximized. This paper argues that the extraboard operator scheduling problem is NP-hard and three heuristic approaches are presented for the solution of such problems. These include a decomposition-based algorithm whose worst-case performance ratio is proved to lie in [1 − 1/e, 19/27], wheree≈ 2:718 is the base of the natural logarithm. Numerical experiments are presented that use data from a large transit agency, which show that the average performance of the decomposition algorithm is good when applied to real-world data. [ABSTRACT FROM PUBLISHER]

The requirement to be globally competitive requires companies to have a high level of flexibility to allow for the production of a large variety of products. To limit work-in-process, decision makers periodically schedule according to a make-to-order management strategy i.e. the production of finite batches of the same product code. Scheduling calls for frequent set up activities, which require the reconfiguration of a manufacturing process, and allows manufacturers to switch between different codes. This can limit the production horizon of one product code to a few hours or shifts. In this context, efficient online quality control monitoring using control charts is strategic to eliminate scrap or rework and to meet the demand at the time specified by the production plan. The design of control charts for a process with a limited production horizon is a challenge for statistical process control practitioners. Under this framework, this article investigates the issues related to the implementation of the Variable Sampling Interval (VSI) Shewhart control chart in a process with finite production horizon. When the production horizon is finite, the statistical properties of a control chart are known to be a function of the number of scheduled inspections. In the case of aVSIcontrol chart, the quality practitioner cannot fix the number of inspectionsa prioridue to the stochastic nature of the sampling interval selection. Therefore, the aim of this article is to propose a new Markov chain approach for theexactcomputation of the statistical performance of theVSIcontrol chart in processes with anunknownandfinitenumber of inspections. The proposed approach is general and does not depend on the monitored sample statistic. With reference to the process mean monitoring, an extensive numerical analysis compares the performance of theVSIchart to the Variable Sample Size and Fixed Sampling Ratezcharts. Numerical results show that theVSIchart outperforms other charts for moderate to large shift sizes. An illustrative example shows the implementation of theVSIchart in a short run producing a finite batch of mechanical parts. [ABSTRACT FROM AUTHOR]

This article studies the joint price quotation and production scheduling problem for a manufacturer. The novelty of the work includes modeling the uncertainty in the customer’s order placement, as well as considering the detailed sequencing decision for multiple distinct orders, in a unified framework. We derive closed-form expressions for the expected production cost, measured by the total weighted completion time, under a given set of price quotations and then design dynamic programming algorithms to find the optimal price quotations. The proposed model and algorithms are validated by computational experiments. Important managerial insights are provided. First, the manufacturer only needs to evaluate a few discrete prices to quote, rather than consider a full, continuous spectrum of prices. Second, knowing accurate information on order placement probabilities is important for the manufacturer to make profitable pricing and scheduling decisions. Third, the integrated decision on price quotation and production scheduling has a significant advantage in profit maximization compared with various alternative decision approaches. The quotation model also demonstrates efficiency in quoting dynamically arriving inquiries. [Supplementary materials are available for this article. Go to the publisher’s online edition ofIIE Transactionsfor the proof of Theorem 3.] [ABSTRACT FROM PUBLISHER]

This article studies simulation optimization methods for the stochastic economic lot scheduling problem. In contrast with prior research, the focus of this work is on methods that treat this problem as a black box. Based on a large-scale numerical study, approximate dynamic programming is compared with a global search for parameters of simple control policies. Two value function approximation schemes are proposed that are based on linear combinations of piecewise-constant functions as well as control policies that can be described by a small set of parameters. While approximate value iteration worked well for small problems with three products, it was clearly outperformed by the global policy search as soon as problem size increased. The most reliable choice in this study was a globally optimized fixed-cycle policy. An additional analysis of the response surface of model parameters on optimal average cost revealed that the cost effect of product diversity was negligible. [ABSTRACT FROM AUTHOR]

This article examines the problem of adaptively scheduling a limited number of identical replacements of a vital component, each of which degrades according to a discrete-time Markov chain. The component is vital in the sense that its failure results in irreparable system breakdown; therefore, the objective is to maximize the total expected lifetime of the system, though other performance measures are explored under the optimal policy. The problem is formulated as a discrete-time Markov decision process and its structural properties are examined. While the problem scenario is fairly simple, the proofs of intuitive structural properties via standard dynamic programming approaches are elusive. Instead, we demonstrate the usefulness of a sample path approach in a maintenance optimization context, and provide some counterexamples to other seemingly intuitive structural results. [ABSTRACT FROM PUBLISHER]

This article considers the problem of planning a complex project when there is the possibility of a Disruptive Event (DE) occurring sometime during the project. If such a disruption occurs, work on all activities will stop for some (random) time, but overhead and indirect costs will continue to accrue as well as possible penalty costs. Given information about the likelihood of such an event, how should a risk-neutral manager who wants to minimize the expected total cost of the project react (where total cost includes direct labor costs, indirect/overhead costs, and penalty costs)? Should a manager take preventive action at the start of the project (i.e., build additional slack into the project beyond that of a normal cost-minimizing schedule), act at any time during the project after gaining more information about the likelihood of a disruption, or wait until the DE occurs? The problem is formulated as a stochastic dynamic programming problem and this model is used to demonstrate several important implications for managers who face the threat of potential DEs. An efficient algorithm is described that can find the optimal compression strategies for large-scale projects; a numerical example illustrates both the algorithm and implications. [ABSTRACT FROM AUTHOR]

In a majority of settings, rehabilitative services are provided at healthcare facilities by skilled therapists who work as independent contractors. Facilities include hospitals, nursing homes, clinics, and assisted living centers and may be located throughout a wide geographic area. To date, the problem of constructing weekly schedules for the therapists has yet to be fully investigated. This article presents the first algorithm for supporting weekly planning at the agencies that do the contracting. The goal is to better match patient demand with therapist skills while minimizing treatment, travel, administrative and mileage reimbursement costs. The problem was modeled as a mixed-integer program but has several complicating components, including different patient classes, optional weekly treatment patterns and a complex payment structure that frustrated the use of exact methods. Alternatively, a parallel (two-phase) greedy randomized adaptive search procedure was developed that relies on an innovative decomposition scheme and a number of benefit measures that explicitly address the trade-off between feasibility and solution quality. In Phase I, daily routes are constructed for the therapists in parallel and then combined to form weekly schedules. In Phase II, a high-level neighborhood search is executed to converge towards a local optimum. This is facilitated by solving a series of newly formulated traveling salesman problems with side constraints. Extensive testing with both real data provided by a U.S. rehabilitation agency and associated random instances demonstrates the effectiveness of the purposed procedure. [ABSTRACT FROM AUTHOR]

This article studies the coordination between pricing and production scheduling decisions of a manufacturer who quotes prices for a set of order inquiries. Each inquiry is either canceled or confirmed by its owner following a certain probability distribution that depends on the quoted price. The manufacturer then incurs a production scheduling cost for processing each firm order. Two types of price quotation schemes, simultaneous and sequential quotations, are investigated. A simultaneous quotation quotes all order inquiries simultaneously. The problem is formulated with a specific form of price function as a quadratic program that can be solved efficiently. Properties of optimal quotations are provided. A sequential quotation quotes order inquiries one at a time. For the problem, optimal algorithms are developed using implicit enumeration and design-efficient heuristics. Simultaneous and sequential quotations and several managerial insights are obtained in computational studies. The conditions under which the simultaneous quotation performs close to sequential quotation and conditions under which heuristic sequential quotation performs near optimal are highlighted. [ABSTRACT FROM AUTHOR]

Lot streaming is a fundamental production scheduling technique to squeeze manufacturing lead times by splitting a large lot of n identical items into sublots. This article presents a full characterization of optimal solutions for two-stage lot streaming with attached machine setup times to minimize the makespan. An O(n 3) time dynamic programming algorithm is presented for the discrete variant of the problem, in which all sublot sizes need to be integral. Since this running time can be prohibitively long for larger n, the continuous variant is also analyzed and an O(n) time algorithm for its solution is presented. Also, rounding procedures for the optimal continuous solution to obtain an approximate solution for the discrete problem are designed and analyzed. It is shown that a particular class of rounding procedures, using dynamic programming, has a compelling absolute worst-case and empirical performance. [ABSTRACT FROM PUBLISHER]

The design and real-time scheduling of lift-gas compressors in oil fields entails solving a mixed-integer non-linear problem that generalizes the facility location problem. This article presents a revised formulation that represents the constraints on compressor discharge pressure as a family of linear inequalities, which is shown to be tighter than a previous formulation. Mixed-integer linear approximations for these formulations are obtained by piecewise linearizing the non-linear functions, using binary variables and specially ordered set variables. Valid inequalities for compressor capacity along with separation and lifting procedures are proposed. The article also presents computational experiments comparing the formulations and evaluating the impact of cutting plane generation on solution speed. [ABSTRACT FROM PUBLISHER]

This article considers a new class of multi-period network interdiction problems that focus on scheduling the activities of law enforcement in order to successfully interdict criminals in an illegal drug supply chain. This class of problems possesses several novel features for interdiction problems that were motivated through collaborations with city-level drug enforcement officials. These features include modeling the temporal aspects of these interdictions and the requirements associated with building interdictions in order to arrest high-ranking criminals in the drug supply chain. Based on these collaborations a systematic procedure is developed to generate realistic test instances of the multi-period network interdiction problem. Computational analysis on these realistic test instances provides some direction to the policies that law enforcement should implement in their interdiction activities. [ABSTRACT FROM PUBLISHER]

Balanced words are useful for scheduling mixed-model, just-in-time assembly lines; planning preventive maintenance; managing inventory; and controlling asynchronous transfer mode networks. This article considers the challenging problem of finding a balanced word (a periodic sequence) for a finite set of letters, when the desired densities of the letters in the alphabet are given. Two different measures of balance are considered. This article presents a branch-and-bound approach for finding optimally balanced words and presents the results of computational experiments to show how problem characteristics affect the time required to find an optimal solution. The optimal solutions are also used to evaluate the performance of an aggregation approach that combines letters with the same density, constructs a word for the aggregated alphabet, and then disaggregates this word into a feasible word for the original alphabet. Computational experiments show that using aggregation with the heuristics not only finds more balanced words but also reduces computational effort for larger instances. [ABSTRACT FROM PUBLISHER]

This article considers a make-to-order manufacturing environment with fixed guaranteed delivery lead times and multiple product families, each with a stochastic demand process. The primary challenge in this environment is how to meet the quoted delivery times subject to fluctuating workload and capacity limits. The tactical planning parameters are considered, namely, the planning windows and planned lead times. The planning process that is modeled is the one in which the demand represents a dynamic input into the master production schedule. A planning window for each product family controls how the schedule of each product family is translated into a job release. It can be thought of as the slack that exists when the fixed quoted delivery lead time is longer than the total planned production lead time. Furthermore, the planned lead time of each station regulates the workflow within a multi-station shop. The model has underlying discrete time periods to allow the modeling of the planning process that is typically defined in time buckets; within each time period, the intra-period workflow that permits multiple job movements within the time period is modeled. The presented model characterizes key performance measures for the shop as functions of the planning windows and planned lead times. An optimization model is formulated that is able to determine the values of these planning parameters that minimize the relevant production-related costs. [Supplementary materials are available for this article. Go to the publisher's online edition of IIE Transactions for additional results of the simulation study in Section 6 of this manuscript.] [ABSTRACT FROM AUTHOR]

This article studies the scheduling of buffer times in a single-machine environment. A buffer time is a machine idle time in between two consecutive jobs and is a common tool to protect a schedule against disruptions such as machine failures. This article introduces new classes of robust machine scheduling problems. For an arbitrary non-preemptive scheduling problem 1|β|γ, three corresponding robustness problems are obtained: (i) maximize overall (weighted) buffer time while ensuring a given schedule's performance (with regard to the objective function γ); (ii) optimize the schedule's performance (with regard to γ) while ensuring a given minimum overall (weighted) buffer time; and (iii) find the trade-off curve regarding both objectives. The relationships between the different classes of problems and the corresponding underlying problems are outlined. Furthermore, the robust counterparts of three very basic single-machine scheduling problems are analyzed. [ABSTRACT FROM AUTHOR]

Group testing with variable group sizes for incomplete identification has been proposed in the literature but remains an open problem because the available solution approaches cannot handle even relatively small problems. This article proposes a general two-stage model that uses stochastic dynamic programming at stage 2 for the optimal group sizes and non-linear programming at stage 1 for the optimal number of group-testable units. By identifying tight bounds on the optimal group size for each step at stage 2 and the optimal initial purchase quantity of the group-testable units at stage 1, an efficient solution approach is developed that dramatically reduces both the number of functional evaluations and the intermediate results/data that need to be stored and retrieved. With this approach, large-scale practical problems can be solved exactly within very reasonable computation time. This makes the practical implementation of the dynamic group-testing scheme possible in manufacturing and health care settings. [ABSTRACT FROM AUTHOR]

Forecasting and production control systems typically rely on operational rules that have been accumulated and refined from enterprise experts. Designing a rule-based system is a challenging task. In this article, a new rule-based system design methodology for forecasting and production control is proposed. The methodology first represents the rule-based system as a finite state automaton (a Moore machine) and then formulates an optimal control problem in a feedback control architecture. The solution to the optimal control problem provides action rules for forecasting and production that minimize cost over a given time horizon. The proposed methodology provides a systematic tool for rule-based system design that gives robust and realistic solutions. [ABSTRACT FROM AUTHOR]

For s-precedence constraints, job i cannot start processing until all jobs that precede i start. This is different from the standard definition of a precedence relation where i cannot start until all prior jobs complete. While not discussed in the scheduling literature, s-precedence constraints have wide applicability in real-world settings such as first-come, first-served processing systems. This article considers a deterministic scheduling problem where jobs with s-precedence relations are processed by multiple identical parallel machines. The objective is to minimize the makespan. The problem is shown to be intractable. A heuristic procedure is developed and tight worst-case bounds on the relative error are derived. Finally, computational experiments show that the proposed heuristic provides effective solutions. [ABSTRACT FROM AUTHOR]

In practice, scheduling systems are subject to considerable uncertainty in highly dynamic operating environments. The ability to cope with uncertainty in the scheduling process is becoming an increasingly important issue. This paper takes a proactive scheduling approach to study scheduling problems with two sources of uncertainty: processing time variability and machine breakdowns. Two robustness (expected total flow time and expected total tardiness) and three stability (the sum of the squared and absolute differences of the job completion times and the sum of the variances of the realized completion times) measures are defined. Special cases for which the measures can be easily optimized are identified. A dominance rule and two lower bounds for one of the robustness measures are developed and subseqently used in a branch-and-bound algorithm to solve the problem exactly. A beam search heuristic is also proposed to solve large problems for all five measures. The computational results show that the beam search heuristic is capable of generating robust schedules with little average deviation from the optimal objective function value (obtained via the branch-and-bound algorithm) and it performs significantly better than a number of heuristics available in the literature for all five measures. [ABSTRACT FROM AUTHOR]

A two-stage stochastic integer program to determine an optimal schedule for jobs requiring multiple classes of resources under uncertain processing times, due dates, resource consumption and availabilities is formulated. Temporary resource capacity expansion for a penalty is allowed. Potential applications of this model include team scheduling problems that arise in service industries such as engineering consulting and operating room scheduling. An exact solution method is developed based on Benders decomposition for problems with a moderate number of scenarios. Benders decomposition is then embedded within a sampling-based solution method for problems with a large number of scenarios. A sequential sampling procedure is modified to allow for approximate solution of integer programs and its asymptotic validity and finite stopping are proved under this modification. The solution methodologies are compared on a set of test problems. Several algorithmic enhancements are added to improve efficiency. [ABSTRACT FROM AUTHOR]

A dynamic capacity allocation problem is considered in this paper. A fixed amount of daily processing capacity is allowed. Jobs of different priorities arrive randomly over time and a decision is required on which jobs should be scheduled on which days. The jobs that are waiting to be processed incur a holding cost depending on their priority levels. The objective is to minimize the total expected cost over a planning horizon. In this paper the focus is on a class of policies that are characterized by a set of protection levels. The role of the protection levels is to “protect” a portion of the capacity from the lower priority jobs so as to make it available for the future higher priority jobs. A stochastic approximation method to find a good set of protection levels is developed and its convergence is proved. Computational experiments indicate that protection level policies perform especially well when the coefficient of variation for the job arrivals is high. [Supplementary materials are available for this article. Go to the publisher's online edition of IIE Transactions for the following free supplemental resource: Technical appendix detailing the proofs of propositions.] [ABSTRACT FROM AUTHOR]

A manufacturing firm that builds a product to stock to meet a random demand is studied. Production time is deterministic, so that if there is a backlog, customers are quoted a lead time that is proportional to the backlog. In order to represent the customers' response to waiting, a defection function—the fraction of customers who choose not to order as a function of the quoted lead time—is introduced. Unlike models with backorder costs, the defection function is related to customer behavior. Using a continuous flow control model with linear holding cost and Markov modulated demand, it is shown that the optimal production policy has a hedging point form. The performance of the system under this policy is evaluated, allowing the optimal hedging point to be found. [Supplementary materials are available for this article. Go to the publisher's online edition of IIE Transactions for the following free supplemental resource: Appendix] [ABSTRACT FROM AUTHOR]

This paper describes an approximate analytical method for evaluating the average values of throughput and buffer levels of closed three-machine production systems with finite buffers. The method includes a new set of decomposition equations and a new building block model. The machines have deterministic processing times and geometrically distributed probabilities of failure and repair. The numerical results of the method are close to those from simulation. The method performs well because it takes into account the correlation among the numbers of parts in the buffers. Extensions to larger systems are discussed. [Supplementary materials are available for this article. Go to the publisher's online edition of IIE Transactions for the following free supplemental resource: Appendix of additional numerical results] [ABSTRACT FROM AUTHOR]

Compact, multi-deep three-dimensional (3D), Automated Storage and Retrieval Systems (AS/RS) are becoming more common, due to new technologies, lower investment costs, time efficiency and compact size. Decision-making research on these systems is still in its infancy. This paper studies a particular compact system with rotating conveyors for the depth movement and a Storage/Retrieval (S/R) machine for the horizontal and vertical movement of unit loads. The optimal storage zone boundaries are determined for this system with two product classes: high- and low-turnover, by minimizing the expected S/R machine travel time. We formulate a mixed-integer non-linear programming model to determine the zone boundaries. A decomposition algorithm and a one-dimensional search scheme are developed to solve the model. The algorithm is complex, but the results are appealing since most of them are in closed-form and easy to apply to optimally layout the 3D AS/RS rack. The results show that the S/R machine travel time is significantly influenced by the zone dimensions, zone sizes and ABC curve skewness (presenting turnover patterns of different products). The presented results are compared with those under random storage and it is shown that significant reductions of the machine travel time are obtainable by using class-based storage. [Supplementary materials are available for this article. Go to the publisher's online edition of IIE Transactions for the following free supplemental resource: Appendix] [ABSTRACT FROM AUTHOR]

A multi-item manufacturer served by a single supplier in a stochastic environment is considered. The manufacturer and the supplier have to decide which items to produce to stock and which to produce to order. The manufacturer also has to quote due dates to arriving customers for make-to-order products. The manufacturer is penalized for long lead times, missing the quoted lead times and high inventory levels. Several variations of this problem are considered and effective heuristics for the make-to-order/make-to stock decision are designed to find the appropriate inventory levels for make-to-stock items. Scheduling and lead time quotation algorithms for centralized and decentralized versions of the model are also developed. Extensive computational testing is performed to assess the effectiveness of the proposed algorithms, and the centralized and decentralized models are compared in order to quantify the value of centralized control in this supply chain. As centralized control is not always practical or cost-effective, the value of limited information exchange for this system is explored. [Supplementary materials are available for this article. Go to the publisher's online edition of IIE Transactions for the following free supplemental resource(s): Online appendix including additional computational analysis and proofs.] [ABSTRACT FROM AUTHOR]

The problem of scheduling material-handling hoists in automated electroplating lines to maximize the throughput is considered. An electroplating line processes identical products cyclically in a series of tanks. The transfer of products between tanks is performed by one or more hoists mounted on an overhead track. A system consisting of two hoists is considered in this work. The scheduling problem in this system is significantly more difficult than that with one hoist as it involves additional decisions concerning the assignment of tasks to hoists and additional constraints to ensure that there are no collisions between hoists. A heuristic algorithm to solve the problem is proposed. The algorithm generates sequences of product transfer tasks in the production cycle and assigns the tasks in sequence to the hoists. A linear programming model is developed to find an optimal schedule for each given hoist assignment. The results of computational experiments are presented and discussed demonstrating the effectiveness and efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We consider the problem of locating facilities and allocating servers on a congested network (LASCN). Demands for service that originate from the nodes are assumed to be Poisson distributed and the servers provide a service time that is exponentially distributed. The objective is to minimize the total cost of the system which includes a fixed installation cost, a variable server cost, a cost associated with travel time and a cost associated with the waiting time in the facility for all the customers. The problem is formulated using non-linear programming and subsequently analyzed. Results for exact and approximate solution approaches are reported. We also show that we can modify the approaches to solve the LASCN with constraints limiting both the travel time to the servers and the waiting time of customers. [ABSTRACT FROM AUTHOR]

In this study we provide insights into the effectiveness of the clearing function concept in a hierarchical planning context. The clearing function is a mathematical representation of the relation between the Work-In-Process (WIP) and the throughput of a production process. We use it in a deterministic order release planning model to anticipate the dynamics of the operational level, which is subject to uncertainties. A multi-period single-item order release and scheduling problem is considered in which the delivery schedule of the orders is determined through the planned lead times, and the capacity loading decisions are separated from the order release decisions in a way so as to plan for on-time deliveries. Early or late delivery of the orders, which are released and delivered in batches, has not been considered explicitly in previous studies on clearing functions, and it significantly affects the inventory costs. Both linear and non-linear clearing functions are tested using a simulation approach. The results indicate that modeling the clearing of WIP by a shop should be based on the short-term operational dynamics of the shop rather than on the long-term average shop behavior, since it improves the consistency between the operational planning and scheduling levels of the hierarchy. The presented methods and results provide valuable information on modeling production characteristics in aggregate production planning and scheduling models. [ABSTRACT FROM AUTHOR]

This paper addresses the issue of finding robust and stable schedules with respect to random disruptions. Specifically, two surrogate measures for robustness and stability are developed. The proposed surrogate measures, which consider both busy and repair time distributions, are embedded in a tabu-search-based scheduling algorithm, which generates schedules in a single-machine environment subject to machine breakdowns. The performance of the proposed scheduling algorithm and the surrogate measures are tested under a wide range of experimental conditions. The results indicate that one of the proposed surrogate measures performs better than existing methods for the total tardiness and total flowtime criteria in a periodic scheduling environment. A comprehensive bibliography is also presented. [ABSTRACT FROM AUTHOR]

This paper considers the problem of analyzing and optimizing joint schedules of maintenance and throughput adjustment operations in manufacturing systems. The purpose of joint scheduling of maintenance and throughput changing operations is to maximize the cost benefits of maintenance operations in manufacturing systems in which some or all of the machines can execute their function under different process settings, resulting in different machine and system throughputs. Such a capability enables one to strategically slow down more degraded machines or accelerate freshly maintained machines so that production targets can be met and maintenance operations can be offset to times when they are less intrusive on the manufacturing process. A Monte-Carlo-simulation-based method is proposed for the evaluation of cost effectiveness of any schedule of maintenance and throughput changing operations, and a genetic-algorithm-based method is proposed to enable searching for schedules that would maximize the cost benefits of these operations. A matrix chromosome representation of the joint schedules of maintenance and throughput adjustment operations is introduced and several mechanisms of chromosome evolution and selection are proposed and analyzed in numerical simulations of such manufacturing systems. Results indicate a good ability for the newly proposed methods to achieve a tradeoff between cost benefits of production and losses due to maintenance operations through strategic allocation of maintenance and throughput changing actions. [ABSTRACT FROM AUTHOR]

Capacity flexibility is becoming increasingly important as a means for reducing inventory while maintaining customer service levels. We examine two means to increase capacity flexibility. In particular, we examine an environment where both cross training and flexible workdays are available to respond to workload variability. Flexible workdays are under consideration in the US Legislature. This proposed legislation provides the opportunity for workers to exchange overtime for time off. From a managerial perspective, flexible workdays allow management to shift capacity from periods of light load to periods of heavy load. We simulate the operation of a job shop with both cross training and flexible workdays. Our results indicate that cross training is a far more effective tool for improving performance as compared to flexible workdays. Flexible workdays can be valuable particularly in volatile conditions. However, our results indicate that the degree of cross training is a critical consideration in determining the impact of flexible workdays. [ABSTRACT FROM AUTHOR]

Many New Product Development (NPD) projects are inherently complex, making effective management of the tasks, resources, and teams necessary to bring new products to market problematic. Frequently, managers of NPD projects are overwhelmed by complicating factors such as stochastic task times, ill-defined specifications, complex interrelationships between tasks, and information dependencies. Recently, an alternative project management tool called the Design Structure Matrix (DSM) that explicitly takes into account the iterative nature of NPD projects has been proposed. In this paper, we first introduce a mixed-integer linear programming formulation for the numerical DSM. Then, we analyze the numerical DSM and establish the complexity of this class of problems. Finally, numerical analysis of the DSM problem and heuristic approaches is presented that shows that relatively good solutions can be easily obtained, thereby offering managers an efficient alternative solution approach to the original DSM problem. [ABSTRACT FROM AUTHOR]

We extend the classical no-wait two-machine flow shop scheduling problem to the case where job-processing times are controllable through the allocation of a common, limited and nonrenewable resource. Our objective is to simultaneously determine the sequence of the jobs and the resource allocation for each job on both machines in order to minimize the makespan. By using the equivalent load method to obtain the optimal resource allocation on a series-parallel graph, we reduce the problem to a sequencing one and show that it is equivalent to a new special case of the Traveling Salesman Problem (TSP). We prove that although the reduced problem forms a subclass of the TSP on permuted Monge matrices, it is still strongly NP-hard. We provide an approximation result and present three special cases which are polynomially solvable. We have also tested two different subtour-patching heuristics in large-scale computational experiments on randomly generated instances of the problem. Both heuristics produced close-to-optimal solutions in most cases. [ABSTRACT FROM AUTHOR]

In the stochastic online scheduling environment, jobs with unknown release times and weights arrive over time. Upon arrival, the information on the weight of the job is revealed but the processing requirement remains unknown until the job is finished. In this paper we consider the objective of minimizing the total weighted completion time. With the assumptions that job weights are bounded, machine capacity is adequate, and processing requirements are bounded and identical and independently distributed across the machines and jobs, we show that any nondelay algorithm is asymptotically optimal for the stochastic online single machine problem, flow shop problem, and uniform parallel machine problem. Our simulation studies of these stochastic online scheduling problems show that two generic nondelay algorithms perform very well as long as the number of jobs is larger than 100. [ABSTRACT FROM AUTHOR]

The analysis of event sequence data that contains system failures is becoming increasingly important in the design of service and maintenance policies. This paper presents a systematic methodology to construct a statistical prediction model for failure event based on event sequence data. First, frequent failure signatures, defined as a group of events/errors that repeatedly occur together, are identified automatically from the event sequence by use of an efficient algorithm. Then, the Cox proportional hazard model, that is extensively used in biomedical survival analysis, is used to provide a statistically rigorous prediction of system failures based on the time-to-failure data extracted from the event sequences. The identified failure signatures are used to select significant covariates for the Cox model, i.e., only the events and/or event combinations in the signatures are treated as explanatory variables in the Cox model fitting. By combining the failure signature and Cox model approaches the proposed method can effectively handle the situation of a long event sequence and a large number of event types in the sequence. Its effectiveness is illustrated by a numerical study and analysis of real-world data. The proposed method can help proactively diagnose machine faults with a sufficient lead time before actual system failures to allow preventive maintenance to be scheduled thereby reducing the downtime costs. [ABSTRACT FROM AUTHOR]

This paper considers the problem of scheduling operations in bufferless robotic cells that produce identical parts. Finding a cyclic solution that minimizes the long-run average time to produce a part has long been a fundamental open problem. Most research has been focused on finding an optimal 1-unit cyclic solution. However, it is known that an optimal multi-unit cyclic solution can be better than an optimal 1-unit cyclic solution for cells with four or more machines. For additive travel-time cells, we present a linear-time algorithm that produces a cyclic solution whose per unit cycle time is within a factor of 10/7 of the optimum. This result improves the current best 3/2-approximation guarantee. [ABSTRACT FROM AUTHOR]

We consider an integrated scheduling and distribution model in which jobs completed by two different machines must be bundled together for delivery. The objective is to minimize the sum of the delivery cost and customers' waiting costs. Such a model not only attempts to coordinate the job schedules on both machines, but also aims to coordinate the machine schedules with the delivery plan. Polynomial-time heuristics and approximation schemes are developed for the model with only direct shipments as well as the general model with milk-run deliveries. [ABSTRACT FROM AUTHOR]

This paper deals with the Flow-shop Scheduling Problem (FSP). The NEH algorithm is regarded as one of the best constructive methods for solving the FSP. However, the running time of the NEH algorithm when used to solve large-scale FSPs is fairly long. The block properties of the FSP are investigated to reduce the running time. Using these block properties it is found that if a partial schedule is evaluated, the lower bounds of other partial makespans can be obtained in a time of O(1). A pruning procedure based on the block properties of the FSP is introduced into the NEH algorithm to reduce the computational complexity. Experimental results show that the improved NEH algorithm has a greatly reduced running time compared with the classical NEH algorithm. It takes less than 0.2 seconds on average to get a solution for a large-scale FSP (up to 500 jobs and 20 machines). [ABSTRACT FROM AUTHOR]

This paper reviews the literature related to the class of scheduling problems that involve sequence-dependent setup times (costs), an important consideration in many practical applications. It focuses on papers published within the last decade, addressing a variety of machine configurations including single machine, parallel machine, flow shop, and job shop systems and reviews the optimization and heuristic solution methods used for each category. Since lot sizing is so intimately related to scheduling, this paper reviews work that integrates these issues in relationship to each configuration. This paper provides a perspective of this line of research, gives conclusions, and discusses fertile research opportunities posed by this class of scheduling problems. [ABSTRACT FROM AUTHOR]

The ability to respond quickly to customer demands is a key factor in successfully competing in today's globally competitive markets. Thus, meeting due dates could be the most important goal of scheduling in many manufacturing and service industries. Meeting due dates can naturally be translated into minimizing job tardiness. In this paper we present a priority rule for dynamic job shop scheduling that minimizes mean job tardiness. The rule is developed based on the characteristics of existing dispatching rules. With job due dates set by the generalized total work content rule, the computational results of simulation experiments show that the proposed dispatching rule consistently, and often, significantly outperforms a number of well-known priority rules in the literature. The proposed rule is also robust being the best or near-best rule for reducing the mean flowtime, for all the shop load levels and due date tightness factors tested. [ABSTRACT FROM AUTHOR]

This paper focuses on the development of an integrated short-term production scheduling simulation model for a complex manufacturing operation. The decision making tool has a front-end user data interface built with Microsoft Access and Visual Basic for Applications software. The model assists production planners to make informed decisions on how best to schedule simultaneously two lanes of daily or weekly production on a unique plastic parts manufacturing line. The advantages and disadvantages (model weaknesses) of using the simulation model, especially as a scheduling tool, are discussed. In this particular application, we find that the advantages far outweigh the disadvantages. [ABSTRACT FROM AUTHOR]

A fundamental scheduling problem is to determine a production start (ready) time for jobs based on customer-specified due dates. Typically, the objective is to delay the ready time in an attempt to minimize work-in-process inventory and maximize production system utilization. In many practical situations, notably remanufacturing operations, highly variable operation times and intricate process plans complicate this problem. In such a case, a specific ready time implies a confidence of on-time completion. Prior analytical results imply the optimal solution is a function of: (i) customer due dates; (ii) desired confidence levels; and (iii) stochastic makespan minimization. This paper proposes the use of a network flow model to represent a remanufacturing flowshop and then presents a structured heuristic approach that is able to develop sequences and ready times for remanufacturing systems by balancing the three factors. A broad experimental design is used to demonstrate that the proposed scheduling method outperforms previous list rules in terms of the calculated mean and robustness values. [ABSTRACT FROM AUTHOR]