On-line supply chain scheduling problems with preemption

We consider supply chain scheduling problems where customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. The jobs are released on-line, that is, at any time there is no information on the number, release and processing times of future jobs; the processing time of a job becomes known when the job is released. Preemption is allowed. To reduce the total costs, processed jobs are grouped into batches, which are delivered to customers as single shipments; we assume that the cost of delivering a batch does not depend on the number of jobs in the batch. The objective is to minimize the total cost, which is the sum of the total flow time and the total delivery cost. For the single-customer problem, we present an on-line two-competitive algorithm, and show that no other on-line algorithm can have a better competitive ratio. We also consider an extension of the algorithm for the case of m customers, and show that its competitive ratio is not greater than 2m if the delivery costs to different customers are equal.     

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

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

Approximation algorithm for the on-line multi-customer two-level supply chain scheduling problem

A manufacturer has to process jobs released on-line and deliver them to customers. Preemption is allowed. Jobs are grouped into batches for delivery. The sum of the total flow time and the total delivery cost is minimized. Deliveries to different customers cannot be combined. We present an on-line algorithm with the competitive ratio bounded by 3+α$3+\alpha$, where α$\alpha$ is the ratio of the largest processing time to the smallest processing time.     

平行机的供应链排序

研究平行机环境下的供应链排序,即研究如何安排工件在平行机上加工,把加工完毕的工件分批发送给下游客户,使得生产排序费用和发送费用总和最少。这里,生产排序费用是用工件送到时间的函数表示;发送费用是由固定费用和与运输路径有关的可变费用两部分组成。研究以工件带权送到时间和作为生产排序费用的供应链排序问题,给出多项式时间近似算法,并分析算法性能比。     

带交货期的工件族生产与配送的排序问题

本文考虑了多个客户订购不同种类的工件,工件生产完后需要运输到客户的单机供应链排序问题.由于工件属于不同的种类,在加工不同种类工件前要有一个准备时间.每个客户分布在不同位置,客户的每个工件都有一个交货期,工件是分批配送的,每一批配送需要花费一定的时间及费用.考虑了两个与交货期有关的目标函数,分别给出了它们的最优算法.     

Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains

In this paper, an integrated due date assignment and production and batch delivery scheduling problem for make-to-order production system and multiple customers is addressed. Consider a supply chain scheduling problem in which n orders (jobs) have to be scheduled on a single machine and delivered to K customers or to other machines for further processing in batches. A common due date is assigned to all the jobs of each customer and the number of jobs in delivery batches is constrained by the batch size. The objective is to minimize the sum of the total weighted number of tardy jobs, the total due date assignment costs and the total batch delivery costs. The problem is NP-hard. We formulate the problem as an Integer Programming (IP) model. Also, in this paper, a Heuristic Algorithm (HA) and a Branch and Bound (B&B) method for solving this problem are presented. Computational tests are used to demonstrate the efficiency of the developed methods.     

具有两种运输方式选择的物流排序问题

本文研究了单机环境下,有两种运输方式可供选择的集成生产和运输的排序问题。有多个工件需要在一台机器上进行加工,工件生产完后需要分批运到客户处。有两种运输方式,普通运输和特快运输可供选择。制造商需要安排工件的加工顺序,选择合适的运输方式和出发时间,以极小化相应的时间目标与运输费用的加权和。研究了排序理论中主要的两个目标函数,分析了问题的复杂性,对于这些问题给出了它们的最优算法。     

Optimal methods for batch processing problem with makespan and maximum lateness objectives

In this paper we consider the problem of scheduling n jobs on a single batch processing machine in which jobs are ordered by two customers. Jobs belonging to different customers are processed based on their individual criteria. The considered criteria are minimizing makespan and maximum lateness. A batching machine is able to process up to b jobs simultaneously. The processing time of each batch is equal to the longest processing time of jobs in the batch. This kind of batch processing is called parallel batch processing. Optimal methods for three cases are developed: unbounded batch capacity, b > n, with compatible job groups and bounded batch capacity, b  n, with compatible and non compatible job groups. Each job group represents a different class of customers and the concept of being compatible means that jobs which are ordered by different customers are allowed to be processed in a same batch. We propose an optimal method for the problem with incompatible groups and unbounded batches. About the case when groups are incompatible and bounded batches, our proposed method is considered as optimal when the group with maximum lateness objective has identical processing times. We regard this method, however, as a heuristic when these processing times are different. When groups are compatible and batches are bounded we consider another problem by assuming the same processing times for the group which has the maximum lateness objective and propose an optimal method for this problem.     

Scheduling with batch setup times and earliness-tardiness penalties

We consider a scheduling model in which several batches of jobs need to be processed by a single machine. During processing, a setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. All the jobs in the same batch have a common due date that is either externally given as an input data or internally determined as a decision variable. Two problems are investigated. One problem is to minimize the total earliness and tardiness penalties provided that each due date is externally given. We show that this problem is NP-hard even when there are only two batches of jobs and the two due dates are unrestrictively large. The other problem is to minimize the total earliness and tardiness penalties plus the total due date penalty provided that each due date is a decision variable. We give some optimality properties for this problem with the general case and propose a polynomial dynamic programming algorithm for solving this problem with two batches of jobs. We also consider a special case for both of the problems when the common due dates for different batches are all equal. Under this special case, we give a dynamic programming algorithm for solving the first problem with an unrestrictively large due date and for solving the second problem. This algorithm has a running time polynomial in the number of jobs but exponential in the number of batches.     

Lot sizing for a single product recovery system with variable setup numbers

