A dynamic production planning and scheduling algorithm for two products processed on one line

This paper presents a dynamic production planning and scheduling algorithm for two products processed on one line over a fixed time horizon. Production rates are assumed fixed, and restrictions are placed or inventory levels and production run lengths. The resulting problem is a nonlinear binary program, which is solved using an implicit enumeration strategy. The algorithm focuses on the run changeover period while developing tighter bounds on the length of the upcoming run to improve computational efficiency. About 99% pf 297 randomly generated problems with varying demand patterns are solved in less than 15 seconds of CPU time on a CDC Cyber 172 Computer. A mixed integer programming formulation of the generalized multi-product case under no-backlogging of demand is also given.     

A multi-objective production scheduling case study solved by simulated annealing

During several decades, research in production scheduling mainly concerns a single criterion to optimize. However, the analysis of the performance of a schedule often involves more than one aspect and therefore requires multi-objective analysis. Such situation appears in the real case study considered here.     

A basic searchlight game

A searchlight game is a two-person zero-sum dynamic game of the pursuit-evasion type in which at least one of the two players has a searchlight. A searchlight can be flashed a given number of times within a fixed time period and the objective is to catch the opponent in the region illuminated by the flash. Olsder and Papavassilopoulos instituted the study of these games and, in this paper, we supplement their results, obtaining a closed formula for the value and optimal strategies for the players in their basic game.     

The project scheduling problem with production and consumption of resources: A list-scheduling based algorithm

The paper deals with algorithms for applying classical list scheduling to a project scheduling problem where the units of resources are produced or consumed at the occurrence of precedence-related events. It is shown that the feasibility variant of the project scheduling problem is NP-complete. Moreover, polynomial-time scheduling algorithms are devised for the three cases where the occurrence time sequence of all events or the consuming events or the producing events is given in advance. By enumerating these sequences (called linear orders), one obtains a list-scheduling based algorithm for minimizing the makespan of a project scheduling problem with production and consumption of resources.     

A stochastic production planning model with a dynamic chance constraint

This paper deals with the optimal production planning for a single product over a finite horizon. The holding and production costs are assumed quadratic as in Holt, Modigliani, Muth and Simon (HMMS) [7] model. The cumulative demand is compound Poisson and a chance constraint is included to guarantee that the inventory level is positive with a probability of at least α at each time point. The resulting stochastic optimization problem is transformed into a deterministic optimal control problem with control variable and of the optimal solution is presented. The form of state variable inequality constraints. A discussion the optimal control (production rate) is obtained as follows: if there exists a time t₁ such that t₁?[O, T]where T is the end of the planning period, then (i) produce nothing until t₁ and (ii) produce at a rate equal to the expected demand plus a ‘correction factor’ between t₁ and T. If t₁ is found to be greater than T, then the optimal decision is to produce nothing and always meet the demand from the inventory.     

Competitive Advertising Under Uncertainty: A Stochastic Differential Game Approach

We analyze optimal advertising spending in a duopolistic market where each firm's market share depends on its own and its competitor's advertising decisions, and is also subject to stochastic disturbances. We develop a differential game model of advertising in which the dynamic behavior is based on the Sethi stochastic advertising model and the Lanchester model of combat. Particularly important to note is the morphing of the sales decay term in the Sethi model into decay caused by competitive advertising and noncompetitive churn that acts to equalize market shares in the absence of advertising. We derive closed-loop Nash equilibria for symmetric as well as asymmetric competitors. For all cases, explicit solutions and comparative statics are presented.     

A dynamic solution in N-person cooperative game theory

We formulate a cooperative game as an extended form game in which each player in turn proposes payoffs to a coalition over M steps. Payoffs at time t are discounted by a penalty function f(t). If all players in a coalition agree to their payoffs, they receive them. Under a convergence hypothesis verified by computer for three players in many cases, we compute the payoffs resulting from a coalition pattern and give necessary conditions for particular patterns. The resulting solution is related to the Nash bargaining solution and the competitive solution.     

A markov chain game with dynamic information

Two players, not knowing each other's position, move in a domain and can flash a searchlight. The game terminates when one player is caught within the area illuminated by the flash of the other. However, if this first player is not in this area, then the other player has disclosed his position to the former one, who may be able to exploit this information. The game is considered on a finite state space and in discrete time.The work of the second author was supported by ZWO, The Netherlands Organization for the Advancement of Pure Research, Contract No. B62-239, by the US Air Force Office of Scientific Research, Grant No. AFOSR-85-0245, and by the National Science Foundation, Grant No. NSF-INT-8504097.Visiting Professor at Delft University of Technology during 1986.     

A differential game with jump process observations

We introduce a stochastic differential game with jump process observations. Both players obtain common, noisy information of the state of the system only at random time instants. The solutions to this game and its continuous observations in noise counterpart are obtained. Some earlier results dealing with the effect of changes in system parameters on the optimal cost for the continuous observations case are extended to the game with jump process observations.This work was supported by a 1978 Summer Faculty Fellowship from the University of Maryland, Baltimore County.     

A stochastic permutation-flowshop scheduling problem minimizing in distribution the schedule length

Consider n jobs (J₁,J₂,…,J_n) and m machines (M₁,M₂…,M_m). Upon completion of processing of J_i, 1 ? i ? n, on M_j 1 ? j ? m ? 1, it departs with probability p_i or moves to M_j+1 with the complementary probability, 1?p_i. A job completing service on M_m departs. The processing time of j_i on M_j possesses a distribution function F_j. It is proved that sequencing the jobs in a nondecreasing order of p_i minimizes in distribution the schedule length.     

