Parallel flowshop scheduling using Tabu search

Production scheduling problems in manufacturing systems with parallel machine flowshops are discussed. A mathematical programming model for combined part assignment and job scheduling is developed. The objective of solving the scheduling problem is to minimize a weighted sum of production cost and the cost incurred from late product delivery. The solution of the model is NP-hard. To solve the problem efficiently, a heuristic algorithm combining Tabu search and Johnson's method was proposed. Several numerical examples are presented to illustrate the developed model and the algorithm. Computational results from these example problems are very encouraging.     

Prescribed error tolerances within fixed computational times for scattering problems of arbitrarily high frequency: the convex case

We present a new algorithm for the numerical solution of problems of electromagnetic or acoustic scattering by large, convex obstacles. This algorithm combines the use of an ansatz for the unknown density in a boundary-integral formulation of the scattering problem with an extension of the ideas of the method of stationary phase. We include numerical results illustrating the high-order convergence of our algorithm as well as its asymptotically bounded computational cost as the frequency increases.     

Infinite horizon production planning with periodic demand: solvable cases and a general numerical approach

In this paper, we consider a single part-type pull manufacturing system, which controls its production rates in response to periodic demand. When tracking the demand results in a product surplus, an inventory storage cost is incurred. Likewise, if an overall shortage occurs then a backlog cost is paid. In addition, production costs accrue when the system is not idle. Given an infinite planning horizon, the objective is to determine the cyclic production rates in order to minimize the total cost. With the aid of the maximum principle, extremal behavior of the system is studied and the continuous-time production planning problem is reduced to a discrete problem with a limited number of switching points at which time the production rates change. Using this result, an efficient numerical algorithm is proposed, which will yield an approximation to the optimal solution within any desired level of accuracy. In addition, we determine the analytical solution to the problem for three special cases: (i) the system capacity is not limited and the inventory storage cost factor is equal to the backlog cost factor; (ii) the production cost is negligible; and (iii) the surplus and shortages costs are negligible.     

Development of a production inventory model with uncertainty and reliability considerations

This paper addresses a problem of an imperfect production system under fuzzy demand and inventory holding cost. Production process reliability is considered because of the imperfect production process. In this problem, reliability of the system in regards to producing defective and non-defective items is considered as a decision variable. The objective is to maximize the graded mean integration value (GMIV) of the expected average profit while considering revenues as well as any other relevant costs. The developed model belongs to the class of a geometric programming. We have developed a simple mathematical methodology to solve the model. Genetic algorithm and simulated annealing algorithms are also applied to solve and validate the results. A numerical example has been presented to interpret the solutions.     

SYNTHESIS OF KANBAN CONTROL POLICIES FOR MULTI-STAGE JUST-IN-TIME ASSEMBLY SYSTEMS

This paper studies the problem of determining the number of Kanbans that should be assigned to each production slage of a multi-stage assembly system in a just-in-time production environment. The objective is to minimize the inventory cost of the system. A new algorithm is developed as a means of solving such a problem. The approach is described in some detail and the theoretical results obtained are illustrated by using a numerical example. A set of randomly generated test problems are also included to illustrate the performance of the algorithm. The results show that the algorithm proposed in this paper is indeed superior both in terms of minimizing Ihe required amount of computational effort and improving accuracy.     

Storage Decisions in Information Systems

The problem is to dynamically store different data records in different storage devices in each period so as to minimize the total expected discounted cost over a planning horizon. Each device has a fixed total capacity, each record has a given storage space requirement, while the number of requests for each record per period is changing stochastically through time. Given an allocation, the total cost per period consists of the storage cost (depending on the storage requirements and device), the access cost including update and retrieval costs (depending on the number of requests) and the transfer cost (depending upon the change of allocation from the previous period). A dynamic programming model is presented to yield optimal strategies. The special case of independent identically distributed demands is completely solved, using a generalized transportation algorithm while a heuristic procedure is indicated for the general problem using parametric analysis.     

Forward-in-time goal-oriented adaptivity

In goal-oriented adaptive algorithms for partial differential equations, we adapt the finite element mesh to reduce the error of the solution in some quantity of interest. In time-dependent problems, this adaptive algorithm involves solving a dual problem that runs backward in time. This process is, in general, computationally expensive in terms of memory storage. In this work, we define a pseudo-dual problem that runs forward in time. We also describe a forward-in-time adaptive algorithm that works for some specific problems. Although it is not possible to define a general dual problem running forwards in time that provides information about future states, we provide numerical evidence via one-dimensional problems in space to illustrate the efficiency of our algorithm as well as its limitations. Finally, we propose a hybrid algorithm that employs the classical backward-in-time dual problem once and then performs the adaptive process forwards in time.     

