一种类微粒群算法及其在混流装配线调度问题中的应用

混流装配生产线的调度问题是准时化生产系统中最重要的问题之一.基于微粒群算法的原理,提出了一种类微粒群算法——PPSO(Pseudo Particle Swarm Optimization),可应用于解决准时化生产方式下的混流装配线调度问题.数值试验表明,采用PPSO方法比采用目标追随法、遗传算法和模拟退火算法的求解质量有很大提高.     

基于GA-SA的混合U型装配线平衡

在JIT生产系统中，混合U型装配线是一种能够满足市场多样化需求的柔性系统，章综合考虑作业元素的分配和产品的投产排序两个因素，建立了混合U型装配线的平衡模型，给出了人工智能算法的平衡方法，从全局优化的角度研究了混合U型装配线的平衡问题。     

Optimally routing and scheduling tow trains for JIT-supply of mixed-model assembly lines

In recent years, more and more automobile producers adopted the supermarket-concept to enable a flexible and reliable Just-in-Time (JIT) part supply of their mixed-model assembly lines. Within this concept, a supermarket is a decentralized in-house logistics area where parts are intermediately stored and then loaded on small tow trains. These tow trains travel across the shop floor on specific routes to make frequent small-lot deliveries which are needed by the stations of the line. To enable a reliable part supply in line with the JIT-principle, the interdependent problems of routing, that is, partitioning stations to be supplied among tow trains, and scheduling, i.e., deciding on the start times of each tow train’s tours through its assigned stations, need to be solved. This paper introduces an exact solution procedure which solves both problems simultaneously in polynomial runtime. Additionally, management implications regarding the trade-off between number and capacity of tow trains and in-process inventory near the line are investigated within a comprehensive computational study.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

Solving real car sequencing problems with ant colony optimization

An automobile assembly line is usually configured as three successive shops in which the body is constructed, painted, and then assembled together with all component parts into a finished vehicle. However, many published production sequencing models ignore the first two shops and base their results only on the requirements and constraints of the assembly shop. In this article, we propose to more closely follow the actual industrial structure. We therefore first propose a single objective mathematical model for scheduling the paint and assembly shops. We then propose an ACO metaheuristic for solving a multiple-objective formulation. Data provided by Groupe Renault show that the proposed approach offers better solutions than those of current practice.     

An imperialist competitive algorithm for multi-objective U-type assembly line design

Many assembly lines are now being designed as U-type assembly lines rather than straight lines because of the pressure of the just-in-time (JIT) manufacturing concept. Since any type of an assembly line balancing problem is known to be NP-hard, there has been a growing tendency toward using evolutionary algorithms to solve such a hard problem. This paper proposes a new population-based evolutionary algorithm, namely imperialist competitive algorithm (ICA) inspired by the process of socio-political evolution, to address the multi-objective U-type assembly line balancing problem (UALBP). Two considered objectives are to minimize the line efficiency and minimize the variation of workload. Furthermore, the Taguchi design is applied to tune the effective parameters of the proposed ICA. To demonstrate the efficiency of the proposed algorithm, the associated results are compared against an efficient genetic algorithm (GA) in the literature over a large group of benchmarks taken from the literature. The computational results show that the proposed ICA outperforms GA.     

Multi-vendor integrated procurement-production system under shared transportation and just-in-time delivery system

Just-in-time (JIT) procurement is one of the important elements of lean production system. Successful implementation of JIT needs vendor-manufacturer cooperation on small lot size delivery and inbound logistics cost reduction. Unlike the most recent literature focusing on single-vendor and single-buyer integrated inventory systems, this paper studies a multi-vendor integrated procurement-production inventory system that incorporates delivery and shared transportation costs. A multi-vendor optimal model is developed here for deciding the batch size of vendor's production, and delivery frequencies of different vendors to the manufacturer. Solution procedures for two special cases—uncapacitated and capacitated models are developed; especially, a new approximate method for capacitated model is devised. Numerical examples demonstrate the solution mechanism for the model. The results highlight cooperation between vendors and manufacturers on JIT procurement practices.     

Optimal models for a multi-stage supply chain system controlled by kanban under just-in-time philosophy

This research studies a multi-stage supply chain system that operates under a JIT (just-in-time) delivery policy. Kanbans play an important role in the information and material flows in a supply chain system. Thus, a kanban mechanism is employed to assist in linking different production processes in a supply chain system to implement the scope of JIT philosophy. For a multi-stage supply chain system, a mixed-integer nonlinear programming (MINLP) problem is formulated from the perspective of JIT delivery policy where a kanban may reflect to a transporter such as a truck or a fork-lifter. The number of kanbans, the batch size, the number of batches and the total quantity over one period are determined optimally. It is solved optimally by branch and bound method. A greedy heuristic to avoid the large computational time in branch-and-bound algorithm is developed for solving a large MINLP. Coupled with plant-wide efforts for cost control and management commitment, a logistic system for controlling the production as well as the supply chain is built, which results in minimizing the total cost of the supply chain system. The results show that the improvements in reduction of inventory, wasted labor and customer service in a supply chain are significantly accomplished through the kanban mechanism.     

