Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain

In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.     

A mixed integer programming model for scheduling orders in a steel mill

The problem of scheduling orders at each facility of a large integrated steel mill is considered. Orders are received randomly, and delivery dates are established immediately. Each order is filled by converting raw materials into a finished saleable steel product by a fixed sequence of processes. The application of a deterministic mixed integer linear programming model to the order scheduling problem is given. One important criterion permitted by the model is to process the orders in a sequence which minimizes the total tardiness from promised delivery for all orders; alternative criteria are also possible. Most practical constraints which arise in steelmaking can be considered within the formulation. In particular, sequencing and resource availability constraints are handled easily. The order scheduling model given here contains many variables and constraints, resulting in computational difficulties. A decomposition algorithm is devised for solving the model. The algorithm is a special case of Benders partitioning. Computational experience is reported for a large-scale problem involving scheduling 102 orders through ten facilities over a six-week period. The exact solution to the large-scale problem is compared with schedules determined by several heuristic dispatching rules. The dispatching rules took into consideration such things as due date, processing time, and tardiness penalties. None of the dispatching rules found the optimal solution.     

面对单客户的生产与配送二级供应链协同调度探讨

本文探讨了单机器单客户下的生产与配送二级供应链协同调度问题,对于配送车容量有限且车辆充足、单配送车容量无限的两种情形展开分析。针对每一种情形,分析对比了在配送环节中iid(单独配送)方式与 direct(批量配送)方式对供应链调度效果的作用,给出了不同配送方式占优的条件。研究结果对于供应链协同调度模式的选择具有指导意义。     

智能制造环境下的备件生产与运输协同调度问题研究

智能制造和即时配送环境下的备件生产与运输协同调度问题是目前国内研究的一大热点,这是因为备件供应链响应速度已成为当前备件制造企业赢得客户的关键因素。为了提高客户满意度,尽可能缩短从客户下达定制化生产订单到订单配送完成的时间,本文建立了以所有客户总等待时间最短为目标的混合整数规划模型和集合覆盖模型,推导了最优解性质,并设计改进的分支定价算法求得最优解。通过将小规模算例结果与CPLEX进行对比,验证了模型和算法的有效性。多组算例测试结果表明,所提出的模型和算法可以有效提升智能制造环境下的备件供应链运作效率。     

储存时间有上限的两阶段供应链排序问题

研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输:加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件.工件的运输完成时刻与完工时刻之差定义为工件的储存时间,且有相应的储存费用,且任意工件的储存时间都不超过某一常数.若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻,则有相应的提前(延误)惩罚费用.目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和.先证明该问题是NP-难的,后对单位时间的储存费用不超过单位时间的延误惩罚费用的情形给出了伪多项式时间算法.     

A heuristic approach to a single stage assembly problem with transportation allocation

Determining assembly scheduling and transportation allocation are two practical problems that industries face, such as the electronics and health products industries. Problems associated with assembly scheduling mainly focus on how to determine the orders’ processing sequence on the assembly line in order to minimize the waiting times before they are flown to their destinations. Problems associated with transportation allocation arise in the system of assigning processed orders to transport modes with the purpose of minimizing penalties from earliness and tardiness. To minimize overall delivery costs, businesses should decide on assembly scheduling and transportation allocation decision simultaneously. However, since simultaneously making these two decisions is not an easy task, most of the works done on them usually deal with these two problems separately. Apart from previous works, this paper establishes a mixed integer programming model that deals with these problems simultaneously. Due to the computational complexity of the problem, this paper develops a hybrid heuristic algorithm to solve this problem, and we evaluate the performance of the presented heuristic algorithm with the well-known GAMS/BARON and Lingo commercial software, which tests the heuristic algorithm on randomly-generated problems. The presented heuristic algorithm is shown to perform well compared with well-known commercial software.     

Supply chain scheduling in a collaborative manufacturing mode: model construction and algorithm design

In collaborative manufacturing, the supply chain scheduling problem becomes more complex according to both multiple product demands and multiple production modes. Aiming to obtain a reasonable solution to this complexity, we analyze the characteristics of collaborative manufacturing and design some elements, including production parameters, order parameters, and network parameters. We propose four general types of collaborative manufacturing networks and then construct a supply chain scheduling model composed of the processing costs, inventory costs, and two penalty costs of the early completion costs and tardiness costs. In our model, by considering the urgency of different orders, we design a delivery time window based on the least production time and slack time. Additionally, due to the merit of continuously processing orders belonging to the same product type, we design a production cost function by using a piecewise function. To solve our model efficiently, we present a hybrid ant colony optimization (HACO) algorithm. More specifically, the Monte Carlo algorithm is incorporated into our HACO algorithm to improve the solution quality. We also design a moving window award mechanism and dynamic pheromone update strategy to improve the search efficiency and solution performance. Computational tests are conducted to evaluate the performance of the proposed method.

     

Scheduling parallel machines with single vehicle delivery