Modelling and design for a shuttle-based storage and retrieval system

The shuttle-based storage and retrieval system (SBS/RS) is a relatively new part-to-picker order picking system. We have developed a performance estimation and design algorithm for the SBS/RS. The performance estimation is based on a queuing model. The design algorithm aims to find the minimum cost configurations in terms of number of tiers, aisles, lifts and workstations with given throughput, tote capacity and order cycle time requirements. We used simulation driven by parameters abstracted from an actual SBS/RS to verify the performance estimation, and applied the design algorithm in the case study. The results indicate that: (1) compared to simulation results, the throughput of the performance estimation is nearly identical when the arrival rate is below the maximum capacity; (2) the design algorithm yields a configuration with 28.1% cost reduction in the current system. In addition, we also compared the shuttle system with the competing robotic order fulfilment system (robotic system in short) in terms of facility cost, building cost and order cycle time. We found that the shuttle system is a better choice if large storage capacity and high throughput are required whereas the robotic order fulfilment system performs better if small storage capacity and low throughput are required.     

Ant colony optimisation algorithm for distribution-allocation problem in a two-stage supply chain with a fixed transportation charge

In a fixed charge transportation problem, each route is associated with a fixed charge (or a fixed cost) and a transportation cost per unit transported. The presence of the fixed cost makes the problem difficult to solve, thereby requiring the use of heuristic methods. In this paper, an algorithm based on ant colony optimisation is proposed to solve the distribution-allocation problem in a two-stage supply chain with a fixed transportation cost for a route. A numerical study on benchmark problem instances has been carried out. The results obtained for the proposed algorithm have been compared with that for the genetic algorithm-based heuristic currently available in the literature. It is statistically confirmed that the proposed algorithm provides significantly better solutions.     

多种易变质性物品集中采购成本优化

将库存损失量看作是存贮时间和库存水平的函数,研究了一次集中采购多种易变质性物品的成本优化问题,分析了总成本的构成,以总成本最小化为目标,建立了该问题的混合整数规划模型,并给出了一种该模型的求解方法,计算实例验证了该方法的有效性.     

Process tolerance allocation in angular tolerance charting

The paper deals with the process tolerance allocation problem for manufacturing a product with angular features in two-dimensional angular tolerance charting. First, a discrete interval cost–tolerance model is investigated to represent the relationship between manufacturing cost and tolerance. Then a multichoice knapsack model is formulated to allocate systematically the best tolerance to each individual machining dimension in both radial and axial directions with the objective of minimizing the total manufacturing cost. Furthermore, a genetic algorithm is developed to obtain the optimal solution to the multichoice knapsack model. Finally, a numerical example is presented to illustrate the model and the approach developed.     

Harmony search optimization algorithm for a novel transportation problem in a consolidation network

This article presents a new harmony search optimization algorithm to solve a novel integer programming model developed for a consolidation network. In this network, a set of vehicles is used to transport goods from suppliers to their corresponding customers via two transportation systems: direct shipment and milk run logistics. The objective of this problem is to minimize the total shipping cost in the network, so it tries to reduce the number of required vehicles using an efficient vehicle routing strategy in the solution approach. Solving several numerical examples confirms that the proposed solution approach based on the harmony search algorithm performs much better than CPLEX in reducing both the shipping cost in the network and computational time requirement, especially for realistic size problem instances.     

A Sequential Bounding Approach for Optimal Appointment Scheduling

This study is concerned with the determination of optimal appointment times for a sequence of jobs with uncertain durations. Such appointment systems are used in many customer service applications to increase the utilization of resources, match workload to available capacity, and smooth the flow of customers. We show that the problem can be expressed as a two-stage stochastic linear program that includes the expected cost of customer waiting, server idling, and a cost of tardiness with respect to a chosen session length. We exploit the problem structure to derive upper bounds that are independent of job duration distribution type. These upper bounds are used in a variation of the standard L-shaped algorithm to obtain optimal solutions via successively finer partitions of the support of job durations. We present new analytical insights into the problem as well as a series of numerical experiments that illustrate properties of the optimal solution with respect to distribution type, cost structure, and number of jobs.     

Routing problem under the shared storage policy for unit-load automated storage and retrieval systems with separate input and output points

In this study the routing problem for unit-load automated storage and retrieval systems (AS/RSs) with separate input and output points is considered under the shared storage policy. The problem is to find an optimal travel route of a S/R (storage and retrieval) machine to process given storage and retrieval requests so that the total travel time is minimised, where the input and output points are possibly separate and the shared storage policy is assumed. We first give two types of formulations as 0–1 integer linear programming problems corresponding to two types of dwell point settings: the dwell point is the input point and the output point. Next, we propose a simple but efficient exact solution algorithm based on the formulations that utilises a general MILP (Mixed Integer Linear Programming) solver. Its efficiency is then demonstrated by numerical experiments. Instances with 400 items (200 for each storage and retrieval) are solved within 100 s.     

