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.     

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.     

Improved algorithm for a generalized on-line scheduling problem on identical machines

This paper considers the problem of on-line scheduling a list of independent jobs in which each job has an arbitrary release time on m parallel identical machines. In this problem, jobs arrive in form of order before its release time and decisions have to be made whenever an order is placed and the orders arrive according to any sequence. A heuristic algorithm, NMLS, better than MLS is given for any m ? 2. The competitive ratio is improved from 2.93920 to 2.78436.     

An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines

We consider the problem of on-line scheduling a set of n jobs on two parallel batch processing machines. The objective is to minimize the makespan. We provide an algorithm for the problem that is better than one given in the literature, improving the competitive ratio from to .     

On the on-line rent-or-buy problem in probabilistic environments

Fujiwara and Iwama [In: The 13th Annual International Symposium on Algorithms and Computation, pp. 476–488 (2002)] first integrated probability distribution into the classical competitive analysis to study the rental problem. They assumed that the future inputs are drawn from an exponential distribution, and obtained the optimal competitive strategy and the competitive ratio by the derivative method. In this paper, we introduce the interest rate and tax rate into the continuous model of Fujiwra and Iwama [In: The 13th Annual International Symposium on Algorithms and Computation, pp. 476–488 (2002)]. Moreover, we use the forward difference method in different probabilistic environments to consider discrete leasing models both with and without the interest rate. We not only give the optimal competitive strategies and their competitive ratios in theory, but also give numerical results. We find that with the introduction of the interest rate and tax rate, the uncertainty involved in the process of decision making will diminish and the optimal purchasing date will be put off.     

具有学习效应的三层供应链排序问题

研究了具有学习效应的三层供应链排序问题. 多个客户分布在不同位置,每个客户都有订 单需要制造商进行生产. 制造商需要针对每一个不同订单的客户从不同的地方进购对应的原材料进行生产,生产完工后需要利用有限的车辆将工件运输到相应客户处. 要求每辆运输车装载尽可 能多的货物才开始运输. 利用动态规划算法研究了最大流程时间、总流程时间以及最大延迟三个目标函数.     

Randomized on-line scheduling on three processors

We consider a randomized on-line scheduling problem where each job has to be scheduled on any of m identical processors. The objective is to minimize the expected makespan. We show that the competitive ratio of any randomized algorithm for m=3 processors must be strictly greater than .     

Supply chain scheduling: Sequence coordination

A critical issue in supply chain management is coordinating the decisions made by decision makers at different stages, for example a supplier and one or several manufacturers. We model this issue by assuming that both the supplier and each manufacturer have an ideal schedule, determined by their own costs and constraints. An interchange cost is incurred by the supplier or a manufacturer whenever the relative order of two jobs in its actual schedule is different from that in its ideal schedule. An intermediate storage buffer is available to resequence the jobs between the two stages. We consider the problems of finding an optimal supplier's schedule, an optimal manufacturer's schedule, and optimal schedules for both. The objective functions we consider are the minimization of total interchange cost, and of total interchange plus buffer storage cost. We describe efficient algorithms for all the supplier's and manufacturers’ problems, as well as for a special case of the joint scheduling problem. The running time of these algorithms is polynomial in both the number of jobs and the number of manufacturers. Finally, we identify conditions under which cooperation between the supplier and a manufacturer reduces their total cost.     

A genetic algorithm for the two-stage supply chain distribution problem associated with a fixed charge

This paper considers a two-stage distribution problem of a supply chain that is associated with a fixed charge. Two kinds of cost are involved in this problem: a continuous cost that linearly increases with the amount transported between a source and a destination, and secondly, a fixed charge, that incurs whenever there exists a transportation of a non-zero quantity between a source and a destination. The objective criterion is the minimisation of the total cost of distribution. A genetic algorithm (GA) that belongs to evolutionary search heuristics is proposed and illustrated. The proposed methodology is evaluated for its solution quality by comparing it with the approximate and lower bound solutions. Thus, the comparison reveals that the GA generates better solution than the approximation method and is capable of providing solution either equal or closer to the lower bound solution of the problem.     

Approximation of the supply scheduling problem

The supply scheduling problem consists in finding a minimum cost delivery plan from a set of providers to a manufacturing unit, subject to given bounds on the shipment sizes and subject to the demand at the manufacturing unit. We provide a fully polynomial time approximation scheme for this problem.     

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.     

Extension of algorithm list scheduling for a semi-online scheduling problem

A general algorithm, called ALG, for online and semi-online scheduling problem Pm||C _max with m ≥ 2 is introduced. For the semi-online version, it is supposed that all job have their processing times within the interval [p, rp], where p > 0,1 < r ≤ m/m − 1. ALG is a generalization of LS and is optimal in the sense that there is not an algorithm with smaller competitive ratio than that of ALG.     

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

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

A two-phase ant colony algorithm for multi-echelon defective supply chain network design