We investigate the integrated production and distribution scheduling problem in a supply chain. The manufacturer’s production environment is modeled as a parallel machine system. A single capacitated vehicle is employed to deliver products in batches to multiple customers. The scheduling problem can also be viewed as either parallel machines with delivery considerations or a flexible flowshop. Different inventory holding costs, job sizes (volume or storage space required in the transportation unit), and job priorities are taken into account. Efficient mathematical modeling and near-optimal heuristic approaches are presented for minimizing total weighted completion time.     

Integrated machine scheduling and vehicle routing with time windows

This paper integrates production and outbound distribution scheduling in order to minimize total tardiness. The overall problem consists of two subproblems. The first addresses scheduling a set of jobs on parallel machines with machine-dependent ready times. The second focusses on the delivery of completed jobs with a fleet of vehicles which may differ in their loading capacities and ready times. Job-dependent processing times, delivery time windows, service times, and destinations are taken into account. A genetic algorithm approach is introduced to solve the integrated problem as a whole. Two main questions are examined. Are the results of integrating machine scheduling and vehicle routing significantly better than those of classic decomposition approaches which break down the overall problem, solve the two subproblems successively, and merge the subsolutions to form a solution to the overall problem? And if so, is it possible to capitalize on these potentials despite the complexity of the integrated problem? Both questions are tackled by means of a numerical study. The genetic algorithm outperforms the classic decomposition approaches in case of small-size instances and is able to generate relatively good solutions for instances with up to 50 jobs, 5 machines, and 10 vehicles.     

Complexity of flow shop scheduling problems with transportation constraints

In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as Automated Guided Vehicles, robots and conveyors, and finished jobs are delivered to warehouses or customers by vehicles such as trucks.This paper investigates two-machine flow shop scheduling problems taking transportation into account. The finished jobs are transferred from the processing facility and delivered to customers by truck. Both transportation capacity and transportation times are explicitly taken into account in these models. We study the class of flow shop problems by analysing their complexity. For the makespan objective function, we prove that this problem is strongly NP-hard when the capacity of a truck is limited to two or three parts with an unlimited buffer at the output of the each machine. This problem with additional constraints, such as blocking, is also proven to be strongly NP-hard.     

优化交货期窗口的两阶段供应链排序问题

研究一类优化交货期窗口的两阶段供应链排序问题. 优化交货期窗口是指交货期窗口的开始与结束时刻是决策变量, 不是输入常量. 两阶段是指工件先加工, 后运输: 加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件. 工件的开始运输时刻与完工时刻之差定义为工件的储存时间, 且有相应的储存费用. 若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻, 则有相应的提前(延误)惩罚费用. 目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和. 针对单位时间的延误惩罚费用不超过单位时间的储存费用、单位时间的储存费用不超过单位时间的提前惩罚费用的情形, 给出了时间复杂性为O(n^{8})的动态规划算法.     

Supply chain scheduling: Just-in-time environment

We study the benefits of coordinated decision making in a supply chain consisting of a manufacturer, a distributor, and several retailers. The distributor bundles finished goods produced by the manufacturer and delivers them to the retailers to meet their demands. The distributor is responsible for managing finished goods inventory. An optimal production schedule of the manufacturer, if imposed on the distributor, may result in an increased inventory holding cost for the distributor. On the other hand, an optimal distribution schedule of the distributor, if imposed on the manufacturer, may result in an increased production cost for the manufacturer. In this paper we develop mathematical models for individual optimization goals of the two partners and compare the results of these models with the results obtained for a joint optimization model at the system level. We investigate the computational complexities of these scheduling problems. The experimental results indicate that substantial cost savings can be achieved at the system level by joint optimization. We also study conflict and cooperation issues in the supply chain. The cost of conflict of a supply chain partner is a measure of the amount by which the unconstrained optimal cost increases when a decision is to be made under the scheduling constraint imposed by the other partner. We quantify these conflicts and show that the cost of conflicts are significant. We also show that a cooperative decision will generate a positive surplus in the system which can be shared by the two partners to make cooperation and coordination strategy more attractive.     

Improving fleet utilization for carriers by interval scheduling

Carriers are under increasing pressure to offset rising fuel charges with cost cutting or revenue generating schemes. One opportunity for cost reduction lies in asset management. This paper presents resource allocation scheduling models that can be used to assign truck loads to delivery times and trucks when delivery times are flexible. The paper makes two main contributions. First, we formulate the problem as a multi-objective optimization model — minimizing the number of trucks needed as well as the costs associated with tardiness or earliness — and demonstrate how improvements in fleet usage translate into savings which carriers can use as incentives to promote flexible delivery times for customers. Second, we show that a two-phase model with a polynomial algorithm in the second phase is able to produce optimal schedules in a reasonable time.     

自由作业的供应链排序研究

研究一类集成工件加工和发送的供应链排序模型,即研究如何安排工件在自由作业机器上加工,把加工完毕的工件分批发送给下游客户,使得含生产排序费用和发送费用的目标函数最优.这里,分别取工件最大送到时间和平均送到时间为生产排序费用;而发送费用是由固定费用和与运输路径有关的变化费用组成.利用排序理论和动态规划方法,构造了自由作业供应链排序问题的多项式时间近似算法,并分析算法的性能比.     