The directional p-median problem: Definition,complexity, and algorithms

An instance of a p-median problem gives n demand points. The objective is to locate p supply points in order to minimize the total distance of the demand points to their nearest supply point. p-Median is polynomially solvable in one dimension but NP-hard in two or more dimensions, when either the Euclidean or the rectilinear distance measure is used. In this paper, we treat the p-median problem under a new distance measure, the directional rectilinear distance, which requires the assigned supply point for a given demand point to lie above and to the right of it. In a previous work, we showed that the directional p-median problem is polynomially solvable in one dimension; we give here an improved solution through reformulating the problem as a special case of the constrained shortest path problem. We have previously proven that the problem is NP-complete in two or more dimensions; we present here an efficient heuristic to solve it. Compared to the robust Teitz and Bart heuristic, our heuristic enjoys substantial speedup while sacrificing little in terms of solution quality, making it an ideal choice for real-world applications with thousands of demand points.     

Global optimal policy for vendor–buyer integrated inventory system within just in time environment

Traditionally, inventory problems for the vendor and the buyer are treated separately. In modern enterprises, however, the integration of vendor–buyer inventory system is an important issue. This co-operative approach to inventory management contributes to the success of supply chain management by minimizing the joint inventory cost. The joint inventory cost and the response time can further be reduced when the buyer orders and the vendor replenishes the required items just in time (JIT) for their consumption. The inclusion of the JIT concept in this model contributes significantly to a joint inventory cost reduction. A numerical example and sensitivity analysis are carried out. The derived results show an impressive cost reduction when compared with Goyal’s model.     

Bicriteria sequencing methods for the mixed-model assembly line in just-in-time production systems

A mixed-model manufacturing facility operating in a pull production environment can be controlled by setting a production schedule only for the last process in the facility which is usually an assembly line of mixed-model type. In the mixed-model sequencing problems, two major goals are considered: (1) smoothing the workload on each workstation on the assembly line, and (2) keeping a constant rate of usage of all parts used on the assembly line. In this study, first, some well-known solution approaches with goal 2 are analyzed through minimizing the sum-of-deviations of actual production from the desired amount. The approaches that are found to be performing better than the others are extended for the bicriteria problem considering goals 1 and 2, simultaneously. It is also shown that the bicriteria problem with the sum-of-deviations type objective function can also be formulated as an assignment problem, and the optimal solution to the small-sized problems can thus be obtained by solving the assignment problem. Finally, the conditions when it is important to take the workload-smoothing goal into consideration are analyzed.     

A new diversity induction mechanism for a multi-objective ant colony algorithm to solve a real-world time and space assembly line balancing problem

Time and space assembly line balancing considers realistic multi-objective versions of the classical assembly line balancing industrial problems. It involves the joint optimisation of conflicting criteria such as the cycle time, the number of stations, and/or the area of these stations. The different problems included in this area also inherit the precedence constraints and the cycle time limitations from assembly line balancing problems. The presence of these hard constraints and their multi-criteria nature make these problems very hard to solve. Multi-objective constructive metaheuristics (in particular, multi-objective ant colony optimisation) have demonstrated to be suitable approaches to solve time and space assembly line balancing problems. The aim of this contribution is to present a new mechanism to induce diversity in an existing multi-objective ant colony optimisation algorithm for the 1/3 variant of the time and space assembly line balancing problem. This variant is quite realistic in the automative industry as it involves the joint minimisation of the number and the area of the stations given a fixed cycle time limit. The performance of our proposal is validated considering ten real-like problem instances. Moreover, the diversity induction mechanism is also tested on a real-world instance from the Nissan plant in Barcelona (Spain).     

The oracle penalty method

A new and universal penalty method is introduced in this contribution. It is especially intended to be applied in stochastic metaheuristics like genetic algorithms, particle swarm optimization or ant colony optimization. The novelty of this method is, that it is an advanced approach that only requires one parameter to be tuned. Moreover this parameter, named oracle, is easy and intuitive to handle. A pseudo-code implementation of the method is presented together with numerical results on a set of 60 constrained benchmark problems from the open literature. The results are compared with those obtained by common penalty methods, revealing the strength of the proposed approach. Further results on three real-world applications are briefly discussed and fortify the practical usefulness and capability of the method.     

A just-in-time three-level integrated manufacturing system for linearly time-varying demand process

