The Theory of a Method of Production Scheduling When there are Many Products

Suppose that there is a single-stage process, possibly with several machines in parallel. Each machine can produce a variety of products and a change of product can, at a cost, be made without restriction. It is assumed that, because of random variations in sales rates, a cyclic scheme of production is not practicable. A modification of the classical square-root formula for lot-size is found that allows for the “interference” between different products. Numerical examples are given in section 8 and the general conditions under which the scheduling scheme of this paper is likely to be efficient are discussed in section 9.     

Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time

We are interested in the problem of scheduling orders for different product types in a facility with a number of machines in parallel. Each order asks for certain amounts of various different product types which can be produced concurrently. Each product type can be produced on a subset of the machines. Two extreme cases of machine environments are of interest. In the first case, each product type can be produced on one and only one machine which is dedicated to that product type. In the second case, all machines are identical and flexible; each product type can be produced by any one of the machines. Moreover, when a machine in this case switches over from one product type to another, no setup is required. Each order has a release date and a weight. Preemptions are not allowed. The objective is minimizing the total weighted completion time of the orders. Even when all orders are available at time 0, both types of machine environments have been shown to be NP-hard for any fixed number (≥2) of machines. This paper focuses on the design and analysis of approximation algorithms for these two machine environments. We also present empirical comparisons of the various algorithms. The conclusions from the empirical analyses provide insights into the trade-offs with regard to solution quality, speed, and memory space. Electronic Supplementary Material The online version of this article () contains supplementary material, which is available to authorized users. This research is supported by the National Science Foundation through grants DMI-0300156 and DMI-0245603.     

Production planning problem with sequence dependent setups as a bilevel programming problem

Each of n products is to be processed on two machines in order to satisfy known demands in each of T periods. Only one product can be processed on each machine at any given time. Each switch from one item to another requires sequence dependent setup time. The objective is to minimize the total setup time and the sum of the costs of production, storage and setup. We consider the problem as a bilevel mixed 0–1 integer programming problem. The objective of the leader is to assign the products to the machines in order to minimize the total sequence dependent setup time, while the objective of the follower is to minimize the production, storage and setup cost of the machine. We develop a heuristics based on tabu search for solving the problem. At the end, some computational results are presented.     

Scheduling orders for multiple product types to minimize total weighted completion time