A dynamic transfer scheme deriving from the dual similar associated game

Dynamic process is an approach to cooperative games, and it can be defined as that which leads the players to a solution for cooperative games. Hwang et al. (2005) adopted Hamiache’s associated game (2001) to provide a dynamic process leading to the Shapley value. In this paper, we propose a dynamic transfer scheme on the basis of the dual similar associated game, to lead to any solution satisfying both the inessential game property and continuity, starting from an arbitrary efficient payoff vector.     

Nonlinear programming and genetic search application for production scheduling in coal mines

Efforts to eliminate unnecessary scheduling and inventory problems faced by the coal industry today initiated the development of a generalized, nonlinear programming model. Although no accepted methodology for developing such a model for this purpose currently exists, one was created and successfully tested. Production and transportation cost estimates were obtained from independent coal mines in Illinois, Virginia, and Pennsylvania, and based on these estimates, a hypothetical model was developed and tested using genetic search for nonlinear optimization. The results of our tests indicate that the model has potential for decision support in coal mines.     

LP-based online scheduling: from single to parallel machines

We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-preemptive version of the problem, improving upon the 3.28-competitive algorithm of Megow and Schulz. Additionally, we show how to combine randomization techniques with the linear programming approach to obtain randomized algorithms for both versions of the problem with competitive ratio strictly smaller than 2 for any number of machines (but approaching two as the number of machines grows). Our algorithms naturally extend several approaches for single and parallel machine scheduling. We also present a brief computational study, for randomly generated problem instances, which suggests that our algorithms perform very well in practice. A preliminary version of this work appears in the Proceedings of the 11th conference on integer programming and combinatorial optimization (IPCO), Berlin, 8–10 June 2005.     

The stochastic economic lot scheduling problem: A survey

The present literature survey focuses on the stochastic economic lot scheduling problem (SELSP). The SELSP deals with the make-to-stock production of multiple standardized products on a single machine with limited capacity under random demands, possibly random setup times and possibly random production times. The main task of a production manager in this setting is the construction of a production plan for the machine. Based on the critical elements of such a production plan, we present a classification and extensive overview of the research on the SELSP together with an indication of open research areas. By doing so, we intend to stimulate the discussion on the important problems concerning the SELSP both from a theoretical and a practical point of view.     

A production scheduling heuristic for an electronics manufacturer with sequence-dependent setup costs

In this paper, we develop a three-step heuristic to address a production scheduling problem at a high volume assemble-to-order electronics manufacturer. The heuristic provides a solution for scheduling multiple product families on parallel, identical production lines so as to minimize setup costs. The heuristic involves assignment, sequencing, and time scheduling steps, with an optimization approach developed for each step. For the most complex step, the sequencing step, we develop a greedy randomized adaptive search procedure (GRASP). We compare the setup costs resulting from the use of our scheduling heuristic against a heuristic previously developed and implemented at the electronics manufacturer that assumes approximately equal, sequence-independent, setup costs. By explicitly considering the sequence-dependent setup costs and applying GRASP, our empirical results show a reduction in setups costs for an entire factory of 14–21% with a range of single production line reductions from 0% to 49%.     

Integrated production scheduling in large-scale flexible electronic parts manufacturing

This study reports the development of a production scheduling system for the integrated management of production in large-scale, high-volume electronic assembly lines. The development of the system incorporates control and planning considerations by addressing the interaction of various subsystems. Stochastic and deterministic aspects of the problem environment are appropriately handled via relevant simulation and analytic models. By effecting a hierarchical breakdown of the problem environment, the system produces information used in practical decision making for production planning and scheduling. Procedures used encompass and address considerations for management of work-in-process, optimization of the various subsystems' performance, minimization of setup time effect, and inventory carrying costs.     

A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case

In this paper we consider the problem of no-wait cyclic scheduling of identical parts in an m-machine production line in which a robot is responsible for moving each part from a machine to another. The aim is to find the minimum cycle time for the so-called 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. The earlier known polynomial-time algorithms for this problem are applicable only under the additional assumption that the robot travel times satisfy the triangle inequalities. We lift this assumption on robot travel times and present a polynomial-time algorithm with the same time complexity as in the metric case, O(m⁵logm).     

Real-time production scheduling of an automated cardline

In this paper, we describe a flow model of an automated-printed circuit card assembly line at the International Business Machines Corporation (IBM) plant at Tucson, Arizona. We use a simulation based on this model as a test bed to discuss the performance of a hierarchical scheduling policy described in [3]. We compare this with other policies for loading parts into a flexible manufacturing system. We demonstrate that the hierarchical strategy is effective in meeting production requirements (both total volume and balance among part types) while limiting average work-in-process (WIP). This is a consequence of the feedback nature of the policy. Hedging (i.e. building up buffer stock) compensates for machine failures, thus resulting in high production percentages. The work-in-process (WIP) is low, as the policy reduces internal queues by respecting the capacity constraints of the system at every instant.     

一种基于双链量子编码的动态车辆路径问题解决策略

针对配送调度事件动态变化的动态车辆路径问题(DVRP), 以最小化运输成本、最小化配送时间 与最大化载货率为目标, 建立了问题的数学模型,提出了改进的多相量子粒子群算法. 针对DVRP问题的特点,提出基于车辆链和货物链的双链量子编码方法; 同时设计了基于周期和 重调度因子驱动的动态调度策略. 最后将方法应用于动态仿真算例, 并与其他经典算法比较, 结果验证了所提出方法的有效性.