An optimal product-reconfiguration policy due to order changes

Abstract

It is not an uncommon problem that a finished product cannot be delivered to its customer due to order change. In many real-life applications, such as rack-mounted computer products, it is possible to reconfigure a product by altering the combination of its components. Therefore, an inventory item, resulting from a cancelled order, can be handled in one of two ways: (1) keep the product in storage for a future order; or (2) send the product back to the manufacturing Door for reconfiguration in accordance with a new order A wise decision can be made by evaluating the trade-off between the inventory cost and the conversion cost. This paper presents an optimization procedure for achieving the minimum-cost solution. The problem is formulated by a quadratic programming model. Under a fairly general condition, the problem can be converted into a standard capacitated transportation problem and, therefore, can be solved efficiently. The cost structure, problem formulation, and solution technique arc discussed.     

Simplest strategies method for manufacturing workcell restoration

We consider the production process of a manufacturing workcell. Production items obtained from an outside supplier are not processed adequately as far as their quality is concerned. Production items meeting the required quality depend on the workcell state, which degrades according to the number of produced items. The workcell is completely restored by some restoring operations leading to its as-new condition. The method of deriving the restoration period, which leads to the maximum probability that produced items meet the required quality, is introduced. It is based on the nontraditional approach, i.e. on the simplest strategies method for the formulation of the problem presented here. The implementation of this optimization approach is illustrated with an example.     

Probabilistic graph-coloring in bipartite and split graphs

We revisit in this paper the stochastic model for minimum graph-coloring introduced in (Murat and Paschos in Discrete Appl. Math. 154:564–586, 2006), and study the underlying combinatorial optimization problem (called probabilistic coloring) in bipartite and split graphs. We show that the obvious 2-coloring of any connected bipartite graph achieves standard-approximation ratio 2, that when vertex-probabilities are constant probabilistic coloring is polynomial and, finally, we propose a polynomial algorithm achieving standard-approximation ratio 8/7. We also handle the case of split graphs. We show that probabilistic coloring is NP-hard, even under identical vertex-probabilities, that it is approximable by a polynomial time standard-approximation schema but existence of a fully a polynomial time standard-approximation schema is impossible, even for identical vertex-probabilities, unless P=NP. We finally study differential-approximation of probabilistic coloring in both bipartite and split graphs. Part of this research has been performed while the second author was with the LAMSADE on a research position funded by the CNRS.     

The orbit problem is in the GapL hierarchy

The Orbit problem is defined as follows: Given a matrix A∈ℚ ^n×n and vectors x,y∈ℚ ⁿ , does there exist a non-negative integer i such that A ⁱ x=y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton (J. ACM 33(4):808–821, 1986). In this paper we place the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for C₌L with respect to logspace many-one reductions.     

The shortest path improvement problems under Hamming distance

In this paper, we consider the shortest path improvement problems under Hamming distance (SPIH), where the weights of edges can be modified only within given intervals. Two models are considered: the general SPIH problem and the SPIH problem with a single pair of required vertices. For the first problem, we show that it is strongly NP-hard. For the second problem, we show that even if the network is a chain network, it is still NP-hard.This paper is dedicated to Dr. Yong He.     

Production scheduling for apparel manufacturing systems

In this paper, we model an apparel manufacturing system characterized by the co-existence of the two production lines, i.e. traditional, long lead time production line and flexible, short lead time production line. Our goal is to find strategies which decide: (i) the fraction of the total production capacity to be allocated to each individual line, and (ii) the production schedules so as to maximize the overall profits. In this problem, searching for the best solution is prohibited in view of the tremendouscomputing budget involved. Using ordinal optimization ideas, we obtained very encouraging results not only have we achieved a high proportion of 'good enough' designs but also tight profit margins compared to a pre-calculated upper bound. There is also a saving of at least 1/2000 of the computation time.     

A combined optimization and agent-based approach to supply chain modelling and performance assessment

