摘要:

In this paper we present algorithms for the problem of scheduling n independent jobs on m identical machines. As a generalization of the classical multiprocessor scheduling problem each machine is available only at a machine dependent release time. Two objective functions are considered. To minimize the makespan, we develop a dual approximation algorithm with a worst case bound of 5/4. For the problem of maximizing the minimum completion time, we develop an algorithm, such that the minimum completion time in the schedule produced by this algorithm is at least 2/3 times the minimum completion time in the optimum schedule. The paper closes with some numerical results.

ISSN:0740-817X    

DOI:10.1080/07408179808966555

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

Asynchronous production systems are classified into systems with fixed, unrestricted, and restricted work-in-process inventory. For each class routing optimization models are presented. Furthermore, extensions are provided in order to include optimal lotsizing and/or part mix decisions. These extensions find optimal solutions for two previously published problems with only heuristic solution procedures.

ISSN:0740-817X    

DOI:10.1080/07408179808966556

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

The Economic Lot Scheduling Problem (ELSP) is the problem of scheduling production of several items in a single facility, so that demands are met without stockouts or backorders, and the long run average inventory carrying and setup costs are minimized. One of the general assumptions in the ELSP is that the yield rates of a given manufacturing process are constant, or 100%, after setup. However, this assumption may not be true for certain manufacturing processes, in which the yield rates are quite low just after setup, and then increase over time. This period is called a stabilization period and yield rates gradually increase during this period until they reach the target rates, which are set empirically or strategically. The purpose of this paper is to clarify the effect of the stabilization period by applying the stabilization period concept to the ELSP, which has been widely applied to many production systems. In this paper, the problem is tackled in three stages: Firstly, we formulate a model and develop an algorithm, which provides a lower bound for a minimum cost. Secondly, we develop a heuristic procedure using the time-varying lot size approach. Finally, we solve a special case of the ELSP to find an upper bound using the common cycle approach.

ISSN:0740-817X    

DOI:10.1080/07408179808966557

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

This paper analyzes a problem of optimal inspection intervals for a failure-prone batch production facility. The model makes a seemingly minor modification to similar models that have appeared recently, but which results in a significant change in the form of the optimal policy. Optimal solutions are developed for both continuous and integer valued sublot sizes. The paper also examines the effects of inspection sublots in an economic lot sizing context and shows that a simple, exact modification of the Economic Production Quantity formula is often possible in the continuous relaxation of the problem.

ISSN:0740-817X    

DOI:10.1080/07408179808966558

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

In this paper we consider periodic review systems under stochastic demands. First, we study the single product periodic review problem and propose a simple solution procedure which is near optimal. Then, given the existence of this simple procedure, we study the joint replenishment problem for multiple items under stochastic demands and suggest simple heuristics which provide very good results. We find the simple procedures combined with the robustness of the cost function to be very attractive in other applications which require coordination of cycle times under stochastic demands.

ISSN:0740-817X    

DOI:10.1080/07408179808966559

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

The importance and benefits of using multiple-load carriers in advanced manufacturing systems has been well documented in recent studies. This study assumes a manufacturing system arranged around a single loop serviced by a single multiple-load carrier. The study presents a {0-1} integer programming model for optimal schedule design, if complete knowledge is available, using a finite planning horizon. In order to solve larger dynamic problems where jobs keep on arriving, two heuristic algorithms are developed, each using a different look-ahead period. The ability of these algorithms is analyzed and compared to the simple First-Encountered-First-Served (FEFS) rule using 31 randomly generated problems. Finally, the impact of increasing carrier capacity is studied.

ISSN:0740-817X    

DOI:10.1080/07408179808966560

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

In this paper, we consider the inventory control problem in a periodic review returnable system. In a returnable system, containers are returned by consumers to the manufacturer for reuse. We view the returns in a given period to be a stochastic function of the number of containers out in the field. Using dynamic programming, we derive the optimal inventory control policy for the system.

ISSN:0740-817X    

DOI:10.1080/07408179808966561

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

Purchase price reductions, even on a one-time-only basis, allow retailers the opportunity to lower their own selling prices, albeit temporarily, in an effort to increase sales. This results in not only additional revenues but also in extra inventory costs. The model presented in this paper examines such a cost/revenue tradeoff, through simultaneous determination of the most profitable: (i) stock level to be purchased by the retailer; (ii) discount level to be passed on to the customers; (iii) stock level qualifying for the retailer's discount; and (iv) time to initiate the discount. Numerical examples are included throughout to illustrate the main features of the model.

ISSN:0740-817X    

DOI:10.1080/07408179808966562

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

In this paper, we consider two equivalent differentiable reformulations of the nondifferentiable Euclidean multifacility location problem (EMFLP). The first of these is derived via a Lagrangian dual approach based on the optimum of a linear function over a unit ball (circle). The resulting formulation turns out to be identical to the known dual problem proposed by Francis and Cabot [1]. Hence, besides providing an easy direct derivation of the dual problem, this approach lends insights into its connections with classical Lagrangian duality and related results. In particular, it characterizes a straightforward recovery of primal location decisions. The second equivalent differentiable formulation is constructed directly in the primal space. Although the individual constraints of the resulting problem are generally nonconvex, we show that their intersection represents a convex feasible region. We then establish the relationship between the Karush-Kuhn-Tucker (KKT) conditions for this problem and the necessary and sufficient optimality conditions for EMFLP. This lends insights into the possible performance of standard differentiable nonlinear programming algorithms when applied to solve this reformulated problem. Some computational results on test problems from the literature, and other randomly generated problems, are also provided.

ISSN:0740-817X    

DOI:10.1080/07408179808966563

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor

摘要:

Lot streaming is the process of splitting a job or lot to allow overlapping between successive operations in a multistage production system. This use of transfer lots usually results in a significantly shorter makespan for the schedule. We study the structural properties of schedules which minimize the makespan for a single job with attached setup times in a flow shop. The structure of the optimal schedules is more complex than in the case with no setups or detached setups, as it may follow a much larger variety of patterns. Using the structural insights obtained, however, it is possible to find the optimal solution with s sublots inO(s) time for the three-machine case.

ISSN:0740-817X    

DOI:10.1080/07408179808966564

出版商:Taylor & Francis Group    

年代:1998

数据来源: Taylor