Single Supplier Scheduling for Multiple Deliveries

The problem of scheduling the production and delivery of a supplier to feed the production of F manufacturers is studied. The orders fulfilled by the supplier are delivered to the manufacturers in batches of the same size. The supplier's production line has to be set up whenever it switches from processing an order of one manufacturer to an order of another manufacturer. The objective is to minimize the total setup cost, subject to maintaining continuous production for all manufacturers. The problem is proved to be NP-hard. It is reduced to a single machine scheduling problem with deadlines and jobs belonging to F part types. An O(NlogF) algorithm, where N is the number of delivery batches, is presented to find a feasible schedule. A dynamic programming algorithm with O(N ^F /F ^F–2) running time is presented to find an optimal schedule. If F=2 and setup costs are unit, an O(N) time algorithm is derived.     

可转包的双目标单机排序问题（英文）

Scheduling with outsourcing is studied in this paper. It is assumed that both manufacturer and subcontractor have a single machine to process n jobs. The manufacturer needs to determine simultaneously a set of outsourced jobs and the schedule of the jobs in-house such that two criterias, i.e., outsourcing cost and production cost, are minimized.The production cost is measured by the number of tardy jobs or the total tardiness of jobs in-house, and the outsourcing cost is proportional to the total processing time of jobs outsourced. Two kinds of problems with different criterias are considered. We analyze the computational complexity and provide pseudo-polynomial time optimization algorithms for the NP-hard version of the problems.     

具有可变配送费用和固定配送时刻的单机排序问题

研究了单机环境下生产与配送的协同排序问题.有多个工件需要在一台机器上进行加工,加工完的工件需要分批配送到一个客户.每批工件只能在固定的几个配送时刻出发,不同的配送时刻对应着不同的配送费用.我们的目标是找到生产与配送的协同排序,极小化排序的时间费用与配送费用的加权和.研究了排序理论中主要的四个目标函数,构建了单机情况下的具体模型,分析了问题的复杂性,对于配送费用单调非增的情况给出了它们的最优算法.     

Manufacturer cooperation in supplier development under risk

Supplier development involves efforts undertaken by manufacturing firms to improve their suppliers’ capabilities and performance. These improvement efforts can be targeted at a variety of areas such as quality management, product development, and cost reduction. Since supplier development requires investments on the part of the manufacturer, it is important to optimally allocate investment dollars among multiple suppliers to minimize risk while maintaining an acceptable level of return. This paper presents a set of optimization models that address this issue. We consider two scenarios: single-manufacturer and multiple suppliers (SMMS) and two-manufacturer and multiple suppliers (TMMS). In the SMMS case, we suggest optimal investments in various suppliers by effectively considering risk and return. The TMMS case investigates whether manufacturers with differing capabilities could gain risk reduction benefits from cooperating with each other in supplier development. Through illustrative applications, we identify conditions in which both cooperation and non-cooperation are beneficial for manufacturers. Under conditions of cooperation, we propose optimal investments for manufacturers to achieve high levels of risk reduction benefits.     

A queueing model of delayed product differentiation

We consider a production system in which a supplier produces semi-finished items on a make-to-stock basis for a manufacturer that will customize the items on a make-to-order basis. The proportion of total processing time undertaken by the supplier determines how suitable the semi-finished items will be to meet customer demand. The manufacturer wishes to determine the optimal point of differentiation (the proportion of processing completed by the supplier) and its optimal semi-finished goods buffer size. We use matrix geometric methods to evaluate various performance measures for this system, and then, with enumeration techniques, obtain optimal solutions. We find that delayed product differentiation is attractive when the manufacturer can balance the costs of customer order fulfillment delay with the costs associated with unsuitable items.     

持股策略下随机需求低碳供应链融资决策均衡

随机市场需求且受制造商减排水平影响,考虑碳限额与交易机制,研究制造商进行单纯银行借贷和供应商投资持股的组合融资时的最优决策和利润情况,分析消费者低碳偏好、碳交易价格和供应商的投资持股比例对供应链的最优决策变量和利润的影响。研究发现:无资金约束、单纯银行借贷和组合融资下,消费者低碳偏好、碳交易价格和持股比例与制造商的减排水平和利润以及供应链系统的利润正相关,而供应商的批发价格和制造商的生产量与消费者低碳偏好正相关,与碳交易价格负相关,而持股比例与供应商的批发价格负相关,与制造商的生产量和减排水平正相关;持股策略下制造商的减排水平和生产量最大,无资金约束时次之,单纯银行借贷时最小;而无资金约束时供应商的批发价格最高,单纯银行借贷时次之,持股策略时最低;在持股比例满足一定条件下,供应商和制造商的利润优于单纯银行借贷时的利润,并且可以优于无资金约束时的利润,提高了供应链的竞争力和效率。     