The main objective of this paper is to give an example of how expert systems techniques for distributed decision-making can be combined with contemporary numerical optimization techniques for the purposes of supply chain optimization and to describe the resulting software implementation. In this paper, multi-agent modelling techniques are applied to simulate and control a simple demand-driven supply chain network system, with the manufacturing component being optimized through mathematical programming. The system measures supply chain performance and the effect of different parameters in the replenishment control system, and can be used to simulate the behaviour of a system that uses optimization for part of its decision-making. The objective of this supply chain network system is to reduce operating cost, while maintaining a high level of customer order fulfilment.     

Experiences and issues in evaluating tool requirements using genetic algorithms

This paper is concerned with the optimization of tool requirements in flexible manufacturing systems (FMSs). The main aim is to determine the best tool spectrum (i.e. the number of duplicates for each tool type to be provided) considering different layouts of the tool management area (tool rooms). The optimization method is based on the reciprocal interaction between a genetic algorithm (GA) and the simulation model of the FMS considered. Thus, the results proposed refer to the efficacy of the technique adopted and its practical application to tool management.     

Hospital resident scheduling problem

This paper addresses the resident scheduling problem (RSP) at hospitals concerned with prescribing work-nights for residents while considering departmental staffing and skill requirements as well as residents' preferences. Three scenarios that represent most situations and account for various departmental requirements and needs are described. Although similar scheduling problems are considered in the literature, no analysis exists that adequately deals with the speciffic nature of this problem. The problem is modeled as a mixed-integer program and heuristic solution procedures are developed for the different identified scheduling scenarios. These procedures exploit the inherent network structure of the problem which is an important feature that enhances problem solvability. For the sake of comparison, the problem is also solved exactly via the CPLEX-MIP (version 6.0) package. The contribution of this work is important since many hospitals are still utilizing manual techniques in preparing their own schedules, expending considerable effort and time and yet contending with limited scheduling flexibility.     

Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N ² + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N ³) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal solution.     

Determining an Optimal Penetration Among Weighted Regions in Two and Three Dimensions

We present efficient algorithms for solving the problem of computing an optimal penetration (a ray or a semi-ray) among weighted regions in 2-D and 3-D spaces. This problem finds applications in several areas, such as radiation therapy, geological exploration, and environmental engineering. Our algorithms are based on a combination of geometric techniques and optimization methods. Our geometric analysis shows that the d-D (d = 2, 3) optimal penetration problem can be reduced to solving O(n ^2(d–1)) instances of certain special types of non-linear optimization problems, where n is the total number of vertices of the regions. We also give implementation results of our 2-D algorithms.     

Designing optimal routing strategies for a manufacturer: A case study

A study of the vehicle transportation system for a manufacturer is presented. An algorithm based on a dynamic programming model is developed so as to find the optimal transportation arrangements referring to the composition of the vehicles as well as the routing of these vehicles. The algorithm is run under the current condition as well as under a number of different scenarios. It is shown the algorithm can solve the problem with reduced computational complexity. The findings and suggestions resulting from the study can help the department manager in reviewing current operations arrangement and determining future operations arrangements.     

Some structural properties for the just-in-time level schedule problem

Just-in-time (JIT) is a pull concept applied mainly in repetitive manufacturing systems, and it is characterized by a scenario where only the required units are produced in the required quantities at the required times. It particularly aims at eliminating wastes associated with inventories in the system. A level schedule is desirable for a JIT assembly system, as it serves as an approximation for all forms of smoothing. The min-sum formulation of the assembly line level schedule problem is one of those that has been mainly used in the literature. Using this formulation as a base, we develop some useful structural properties for the problem. Among other things, it is shown that a level schedule would tend to be more difficult to achieve for products (models) with comparatively fewer units in the products composition structure.     

Flow shop scheduling by transportation model

This paper describes the classical problem of scheduling n jobs on m machines in a flow shop. A schedule evaluation algorithm is presented, which for job-pairs, generates a schedule evaluation matrix. The matrix is the input data to a transportation problem, the solution of which gives near-optimal jobsequence and makespan. The performance of the algorithm is discussed.     

Fuzzy multi-attribute decision-making for grouping of electronic components in process planning

