Performance of static priority rules for shared facilities in a remanufacturing shop with disassembly and reassembly

In this paper, we propose a stylized model of a basic remanufacturing shop that handles two remanufacturable products. Product A is comprised of two components A1 and A2, whereas product B is a single entity. After disassembly, component A1 is remanufactured at facility F1; component A2 and product B are remanufactured at facility F2. Both remanufacturing facilities have limited capacity, and are modeled as M/G/1 queues. First, we argue that, under the assumptions of our model, delaying a component to the shop after disassembly, which is a common release mechanism in actual shops, never improves system performance, measured in terms of total weighted average sojourn time (TWAST). Second, we show that the constrained optimal scheduling rule at facility F2 (constrained to simple non-preemptive static priority rules) that minimizes TWAST depends on the processing time characteristics of A1, A2, and B, and can only be found numerically, in general. Using an extensive numerical study based on a numerical approximation for product A's average sojourn time, we show, however, that using FCFS as a scheduling rule at F2 achieves similar TWAST performance, with an average increase of only 7.5%. We also perform a simulation study and show that a two-moment approximation for product A's average sojourn time performs well except for a narrow utilization band.     

Optimal stochastic scheduling in a single server biclass retrial queueing system

The paper deals with the assignment of a single server to two retrial queues. Each customer reapplies for service after an exponentially distributed amount of time. The server operates at customer dependent exponential rates. There are holding costs and costs during service per customer and per unit of time. We provide conditions on which it is optimal to allocate the server to queue 1 or 2 in order to minimize the expected total costs until the system is cleared.     

A Lagrangean heuristic algorithm for disassembly scheduling with capacity constraints

This paper considers the problem of determining the disassembly schedule (quantity and timing) of products in order to satisfy the demand of their parts or components over a finite planning horizon. The objective is to minimize the sum of set-up, disassembly operation, and inventory holding costs. As an extension of the uncapacitated versions of the problem, we consider the resource capacity restrictions over the planning horizon. An integer program is suggested to describe the problem mathematically, and to solve the problem, a heuristic is developed using a Lagrangean relaxation technique together with a method to find a good feasible solution while considering the trade-offs among different costs. The effectiveness of the algorithm is tested on a number of randomly generated problems and the test results show that the heuristic suggested in this paper can give near optimal solutions within a short amount of computation time.     

A two-stage heuristic for disassembly scheduling with assembly product structure

Disassembly scheduling, one of the important operational problems in disassembly systems, is the problem of determining the ordering and disassembly schedules of used or end-of-life products while satisfying the demand of their parts or components over a certain planning horizon. This paper considers products with assembly structure for the objective of minimizing the sum of purchase, set up, inventory holding, and disassembly operation costs, and suggests a two-stage heuristic, in which an initial solution is obtained in the form of the minimal latest ordering and disassembly schedule, and then improved iteratively considering trade-offs among different cost factors. To show the performance of the heuristic, computational experiments were done on the example obtained from the literature and a number of randomly generated test problems, and the results show that the heuristic can give optimal or very near-optimal solutions within very short computation times.     

Master surgery scheduling with consideration of multiple downstream units

We consider a master surgery scheduling (MSS) problem in which block operating room (OR) time is assigned to different surgical specialties. While many MSS approaches in the literature consider only the impact of the MSS on operating theater and operating staff, we enlarge the scope to downstream resources, such as the intensive care unit (ICU) and the general wards required by the patients once they leave the OR. We first propose a stochastic analytical approach, which calculates for a given MSS the exact demand distribution for the downstream resources. We then discuss measures to define downstream costs resulting from the MSS and propose exact and heuristic algorithms to minimize these costs.     

Multi-product economic lot scheduling problem with separate production lines for manufacturing and remanufacturing

We study the economic lot scheduling problem with two production sources, manufacturing and remanufacturing, for which operations are performed on separate, dedicated lines. We develop an exact algorithm for finding the optimal common-cycle-time policy. The algorithm combines a search for the optimal cycle time with a mixed integer programming (MIP) formulation of the problem given a fixed cycle time. Using case study data from an auto part producer, we perform a sensitivity study on the effects of key problem parameters such as demand rates and return fractions. Furthermore, by comparing to results in Tang and Teunter [Tang, O., Teunter, R.H., 2006. Economic lot scheduling problem with returns. Production and Operations Management] for the situation where all operations are performed on the same line, we analyze the cost benefits of using dedicated lines.     

A branch and bound algorithm for disassembly scheduling with assembly product structure