带强制工期的可中断单机排序问题

工件带强制工期,指工件必须在已给定的工期内完工,不得延迟.这种环境在实际应用中随处可见.如果工件过早提前完工,意味着工件还需要保管,将会产生额外费用.本文讨论了在单机上,加工带准备时间与强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过奇偶划分问题归约,证明了其是NP-complete的.而后,讨论了加工时间相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序,因此提出了—个多项式时间算法,既能判定可行性,又能针对可行问题获得最优排序.     

Synchronization in supply chains: implications for design and management

Supply chain management literature calls for coordination between the different members of the chain. Materials should be moved from one supplier to the next according to a just-in-time schedule. In this paper, we show that for many supply chain configurations, complete synchronization will result in some members of the chain being ‘losers’ in terms of cost. We develop an algorithm for optimal synchronization of supply chains and provide some guidelines for incentive alignment along the supply chain. In developing the model, we use the economic delivery and scheduling problem model and analyze supply chains dealing with single and multiple components. For single-component supply chains, we derive a closed-form expression for the optimal synchronized cycle time. For multi-component supply chains, we develop an algorithm for finding the optimal synchronized cycle time. We test the performance of the algorithm and show that it provides optimal solutions for a wide range of problems. We illustrate the models with numerical examples.     

Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness

Parallel machine scheduling is a popular research area due to its wide range of potential application areas. This paper focuses on the problem of scheduling n independent jobs to be processed on m identical parallel machines with the aim of minimizing the total tardiness of the jobs considering a job splitting property. It is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We present a mathematical model for this problem. The problem of total tardiness on identical parallel machines is NP-hard. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using an optimization solver is extremely difficult. We propose two meta-heuristics: Tabu search and simulated annealing. Computational results are compared on random generated problems with different sizes.     

A hybrid genetic algorithm for the finite horizon economic lot and delivery scheduling in supply chains

In this paper, we investigate the lot and delivery scheduling problem in a simple supply chain where a single supplier produces multiple components on a flexible flow line (FFL) and delivers them directly to an assembly facility (AF). It is assumed that all of parameters such as demand rates for the components are deterministic and constant over a finite planning horizon. The main objective is to find a lot and delivery schedule that would minimize the average of holding, setup, and transportation costs per unit time for the supply chain. We develop a new mixed integer nonlinear program (MINLP) and an optimal enumeration method to solve the problem. Due to difficulty of obtaining the optimal solution in medium and large-scaled problems, a hybrid genetic algorithm (HGA) is also developed. The proposed HGA incorporates a neighborhood search (NS) into a basic genetic algorithm that enables the algorithm to perform genetic search over the subspace of local optima. The two proposed solution methods are compared on randomly generated problems, and computational results show that the performance of HGA is very promising because it is able to find an optimal or near-optimal solution for majority of the test problems.     

Notes on the single route lateral transhipment problem

Previous research has analyzed deterministic and stochastic models of lateral transhipments between different retailers in a supply chain. In these models the analysis assumes given fixed transhipment costs and determines under which situations (magnitudes of excess supply and demand at various retailers) the transhipment is profitable. However, in reality, these depend on aspects like the distance between retailers or the transportation mode chosen. In many situations, combining the transhipments may save transportation costs. For instance, one or more vehicle routes may be used to redistribute the inventory of the potential pickup and delivery stations. This can be done in any sequence as long as the vehicle capacity is not violated and there is enough load on the vehicle to satisfy demand. The corresponding problem is an extension of the one-commodity pickup and delivery traveling salesman and the pickup and delivery vehicle routing problem. When ignoring the routing aspect and assuming given fixed costs, transhipment is only profitable if the quantities are higher than a certain threshold. In contrast to that, the selection of visited retailers is dependent on the transportation costs of the tour and therefore the selected retailers are interrelated. Hence the problem also has aspects of a (team) orienteering problem. The main contribution is the discussion of the tour planning aspects for lateral transhipments which may be valuable for in-house planning but also for price negotiations with external contractors. A mixed integer linear program for the single route and single commodity version is presented and an improved LNS framework to heuristically solve the problem is introduced. Furthermore, the effect of very small load capacity on the structure of optimal solutions is discussed.     

Scheduling incoming and outgoing trucks at cross docking terminals to minimize the storage cost

Cross docking terminals allow companies to reduce storage and transportation costs in a supply chain. At these terminals, products of different types from incoming trucks are unloaded, sorted, and loaded to outgoing trucks for delivery. If the designated outgoing truck is not immediately available for some products, they are temporarily stocked in a small storage area available at the terminal. This paper focuses on the operational activities at a cross docking terminal with two doors: one for incoming trucks and another one for outgoing trucks. We consider the truck scheduling problem with the objective to minimize the storage usage during the product transfer inside the terminal. Our interest in this problem is mainly theoretical. We show that it is NP-hard in the strong sense even if there are only two product types. For a special case with fixed subsequences of incoming and outgoing trucks, we propose a dynamic programming algorithm, which is the first polynomial algorithm for this case. The results of numerical tests of the algorithm on randomly generated instances are also presented.