Inventory systems for joint remanufacturing and manufacturing have recently received considerable attention. In such systems, used products are collected from customers and are kept at the recoverable inventory warehouse for future remanufacturing. In this paper a production–remanufacturing inventory system is considered, where the demand can be satisfied by production and remanufacturing. The cost structure consists of the EOQ-type setup costs, holding costs and shortage costs. The model with no shortage case in serviceable inventory is first studied. The serviceable inventory shortage case is discussed next. Both models are considered for the case of variable setup numbers of equal sized batches for production and remanufacturing processes. For these two models sufficient conditions for the optimal type of policy, referring to the parameters of the models, are proposed.     

Batch Delivery Scheduling on a Single Machine

The problem of partitioning a set of independent and simultaneously available jobs into batches and sequencing them for processing on a single machine is presented. Jobs in the same batch are to be delivered together, upon completion of the last job in the batch. Jobs finished before this time have to wait until delivery. There are a delivery cost depending on the number of batches formed and an earliness cost for jobs finished before delivery. The dynamic programming approach to minimizing the total cost is considered, yielding two pseudopolynomial algorithms when the number of batches has a fixed upper bound. A polynomial algorithm for a special case of the problem is also presented.     

The unbounded parallel-batch scheduling with rejection

In this paper, we consider the unbounded parallel-batch scheduling with rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and processed in batches on a machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. Four problems are considered: (1) to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs; (2) to minimize the total completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs; (3) to minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total completion time of the accepted jobs; (4) to find the set of all the Pareto optimal schedules. We provide a polynomial-time algorithm for the first problem. Furthermore, we show that all the other three problems are binary NP-hard and present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for them.     

考虑常数客户批运输的单机排序问题

本文考虑工件首先在单机上加工,完工的工件由一辆容量有限的车配送到指定客户的模型,目标是最小化makespan。对于工件物理大小相同的情况,我们考虑了常数个客户的情形,并且给出了一个多项式时间的动态规划算法。对于工件物理大小不同的情况,我们讨论了一类特殊的三个客户的情形,并给出了一个2-近似算法。     

基于多客户的工件可转包排序问题(英文)

In this paper, we study a new scheduling and outsourcing model with multiple customers in which jobs can be processed by either in-house machine or outsourcing machine.All processed jobs have to be delivered in batches to their respective customers and each shipment incurs a delivery cost as well as a fixed amount of time. We discuss three commonly used objective functions, analyze their complexity and solve them by dynamic programming algorithms.     

分类数很大时的成组排序问题

成组排序具有深刻的实际应用背景,是近年来国外研究得较多的一个热点.已有的某些动态规划算法的复杂性随分类数的增长呈指数型增长趋势,本文用“归并”和解不超过四个新的子问题的方法把分类数较大时的问题转化为分类数较小时的相应问题,简化了问题的求解.     

单位工件的平行机并行分批在线排序问题的算法

本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有n个相互独立的工件J={J₁,…,J_n}要在m台批处理机上加工。批处理机每次可同时加工至多B(Bj(1≤j≤n)的到达时间为r_j,加工时间为1,工件是否会到达事先未知,而只有等到工件的到达时间才能获知它的到达。目标为最小化工件的最大完工时间。针对该排序问题,本文设计了两个竞争比均达到最好可能的在线算法。     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

A fuzzy goal programming and meta heuristic algorithms for solving integrated production: distribution planning problem

Integrated production–distribution planning is one of the most important issues in supply chain management (SCM). We consider a supply chain (SC) network to consist of a manufacturer, with multiple plants, products, distribution centers (DCs), retailers and customers. A multi-objective linear programming problem for integrating production–distribution, which considers various simultaneously conflicting objectives, is developed. The decision maker’s imprecise aspiration levels of goals are incorporated into the model using a fuzzy goal programming approach. Due to complexity of the considered problem we propose three meta-heuristics to tackle the problem. A simple genetic algorithm and a particle swarm optimization (PSO) algorithm with a new fitness function, and an improved hybrid genetic algorithm are developed. In order to show the efficiency of the proposed methods, two classes of problems are considered and their instances are solved using all methods. The obtained results show that the improved hybrid genetic algorithm gives us the best solutions in a reasonable computational time.     

Integrated scheduling of production and distribution for manufacturers with parallel batching facilities

We consider a class of integrated scheduling problems for manufacturers. The manufacturer processes job orders and delivers products to the customer. The objective is to minimize the service span, that is, the period lasting from the time when the order is received to the time when all the products have been delivered to the customer. In the production phase, parallel batch-processing facilities are used to process the jobs. Jobs have arbitrary sizes and processing times. Each facility has a fixed capacity and jobs are processed in batches with the restriction that the total size of jobs in a batch does not exceed the facility capacity. When all the jobs in a batch are completed, the batch is completed. In the distribution phase, the manufacturer uses a vehicle with a fixed capacity to deliver products. The transportation time from the manufacturer to the customer is a constant. Completed products can be delivered in one transfer if the total size does not exceed the vehicle capacity. We first consider the problem where jobs have the same size and arbitrary processing times. We propose approximation algorithms for the problem and we show that a worst-case ratio performance guarantee is respectively 2–1/m. Then we consider the problem where jobs have the same processing time and arbitrary sizes. An approximation algorithm is proposed with an absolute worst-case ratio of 13/7 and an asymptotic worst-case ratio of 11/9. Both the proposed algorithms can be executed in polynomial time.     

On-line scheduling of unit time jobs with rejection: minimizing the total completion time

We consider on-line scheduling of unit time jobs on a single machine with job-dependent penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled, or be rejected at the cost of a penalty. The objective is to minimize the total completion time of the accepted jobs plus the sum of the penalties of the rejected jobs.We give an on-line algorithm for this problem with competitive ratio . Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784.