We consider the problem of scheduling orders for multiple different product types in an environment with m dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the m dedicated machines; that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number (?2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space.     

Hierarchical production control of a flexible manufacturing system

A hierarchical production control framework for a flexible manufacturing system is proposed. The machines in the system are subject to failures in a wide spectrum band. At first, failures are clustered near some discrete points on the failure spectrum in order to define the hierarchical model. Each level in the hierarchy corresponds to a discrete point on the failure spectrum. At each level, faster varying failures are modelled by their mean behaviour, and more slowly varying failures are treated as static. Then, a hierarchical controller of multiple time scale type is proposed. System control at each level is based on the work of Kimemia and Gershwin. Simulation results conclude the paper.     

带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

Production variability in manufacturing systems: Bernoulli reliability case

The problem of production variability in serial manufacturing lines with unreliable machines is addressed. Bernoulli statistics of machine reliability are assumed. Three problems are considered: the problem of production variance, the problem of constant demand satisfaction, and the problem of random demand satisfaction generated by another (unreliable) production line. For all three problems, bounds on the respective variability measures are derived. These bounds show that long lines smooth out the production and reduce the variability. More precisely, these bounds state that the production variability of a line with many machines is smaller than that of a single machine system with production volume and reliability characteristics similar to those of the longer line. Since all the variability measures for a single machine line can be calculated relatively easily, these bounds provide analytical tools for analysis and design of serial production lines from the point of view of the customer demand satisfaction.     

Large-scale capacitated part-routing in the presence of process and routing flexibilities and setup costs

We develop a Lagrangean relaxation-based heuristic procedure to generate a near-optimal solution to large-scale capacitated part-routing problems through a cellular manufacturing system with both routing flexibilities and setup times. Several alternate process plans exist for each product. Any given operation can be performed on alternate machines at different costs. The part demands can be satisfied from internal production or through outsourcing. The objective is to minimize the total material handling, production, outsourcing, and setup costs, subject to satisfying all the part demands and not exceeding any of the machine capacity limits. Our computational experiments show that large problems involving several thousand products and decision variables can be solved in a reasonable amount of computer time to within 1% of their optimal solutions. The proposed procedure is general enough to be applied directly or with slight modifications to real-life, industrial-sized problems.     

An approximation algorithm for parallel machine scheduling with a common server

In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem.     

Flow-shop scheduling with setup and assembly operations

A scheduling model for a production system including machining, setup and assembly operations is considered. Production of a number of single-item products is ordered. Each product is made by assembling a set of several different parts. First, the parts are manufactured in a flow-shop consisting of multiple machines. Then, they are assembled into products on a single assembly stage. Setup operation and setup time are needed when a machine starts processing the parts or it changes items. The operations are partitioned into several blocks. Each block consists of the machining operations, the setup operations, and the assembly operation(s) for one or several products. The parts of the same item in a block are processed successively. The objective function is the mean completion time for all products. We consider a problem to partition the operations into blocks and sequence the parts in each block so as to minimize the objective function. Solution procedures using pseudo-dynamic programming and a branch-and-bound method are proposed. Computational experiments are carried out to evaluate the performance of the solution procedures. It has been found that a good near-optimal schedule is obtained efficiently by the proposed solution procedures.     

On unit time open shops with additional restrictions

We consider open shop problems with unit processing times,n jobs have to be processed onm machines. The order in which a given job is processed on the machines is not fixed. For each job a release time or a due date may be given. Additional, we consider the restriction that every machine must perform all corresponding operations without any delay time. Unit time open shop problems with release times to minimize total completion time were unsolved up to now for both allowed and forbidden delay times. We will solve these problems in the case of two and three machines. Furthermore we will give polynomial algorithms for several no-delay-problems with due dates.     

Batching deteriorating items with applications in computer communication and reverse logistics

We study two deterministic scheduling problems that combine batching and deterioration features. In both problems, there is a certain demand for identical good quality items to be produced in batches. In the first problem, each batch is assigned an individual machine that requires a cost and a time to be activated. All the machines are identical, work in parallel, and always produce good quality items. All the items are available at time zero and they deteriorate while waiting for production. Deterioration results in a linear increase of time and cost of production. In the second problem, there is a single machine that produces good quality as well as defective items in batches. Each batch is preceded by a setup time and requires a setup cost. Defective items have to be reworked on the same machine. They deteriorate while waiting for rework. At a time to be decided, the machine switches from production to rework defective items of the current batch. After rework, every defective item has the required good quality. In both problems, the objective is to find batch partitioning such that a linear combination of the production cost and production completion time is minimized. The two problems are observed at computer service providers and also reverse logistics. In computer service providers, machines and items correspond to communication service channels and information transfer tasks, respectively. We reduce both problems to minimizing a function of one variable representing the number of batches. In an optimal solution of either problem, there are at most two different batch sizes. Linear time algorithms are proposed for both problems.     

Scheduling jobs with release dates,equal processing times,and inclusive processing set restrictions

We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n²+mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.     

需要安装时间的两台多功能机排序问题的计算复杂性

提出需要安装时间的多功能机排序问题,一般情况下,这是NP-困难的;主要研究只有两台机器时一些特殊情况下的计算复杂性.根据加工集合为机器全集的工件组数的不同,分别给出多项式时间算法和分枝定界算法.对各工件组的工件数和加工时间都相等的情况,给出一个多项式时间的最优算法-奇偶算法,从而证明此问题是多项式时间可解的.     

Resource leveling in a machine environment

We address resource leveling problems in a machine environment. Given a set of m machines, one or more renewable resources, and a set of n tasks, each assigned to exactly one of the machines. Each task has a processing time, an earliest start time, a deadline, and resource requirements. There are no precedence relations between the tasks. The tasks have to be sequenced on the machines while minimizing a function of the level of resource utilization from each resource over time. We provide various complexity results including a polynomial time algorithm for a one machine special case. We also propose an exact method using various techniques to find optimal or close-to-optimal solutions. The computational experiments show that our exact method significantly outperforms heuristics and a commercial MIP solver.     

Joint effect of stock threshold level and production policy on an unreliable production environment

In this article we develop an economic manufacturing quantity (EMQ) model subject to stochastic machine breakdown, repair and stock threshold level (STL). Instead of constant production rate, in this model production rate is considered as a decision variable. Since, the stress of the machine depends on the production rate, failure rate of the machine will be a function of the production rate. Again, in this article consideration of safety stock in all existing literature is replaced by the concept of stock threshold level (STL). Further, extra capacity of the machine is considered to buffer against the possible uncertainties of the production process where machine capacity is predetermined. The basic model is developed under general failure and general repair time distributions. Since, the assumption of variable production rate makes the objective function quite complex, so main emphasis is given on computational methodology to solve the present problem. We suggest two computational algorithms for the determination of production rate and stock threshold level which minimize the expected cost rate in the steady state. Finally, through numerical examples we illustrate the key insights of our model from managerial point of view.     

Scheduling dynamic hybrid flowshop with serial batching machines

This paper considers a multi-stage dynamic hybrid flowshop in which some stage contains several identical batching machines and the other stages contain several identical discrete machines. Each discrete machine can process no more than one operation at a time, and each batching machine can process several jobs continuously in a batch. This problem has a strong practical background in the process industry. Since the problem is NP-hard, improved Lagrangian relaxation (LR) is developed where batch decomposition strategy is applied and mixed backward and forward dynamic programming is designed to solve batch-level subproblems with the case that each operation may have multiple predecessors and successors. Results of numerical experiments with up to 60 jobs show that the proposed algorithm can obtain better solutions in a reasonable computation time than traditional LR.     

Representation and analysis of transfer lines with machines that have different processing rates

A transfer line is a tandem production system, i.e. a series of machines separated by buffers. Material flows from outside the system to the first machine, then to the first buffer, then to the second machine, the second buffer, and so forth. In some earlier models, buffers are finite, machines are unreliable, and the times that parts spend being processed at machines are equal at all machines. In this paper, a method is provided to extend a decomposition method to large systems in which machines are allowed to take different lengths of time performing operations on parts. Numerical and simulation results are provided.     

Determining Economic Maintenance Frequency for a Family of Machines

This paper deals with the problem of determining economic maintenance frequency for a group of machines. The operating cost for each machine is assumed to increase with time since the last maintenance work carried out on the machine. The cost of carrying out maintenance work is known and assumed constant. A fixed cost is incurred whenever maintenance work is carried out, and this fixed cost is assumed to be independent of the number of machines on which maintenance work is carried out. The total cost of the system is given by the sum of maintenance and operating costs for all the machines. A heuristic method is proposed for determining the economic maintenance frequency of each machine. An example is given to illustrate the method.     

A polynomially solvable case of the three machine johnson problem

Under study is the classical NP-hard problem with three machines: N tasks must be fulfilled at three machines in minimum time. The processing time is given of each task at each machine. The processing sequences of all tasks are identical. It is impossible to process two tasks at one machine at the same time. We address the properties of this problem, find a new polynomially solvable case, and discuss a corresponding algorithm.