This paper considers a just-in-time (JIT) manufacturing system in which a single manufacturer procures raw materials from a single supplier, process them to produce finished products, and then deliver the products to a single-buyer. The customer demand rate is assumed to be linearly decreasing time-varying. In the JIT system, in order to minimize the suppliers as well as the buyers holding costs, the supply of raw materials and the delivery of finished products are made in small quantities. In this case, both the supply and the delivery may require multiple installments for a single production lot. We develop a mathematical model for this problem, propose a simple methodology for solving the model, and illustrate the effectiveness of the method with numerical examples.     

Measuring performances of multiple-channel queueing systems with imprecise data: a membership function approach

This paper proposes a mixed integer nonlinear programming (MINLP) approach to measure the system performances of multiple-channel queueing models with imprecise data. The main idea is to transform a multiple-channel queue with imprecise data to a family of conventional crisp multiple-channel queues by applying the α-cut approach in fuzzy theory. On the basis of α-cut representation and the extension principle, two pairs of parametric MINLP are formulated to describe the family of crisp multiple-channel queues, via which the membership functions of the performance measures are derived. To demonstrate the validity of the proposed procedure, a real-world case of multiple-channel fuzzy queue is investigated successfully. Since the performance measures are expressed by membership functions rather than by crisp values, the fuzziness of input information is completed conserved. Thus, the results obtained from the proposed approach can represent the system more accurately, and more information is provided for system design in practice.     

Achieving sharp deliveries in supply chains through variance pool allocation

Variability reduction and business process synchronization are acknowledged as key to achieving sharp and timely deliveries in supply chain networks. In this paper, we develop an approach that facilitates variability reduction and business process synchronization for supply chains in a cost effective way. The approach developed is founded on an analogy between mechanical design tolerancing and supply chain lead time compression. We first present a motivating example to describe this analogy. Next, we define, using process capability indices, a new index of delivery performance called delivery sharpness which, when used with the classical performance index delivery probability, measures the accuracy as well as the precision with which products are delivered to the customers. Following this, we solve the following specific problem: how do we compute the allowable variability in lead time for individual stages of the supply chain so that specified levels of delivery sharpness and delivery probability are achieved in a cost-effective way? We call this the variance pool allocation (VPA) problem. We suggest an efficient heuristic approach for solving the VPA problem and also show that a variety of important supply chain design problems can be posed as instances of the VPA problem. One such problem, which is addressed in this paper, is the supply chain partner selection problem. We formulate and solve the VPA problem for a plastics industry supply chain and demonstrate how the solution can be used to choose the best mix of supply chain partners.     

A note on coordination in decentralized assembly systems with uncertain component yields

Gurnani and Gerchak [H. Gurnani, Y. Gerchak, Coordination in decentralized assembly systems with uncertain component yields, European Journal of Operational Research 176 (2007) 1559–1576] study coordination of a decentralized assembly system in which the demand of the assembler is deterministic and the component yields are random. They present incentive alignment control mechanisms under which system coordination is achieved. In this note, we extend Gurnani and Gerchak’s model to the case of positive salvage value and n asymmetric suppliers, and show that the shortage penalty contract which can coordinate Gurnani and Gerchak’s model no longer coordinates the extended model. Furthermore, we present a new kind of contract, surplus subsidy contract, to coordinate the extended model and prove that the profit of the supply chain under coordination can be arbitrarily divided between the component suppliers and the assembler.     

A coordination system for seasonal demand problems in the supply chain

This article considers a single product coordination system using a periodic review policy, participants of the system including a supplier and one or more heterogeneous buyers over a discrete time planning horizon in a manufacturing supply chain. In the coordination system, the demand of buyer in each period is deterministic, the supplier replenishes all the buyers, and all participants agree to plan replenishment to minimize total system costs. To achieve the objective of the coordination system, we make use of small lot sizing and frequent delivery policies (JIT philosophy) to transport inventory between supplier and buyers. Moreover, demand variations of buyers are allowed in the coordination system to suit real-world situations, especially for hi-tech industries. Furthermore, according to the mechanisms of minimizing the total relevant costs, the proposed method can obtain the optimal number of deliveries, shipping points and shipping quantities in each order for all participants in the coordination system.     

Controlled diffusion processes with Markovian switchings for modeling dynamical engineering systems

In this paper the intrinsic complex nature of engineering systems under control is treated by introducing an approach based on Controlled Stochastic Differential Equations with Markovian Switchings (in short CSDEMS). Technical conditions for the existence and uniqueness of the solutions of the CSDEMS are provided. In this context it is not unusual to deal with non-linear CSDEMS that cannot be solved analytically. Therefore, we develop a new two-step, predictor–corrector method for finding numerical approximations to solutions of CSDEMS. This method utilizes the Euler–Maruyama method. An illustrative application to the biochemical engineering area is presented to highlight the usefulness of our approach as a simulation tool.