This paper considers a production planning problem in disassembly systems, which is the problem of determining the quantity and timing of disassembling end-of-use/life products in order to satisfy the demand of their parts or components over a planning horizon. The case of single product type without parts commonality is considered for the objective of minimizing the sum of setup and inventory holding costs. To show the complexity of the problem, we prove that the problem is NP-hard. Then, after deriving the properties of optimal solutions, a branch and bound algorithm is suggested that incorporates the Lagrangean relaxation-based upper and lower bounds. Computational experiments are performed on a number of randomly generated problems and the test results indicate that the branch and bound algorithm can give optimal solutions up to moderate-sized problems in a reasonable computation time. A Lagrangean heuristic for a viable alternative for large-sized problems is also suggested and compared with the existing heuristics to show its effectiveness.     

Optimal policies in stochastic shop scheduling

In this paper a survey is presented of some of the recent results in stochastic open shop, flow shop and job shop scheduling. The distributions of the processing times of the jobs are known in advance, but the actual processing times are not known in advance. The jobs may have due dates. Optimal preemptive and nonpreemptive policies are determined for the minimization of various objective functions, such as the expected makespan, the expected flow time and the expected number of late jobs. The effect of various degrees of dependence between the processing times of any given job on the various machines is investigated. Under given conditions bounds are obtained for the expected makespan in the different models.Partially supported by the National Science Foundation (NSF), under grant ECS-8115344 with the Georgia Institute of Technology.     

Multi-resource allocation in stochastic project scheduling

We propose a resource allocation model for project scheduling. Our model accommodates multiple resources and decision-dependent activity durations inspired by microeconomic theory. First, we elaborate a deterministic problem formulation. In a second stage, we enhance this model to account for uncertain problem parameters. Assuming that the first and second moments of these parameters are known, the stochastic model minimises an approximation of the value-at-risk of the project makespan. As a salient feature, our approach employs a scenario-free formulation which is based on normal approximations of the activity path durations. We extend our model to situations in which the moments of the random parameters are ambiguous and describe an iterative solution procedure. Extensive numerical results are provided.     

Optimal stochastic scheduling of systems with Poisson noises

We consider the problem of optimal stochastic scheduling for nonlinear systems with Poisson noise disturbances and a performance index including both operating costs and costs for scheduling changes. In general, the value functions of the dynamic programming, quasi-variational inequalities which define the optimality conditions for such problems are not differentiable. However, we can treat them as viscosity solutions as introduced by Crandall and Lions. Existence and uniqueness questions are studied from this point of view.This author's research was conducted in the Applied Mathematics Program at the University of Maryland, College Park. It was supported in part by the Department of Energy under contract DE-AC01-79ET-29244.This author's research was supported in part by the Army Research Office under contract DAAG29-83-C-0028 with SEI, Greenbelt, MD. Address correspondence concerning the paper to this author.     

A stochastic production planning problem in hybrid manufacturing and remanufacturing systems with resource capacity planning

DIRECT is derivative-free global-search algorithm has been found to perform robustly across a wide variety of low-dimensional test problems. The reason DIRECT’s robustness is its lack of algorithmic parameters that need be “tuned” to make the algorithm perform well. In particular, there is no parameter that determines the relative emphasis on global versus local search. Unfortunately, the same algorithmic features that enable DIRECT to perform so robustly have a negative side effect. In particular, DIRECT is usually quick to get close to the global minimum, but very slow to refine the solution to high accuracy. This is what we call DIRECT’s “eventually inefficient behavior.” In this paper, we outline two root causes for this undesirable behavior and propose modifications to eliminate it. The paper builds upon our previously published “MrDIRECT” algorithm, which we can now show only addressed the first root cause of the “eventually inefficient behavior.” The key contribution of the current paper is a further enhancement that allows MrDIRECT to address the second root cause as well. To demonstrate the effectiveness of the enhanced MrDIRECT, we have identified a set of test functions that highlight different situations in which DIRECT has convergence issues. Extensive numerical work with this test suite demonstrates that the enhanced version of MrDIRECT does indeed improve the convergence rate of DIRECT.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

Sequencing and scheduling N customers for a stochastic server

In this paper, we study the problem of sequencing and scheduling N customers for a single-server system. The goal is to balance the expected customer flow times and the expected system completion time. Customers are scheduled to enter the system by appointments only and the service times are exponentially distributed with different rates. The optimization of such a system involves determining the customer service order (sequencing) and the interarrival times (scheduling). We show that the service order depends upon the order of service rates and the optimal schedule can be obtained by solving a set of nonlinear equations. Numerical examples are used to illustrate the method.     

Electricity market clearing with improved scheduling of stochastic production