Supply chain system is an integrated production system of a product. In the past researches, this system was often assumed to be an equilibrium structure, but in real production process, some members in this system usually cannot effectively complete their production task because of the losses of production, which will reduce the performance of the whole supply chain production system. This supply chain with the losses of production is called the defective supply chain (DSC) system. This research will discuss the partner selection and the production–distribution planning in this DSC network system. Besides the cost of production and transportation, the reliability of the structure and the unbalance of this system caused by the losses of production are considered. Then a germane mathematical programming model is developed for solving this problem. Due to the complex problem and in order to get a satisfactory near-optimal solution with great speed, this research proposes seeking the solution with the solving model based on ant colony algorithm. The application results in real cases show that the solving model presented by this research can quickly and effectively plan the most suitable type of the DSC network and decision-making of the production–distribution. Finally, a comparative numerical experiment is performed by using the proposed approach and the common single-phase ant colony algorithm (SAC) to demonstrate the performance of the proposed approach. The analysis results show that the proposed approach can outperform the SAC in partner selection and production–distribution planning for DSC network design.     

On-line scheduling on a batch processing machine with unbounded batch size to minimize the makespan

We present on-line algorithms to minimize the makespan on a single batch processing machine. We consider a parallel batching machine that can process up to b jobs simultaneously. Jobs in the same batch complete at the same time. Such a model of a batch processing machine has been motivated by burn-in ovens in final testing stage of semiconductor manufacturing. We deal with the on-line scheduling problem when jobs arrive over time. We consider a set of independent jobs. Their number is not known in advance. Each job is available at its release date and its processing requirement is not known in advance. This general problem with infinite machine capacity is noted 1∣p − batch, r_j, b = ∞∣C_max. Deterministic algorithms that do not insert idle-times in the schedule cannot be better than 2-competitive and a simple rule based on LPT achieved this bound [Z. Liu, W. Yu, Scheduling one batch processor subject to job release dates, Discrete Applied Mathematics 105 (2000) 129–136]. If we are allowed to postpone start of jobs, the performance guarantee can be improved to 1.618. We provide a simpler proof of this best known lower bound for bounded and unbounded batch sizes. We then present deterministic algorithms that are best possible for the problem with unbounded batch size (i.e., b = ∞) and agreeable processing times (i.e., there cannot exist an on-line algorithm with a better performance guarantee). We then propose another algorithm that leads to a best possible algorithm for the general problem with unbounded batch size. This algorithm improves the best known on-line algorithm (i.e. [G. Zhang, X. Cai, C.K. Wong, On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics 48 (2001) 241–258]) in the sense that it produces a shortest makespan while ensuring the same worst-case performance guarantee.     

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

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

Coordination mechanism for a deteriorating item in a two-level supply chain system

The subject of the coordination between the suppliers and the buyers in multi-echelon inventory-distribution systems has been studied by many researchers. This paper considers a supply chain including a manufacturer and several buyers and assumes that the inventory items deteriorate over time and its inventory level decreases. In order to determine the order policies, coordination over the supply chain is achieved by scheduling the buyers’ delivery days and their coordination with the manufacturer’s production cycle. A mathematical model is developed and analyzed. To test the efficiency of the proposed model, two other models with the supposition of lot-sizing policies with common order cycle and independent deciding are also developed. In comparison to the other two models, the numerical results show that the synchronizing model of production and delivery cycles works better and has less total cost. In addition, in order to encourage the buyers in cooperation, a model on profit sharing is proposed that equitably shares the total savings with all the parties.     

An O(n2) algorithm for a controllable machine scheduling problem

A single-machine scheduling problem with controllable processingtimes is discussed in this paper. For some jobs, the processingtime can be crashed up to u units of time with the additionalcost c per unit of time crashed. The object is to find an optimalprocessing sequence as well as crash activities to minimizetotal costs of completion and crash. This problem is shown tobe polynomially solvable, and an O(n²) algorithm is given togetherwith the theoretical proof.     

On-line scheduling to minimize average completion time revisited

We consider the scheduling problem of minimizing the average-weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.     

A heuristic algorithm for the hospital health examination scheduling problem

This study considers the problem of health examination scheduling. Depending on their gender, age, and special requirements, health examinees select one of the health examination packages offered by a health examination center. The health examination center must schedule all the examinees, working to minimize examinee/doctor waiting time and respect time and resource constraints, while also taking other limitations, such as the sequence and continuity of the examination procedures, into consideration. The Binary integer programming (BIP) model is one popular way to solve this health examination scheduling problem. However, as the number of examinees and health examination procedures increase, solving BIP models becomes more and more difficult, if not impossible. This study proposes health examination scheduling algorithm (HESA), a heuristic algorithm designed to solve the health examination scheduling problem efficiently and effectively. HESA has two primary objectives: minimizing examinee waiting time and minimizing doctor waiting time. To minimize examinee waiting time, HESA schedules the various parts of each examinee’s checkup for times when the examinee is available, taking the sequence of the examination procedures and the availability of the resources required into account. To minimize doctor waiting time, HESA focuses on doctors instead of examinees, assigning waiting examinees to a doctor as soon as one becomes available. Both complexity analysis and computational analyses have shown that HESA is very efficient in solving the health examination scheduling problem. In addition to the theoretical results, the results of HESA’s application to the concrete health examination scheduling problems of two large hospitals in Taiwan are also reported.