供应中断风险下采购与定价决策分析

供应中断是供应链上的企业可能面临的问题,运用合理的采购策略可以帮助企业有效缓解供应中断风险。本文研究了供应中断下供应商和制造商之间的纵向竞争和两个制造商之间的横向竞争问题。供应商制定批发价,两个制造商采用不同的采购策略进行产量博弈,其中一个制造商采用紧急双源订货策略,另一个采用可靠单源订货策略。论文采用了多阶段博弈模型,分析了制造商之间的合谋与竞争两种行为,求出了供应商和制造商的最优决策,比较了这两种行为对供应商和制造商的影响。通过数值分析,讨论了成本参数和可靠性参数对于最优订货量的影响以及对于采用不同订货策略的制造商期望利润的影响。     

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.     

带凸资源和恶化效应的单机松弛窗口排序

研究带凸资源和恶化效应的单机窗口指派排序问题,其中窗口指的是松弛窗口,凸资源和恶化效应指的是工件的实际加工时间是其开始加工时间的线性函数,是其资源消耗量的凸函数。目标是确定工件的加工顺序,资源分配量以及窗口的开始加工时间和长度使其在总资源消耗费用(与窗口有关的排序费用)有上界限制的条件下,极小化与窗口有关的排序费用(总资源消耗费用)。获得了求解上述问题的最优算法,证明了该问题是多项式时间可解的。     

随机需求下有产能约束的技术创新策略研究

在随机需求和技术变革的环境下,基于有产能约束的单供应商-单零售商的供应链结构,研究供应商分销价格决策和技术创新策略以及零售商订货决策。建立了三阶段Stackelberg博弈模型,通过逆推方法求得了供应商最优分销价格和技术创新策略以及零售商最优订货量,深入探讨了供应商产能、新技术出现概率以及市场需求期望与波动分别对供应商、零售商和供应链整体利润的影响。结果表明当供应商产能不足时进行技术创新会提高供应商和供应链的利润,但零售商因间接承担供应商技术创新的投资成本而利润下降;当供应商产能过剩时进行技术创新则会降低供应商及供应链的利润,而零售商的利润增加。新技术出现概率增加会提高供应链各成员的利润;提高市场需求期望并减小市场波动对供应商及供应链有利,但可能会降低零售商的利润。     

Single machine scheduling and due date assignment with positionally dependent processing times

We consider single machine scheduling and due date assignment problems in which the processing time of a job depends on its position in a processing sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and, possibly, the total earliness of the scheduled jobs. We present polynomial-time dynamic programming algorithms in the case of two popular due date assignment methods: CON and SLK. The considered problems are related to mathematical models of cooperation between the manufacturer and the customer in supply chain scheduling.     

On-line integrated production–distribution scheduling problems with capacitated deliveries

In on-line integrated production–distribution problems, 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 about future jobs. Processed jobs are grouped into batches, which are delivered to the customers as single shipments. The total cost (to be minimized) is the sum of the total weighted flow time and the total delivery cost. Such on-line integrated production–distribution problems have been studied for the case of uncapacitated batches. We consider the capacitated case with an upper bound on the size of a batch. For several versions of the problem, we present efficient on-line algorithms, and use competitive analysis to study their worst-case performance.     

An agent-based negotiation model on price and delivery date in a fashion supply chain

Price and due-date negotiation between supply chain members is a critical issue. Motivated by industrial practice, we consider in this paper a make-to-order fashion supply chain in which the downstream manufacturer and the upstream supplier are cooperative on due-date and competitive on price. We propose a two-phase negotiation agenda based on such characteristics, and aim to find an optimal solution to deal with the negotiation problem considering production cost and mutual benefit. We build an analytical negotiation model for a manufacturer-supplier pair, discuss their utilities, and examine the Pareto efficiency frontier from the theoretical perspective. After that, from an application perspective, we build an agent-based two-phase negotiation system where agents are used to represent the two parties to enhance communication. In the cooperative phase, a simulated annealing based intelligent algorithm is employed to help the manufacturer agent and the supplier agent search tentative agreement on due dates which can minimize the total supply chain cost. In the competitive phase, the two parties bargain on the pricing issue using concession based methods. They adjust the reservation value and aspiration value for pricing accordingly based on the integrated utility and the result of the previous phase. Simulation results show that, the proposed negotiation approach can achieve optimal utility of agents and reach a win-win situation for the bilateral parties. Sensitivity analysis is conducted to further generate insights on how different parameters affect the performance of the proposed system.     

Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria

In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the following hierarchical optimization problems: minimizing total disruption cost among the minimum total flow time schedules and minimizing total flow time among the minimum total disruption cost schedules. We propose exponential-time algorithms to generate all efficient solutions and to minimize a specified function of the measures. Our extensive computational tests on large size problem instances have revealed that our optimization algorithm finds the best solution by generating only a small portion of all efficient solutions.     

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

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

Single-machine scheduling to minimize total absolute differences in waiting times with deteriorating jobs

In this paper we consider a single-machine scheduling problem with simple linear deterioration. By simple linear deterioration, we mean that the processing time of a job is a simple linear function of its execution starting time and its deterioration rate. The objective is to find a schedule that minimizes total absolute differences in waiting times. We show that the optimal schedule is V-shaped: jobs are arranged in descending order of their deterioration rates if they are placed before the job with the smallest deterioration rate, but in ascending order of their deterioration rates if placed after it. We prove other several properties of an optimal schedule, and introduce two efficient heuristic algorithms that are tested against a lower bound. We also provide computational results to evaluate the performance of the heuristic algorithms.     

Negotiations Within Supply Chains

In this paper we consider a negotiation between a supplier and its retailer. Due to the supplier's commitments with other customers the negotiation is about the maximum order quantity the retailer can order at a fixed price. We propose a structuring for the negotiation that captures two main features: First, we take into account that the supplier can strategically change its production facilities. The impact of this strategic decision is captured by the corresponding change of the supplier's cost situation. Second, we consider the uncertainty about the retailer's future demand due to its own customers. The negotiation takes place with respect to different demand scenarios, yielding a variety of possibilities of avoiding negotiation deadlocks.     

Simultaneous Job Scheduling and Resource Allocation on Parallel Machines

Most deterministic production scheduling models assume that the processing time of a job on a machine is fixed externally and known in advance of scheduling. However, in most realistic situations, apart from the machines, it requires additional resources to process jobs, and the processing time of a job is determined internally by the amount of the resources allocated. In these situations, both the cost associated with the job schedule and the cost of the resources allocated should be taken into account. Therefore, job scheduling and resource allocation should be carefully coordinated and optimized jointly in order to achieve an overall cost-effective schedule. In this paper, we study a parallel-machine scheduling model involving both job processing and resource allocation. The processing time of a job is non-increasing with the cost of the allocated resources. The objective is to minimize the total cost including the cost measured by a scheduling criterion and the cost of all allocated resources. We consider two particular problems of this model, one with the scheduling criterion being the total weighted completion time, and the other with that being the weighted number of tardy jobs. We develop a column generation based branch and bound method for finding optimal solutions for these NP-hard problems. The method first formulates the problems as set partitioning type formulations, and then solves the resulting formulations exactly by branch and bound. In the branch and bound, linear relaxations of the set partitioning type formulations are decomposed into master problems and single-machine subproblems and solved by a column generation approach. The algorithms developed based on this method are capable of solving the two problems with a medium size to optimality within a reasonable computational time.     

考虑促销努力与生产努力的供应链召回努力策略研究

考虑一条由单个供应商和单个制造商组成的二级供应链,面对产品召回事件,供应商和制造商都可以通过召回努力来降低召回事件发生的概率。本文研究了供应链最优召回努力策略,研究发现双方的召回努力与初始期望单位召回成本和潜在市场规模有关。当潜在市场规模和初始期望单位召回成本都较小时,双方均选择部分召回努力,当潜在市场规模和初始期望单位召回成本都较大时,双方均选择全部召回努力,否则,供应商选择全额召回努力而制造商选择部分召回努力。由于制造商的促销努力与供应商的生产努力是企业扩大市场规模常用的策略,因此,本文还研究了这两种策略分别对供应链召回努力策略的影响。我们发现这两种策略都能降低双方采取全额召回努力时潜在市场规模的门槛,激励双方增加召回努力,降低产品召回概率并增加供应链成员的利润。特别的,我们还对比了这两种策略对双方召回努力的影响,发现当促销努力成本系数与生产努力成本系数都较小时,两种策略对召回努力的影响相同,当生产努力成本系数足够大时,考虑促销努力时双方的召回努力水平更高,否则,考虑生产努力时双方的召回努力水平更高。