Newsvendor problem with multiple unreliable suppliers

This paper focuses on supplier-related decisions in a newsvendor setting. We build upon the current literature by analysing the newsvendor problem with multiple unreliable and non-identical suppliers. We also incorporate both fixed ordering costs and capacity limits for supplier selection. We develop an exact algorithm to solve the problem optimally and a heuristic algorithm to solve the problem efficiently. Through structural properties of the optimal solution and a numerical study, we provide useful managerial implications regarding optimal sourcing strategies in complex supply chains. Previous literature concludes that with multiple unreliable (independent) suppliers, cost is the order qualifier and reliability is the order winner. We found that when fixed ordering costs and supply capacities exist, this insight no longer holds. We also examine the sensitivity of the sourcing decisions to supplier capacity levels, demand uncertainty, salvage value and shortage cost. Our results show that high levels of demand uncertainty lead firms to turn to a single-sourcing strategy whereas high salvage values and high shortage cost suggest multi-sourcing strategy.     

AN OPERATION-SEQUENCE-BASED APPROACH IN DESIGNING A FLOW LINE INDEPENDENT-CELL SYSTEM WITH MACHINE CAPACITY INCORPORATED

This paper considers a problem of designing a flow line independent-cell system where each machine can treat multiple production operations and at most two machines of each machine type can be installed in the same cell. The objective is to minimize the total system cost including machine cost and material handling cost subject to each cell capacity. The problem is characterized as NP-hard. Therefore, in order to find a good solution efficiently, this paper proposes two greedy-type heuristic algorithms including a single-combining algorithm and a double-combining algorithm. Both the algorithms are derived by using the process of combining the cells and are tested for their efficiencies with various numerical problems.     

The Joint Replenishment Problem with a Powers-of-Two Restriction

In this paper we consider the joint replenishment problem in the light of recent work by the second and third authors concerning the selection of realistic and consistent reorder intervals in production/ distribution systems. After stating a general dynamic programming formulation of the joint replenishment problem, we present its usual statement which assumes constant reorder intervals. We then restrict the problem further by assuming the constant reorder intervals are powers-of-two multiples of some base planning interval. We present an algorithm based on concepts we developed that solves the joint replenishment problem with the powers-of-two restriction. Like other algorithms proposed for this problem, it is a simple sorting algorithm. Finally, we establish that the algorithm yields a solution whose average annual cost is within 6% of the general problem's long-run minimum average annual cost.     

Partner selection model for design chain collaboration

Due to increasing global competition and shorter new product life cycles, brand owners collaborate more often with design chain partners to bring a new product to market. This paper proposes a design partner selection model to minimise the overall design chain cost, taking into account communication cost, time-to-market, and quality. The model can be formulated as a stagecoach problem. Next, a dynamic programming algorithm is developed for this model to select the optimal partners through the design chain. Finally, a numerical example and a sensitivity analysis are presented. The results also reveal that design quality and manufacturing quality positively influence the total cost, and when brand owners need to speed up time-to-market to keep up with a competitor, the design quality will become less important.     

On the Use of A Vehicle Routing Algorithm for the Parallel Processor Problem with Sequence Dependent Changeover Costs

We consider the problem of sequencing a set of changeover dependent jobs in a parallel processor shop subject to a workload restriction where the objective is to achieve minimum total changeover cost. A heuristic algorithm, developed previously to treat the vehicle delivery model, is used on the problem. Suitable computational experience with the algorithm is provided the results of which would support its application to problems of realistic size.     

An effective methodology for the stochastic project compression problem

In this paper, we consider the problem of planning a complex project when task durations are random. Specifically, we consider the problem of deciding how much to compress tasks in order to minimize the expected total cost that is defined by the sum of direct, indirect, and incentive costs. We initially consider this problem under the assumption that task durations can be modeled by a negative exponential distribution although we later relax this assumption and show that our methodology can be applied to any general distribution. To solve this problem, we develop an effective heuristic algorithm that we call the Stochastic COmpression Project (SCOP) algorithm; the SCOP algorithm is straightforward to implement and our numerical tests indicate that the algorithm performs significantly better than previously reported heuristics. In addition, we compare our approach to solutions found using expected values embedded in a deterministic approach (an approach that is frequently used to solve this problem in practice). Using our results, we show that the deterministic approximation approach, such as the classic PERT model, provides biased results and should be avoided.