In this paper, we consider an electricity market that consists of a day-ahead and a balancing settlement, and includes a number of stochastic producers. We first introduce two reference procedures for scheduling and pricing energy in the day-ahead market: on the one hand, a conventional network-constrained auction purely based on the least-cost merit order, where stochastic generation enters with its expected production and a low marginal cost; on the other, a counterfactual auction that also accounts for the projected balancing costs using stochastic programming. Although the stochastic clearing procedure attains higher market efficiency in expectation than the conventional day-ahead auction, it suffers from fundamental drawbacks with a view to its practical implementation. In particular, it requires flexible producers (those that make up for the lack or surplus of stochastic generation) to accept losses in some scenarios. Using a bilevel programming framework, we then show that the conventional auction, if combined with a suitable day-ahead dispatch of stochastic producers (generally different from their expected production), can substantially increase market efficiency and emulate the advantageous features of the stochastic optimization ideal, while avoiding its major pitfalls.     

Approximation results in parallel machnies stochastic scheduling

We consider scheduling a batch of jobs with stochastic processing times on parallel machines. We derive various new formulae for the expected flowtime and weighted flowtime under general scheduling rules. Smith's Rule, which orders job starts by decreasing ratio of weight to expected processing time provides a natural heuristic for this problem. We obtain a bound on the worst case difference between the expected weighted flow time under Smith's Rule and under an optimal policy. For a wide class of processing time distributions, this bound is of oderO(1) and does not increase with the number of jobs.This research was supported in part by NSF Grant ECS-8712798.     

Dynamic multi-priority,multi-class patient scheduling with stochastic service times

Efficient patient scheduling has significant operational, clinical and economical benefits on health care systems by not only increasing the timely access of patients to care but also reducing costs. However, patient scheduling is complex due to, among other aspects, the existence of multiple priority levels, the presence of multiple service requirements, and its stochastic nature. Patient appointment (allocation) scheduling refers to the assignment of specific appointment start times to a set of patients scheduled for a particular day while advance patient scheduling refers to the assignment of future appointment days to patients. These two problems have generally been addressed separately despite each being highly dependent on the form of the other. This paper develops a framework that incorporates stochastic service times into the advance scheduling problem as a first step towards bridging these two problems. In this way, we not only take into account the waiting time until the day of service but also the idle time/overtime of medical resources on the day of service. We first extend the current literature by providing theoretical and numerical results for the case with multi-class, multi-priority patients and deterministic service times. We then adapt the model to incorporate stochastic service times and perform a comprehensive numerical analysis on a number of scenarios, including a practical application. Results suggest that the advance scheduling policies based on deterministic service times cannot be easily improved upon by incorporating stochastic service times, a finding that has important implications for practice and future research on the combined problem.     

Deliberation scheduling using GSMDPs in stochastic asynchronous domains

We propose a new decision-theoretic approach for solving execution-time deliberation scheduling problems using recent advances in Generalized Semi-Markov Decision Processes (GSMDPs). In particular, we use GSMDPs to more accurately model domains in which planning and execution occur concurrently, plan improvement actions have uncertain effects and duration, and events (such as threats) occur asynchronously and stochastically. In this way, agents develop a continuous-time deliberation policy offline which can then be consulted to dynamically select deliberation-level and domain-level actions at plan execution-time. We demonstrate a significant improvement in expressibility over previous discrete-time approximate models in which mission phase duration was fixed, failure events were synchronized with phase transitions, and planning time was discretized into constant-sized planning quanta.     

Time complexity of single machine scheduling with stochastic precedence constraints

This paper deals with single machine scheduling problems with stochastic precedence relations (so calledGERT networks). Until now most investigations on such problems, dealt with algorithms running in polynomial time. On the other hand, for scheduling problems with deterministic precedence relations exist a lot of results about time complexity. Therefore, the object of this paper is to consider time complexity of scheduling problems with stochastic precedence constraints and to describe the boundary between theNP-hard problems and those which can be solved in polynomial time.     

Minimizing earliness and tardiness costs in stochastic scheduling

We address the single-machine stochastic scheduling problem with an objective of minimizing total expected earliness and tardiness costs, assuming that processing times follow normal distributions and due dates are decisions. We develop a branch and bound algorithm to find optimal solutions to this problem and report the results of computational experiments. We also test some heuristic procedures and find that surprisingly good performance can be achieved by a list schedule followed by an adjacent pairwise interchange procedure.     

Concerning a stochastic dynamical system

We study the discrete-time dynamical system $$X_{n + 1} = 2\sigma \cos (2\pi \theta _n )g(X_n ), n \in \mathbb{Z},$$ Whereθ _n is an ergodic stationary process whose univariate distribution is uniform on the interval [0, 1], the functiong(x) is odd, bounded, increasing, and continous, and ? is the ring of integers. It is proved that under certain conditions there exists a unique stationary process that is a solution of the above equation and this process has a continous purely singular spectrum.