The grouping of objects problem has a wide-range of applications in industry. In electronic assembly planning, grouping components play an important role as they can reduce drastically the number of possible sequences of operations. This paper considers the grouping problem of electronic component families based on their multiple attributes. The difficulty lies with the conflict of criteria when selecting a certain component into a group. In order to overcome this difficulty, the proposed approach introduces the concept of fuzziness, which expresses the degree of concordance on the decision. An example of classification electronic components is presented to illustrate the proposed method.     

Generalized Steiner Problems and Other Variants

In this paper, we examine combinatorial optimization problems by considering the case where the set N (the ground set of elements) is expressed as a union of a finite number of m nonempty distinct subsets N ₁,...,N _m. The term we use is the generalized Steiner problems coined after the Generalized Traveling Salesman Problem. We have collected a short list of classical combinatorial optimization problems and we have recast each of these problems in this broader framework in an attempt to identify a linkage between these “generalized” problems. In the literature one finds generalized problems such as the Generalized Minimum Spanning Tree (GMST), Generalized Traveling Salesman Problem (GTSP) and Subset Bin-packing (SBP). Casting these problems into the new problem setting has important implications in terms of the time effort required to compute an optimal solution or a “good” solution to a problem. We examine questions like “is the GTSP “harder” than the TSP?” for a number of paradigmatic problems starting with “easy” problems such as the Minimal Spanning Tree, Assignment Problem, Chinese Postman, Two-machine Flow Shop, and followed by “hard” problems such as the Bin-packing, and the TSP.     

Comparative evaluation of genetic algorithms for job-shop scheduling

Many optimization problems from the industrial engineering world, in particular the manufacturing systems, are very complex in nature and quite hard to solve by conventional optimization techniques. There has been increasing interest in imitating living beings to solve such kinds of hard optimization problems. Simulating the natural evolutionary process of human beings results in stochastic optimization tech niques called evolutionary algorithms, which can often outperform conventional optimization methods when applied to difficult real-world problems. There are currently three main avenues of this research: genetic algorithms (GAs), evolutionary programming (EP) and evolution strategies (ESs). Among them, genetic algorithms are perhaps the most widely known types of evolutionary algorithms today. During the past years, several GAs for the job-shop scheduling problems have been proposed, each with different chromosome representation. In this paper, the different GAs are collected from the literature and an attempt has been made to evaluate them. The benchmark problems available in open literature are used for evaluation and the performance measure considered is makespan. The algorithms are coded in C+ +.     

A heuristic algorithm for minimizing maintenance workforce level

We develop a heuristic algorithm for minimizing the workforce level required to accommodate all the maintenance jobs requested within a specific time interval. Each maintenance job has its own release and due dates as well as the required man-days, and must be scheduled in a noninterrupted time interval, i.e. without preemption. However, the duration of each job is not fixed, but to be determined within a specific range. We show that this problem can be seen as a variant of the two-dimensional bin-packing problem with some additional constraints. We develop a non-linear mixed integer programming model for the proposed problem, and employ some well-known bin-packing algorithms to develop an efficient heuristic algorithm. In order to evaluate the performance of the proposed heuristic, we present a computationally efficient scheme for getting a good lower bound for the actual minimum. The computational experiment shows that the proposed heuristic algorithm performs quite satisfactorily in practice.     

Approximation and hardness results for label cut and related problems

We investigate a natural combinatorial optimization problem called the Label Cut problem. Given an input graph G with a source s and a sink t, the edges of G are classified into different categories, represented by a set of labels. The labels may also have weights. We want to pick a subset of labels of minimum cardinality (or minimum total weight), such that the removal of all edges with these labels disconnects s and t. We give the first non-trivial approximation and hardness results for the Label Cut problem. Firstly, we present an \(O(\sqrt{m})\)-approximation algorithm for the Label Cut problem, where m is the number of edges in the input graph. Secondly, we show that it is NP-hard to approximate Label Cut within \(2^{\log ^{1-1/\log\log^{c}n}n}\) for any constant c<1/2, where n is the input length of the problem. Thirdly, our techniques can be applied to other previously considered optimization problems. In particular we show that the Minimum Label Path problem has the same approximation hardness as that of Label Cut, simultaneously improving and unifying two known hardness results for this problem which were previously the best (but incomparable due to different complexity assumptions).