A hybrid two-stage transportation and batch scheduling problem

We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.     

Minimizing number of tardy jobs on a batch processing machine with incompatible job families

In this paper we consider the problem of minimizing number of tardy jobs on a single batch processing machine. The batch processing machine is capable of processing up to B jobs simultaneously as a batch. We are given a set of n jobs which can be partitioned into m incompatible families such that the processing times of all jobs belonging to the same family are equal and jobs of different families cannot be processed together. We show that this problem is NP-hard and present a dynamic programming algorithm which has polynomial time complexity when the number of job families and the batch machine capacity are fixed. We also show that when the jobs of a family have a common due date the problem can be solved by a pseudo-polynomial time procedure.     

The coordination of transportation and batching scheduling

We study a coordinated scheduling problem of production and transportation in which each job is transported to a single batching machine for further processing. There are m vehicles that transport jobs from the holding area to the batching machine. Each vehicle can transport only one job at a time. The batching machine can process a batch of jobs simultaneously where there is an upper limit on the batch size. Each batch to be processed occurs a processing cost. The problem is to find a joint schedule of production and transportation such that the sum of the total completion time and the total processing cost is optimized. For a special case of the problem where the job assignment to the vehicles is predetermined, we provide a polynomial time algorithm. For the general problem, we prove that it is NP-hard (in the ordinary sense) and present a pseudo-polynomial time algorithm. A fully polynomial time approximation scheme for the general problem is obtained by converting an especially designed pseudo-polynomial dynamic programming algorithm.     

Single Machine Batch Scheduling Problem with Resource Dependent Setup and Processing Time in the Presence of Fuzzy Due Date

We consider a batch scheduling problem on a single machine which processes jobs with resource dependent setup and processing time in the presence of fuzzy due-dates given as follows:1. There are n independent non-preemptive and simultaneously available jobs processed on a single machine in batches. Each job j has a processing time and a due-date.2. All jobs in a batch are completed together upon the completion of the last job in the batch. The batch processing time is equal to the sum of the processing times of its jobs. A common machine setup time is required before the processing of each batch.3. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource.4. The due-date of each job is flexible. That is, a membership function describing non-decreasing satisfaction degree about completion time of each job is defined.5. Under above setting, we find an optimal batch sequence and resource values such that the total weighted resource consumption is minimized subject to meeting the job due-dates, and minimal satisfaction degree about each due-date of each job is maximized. But usually we cannot optimize two objectives at a time. So we seek non-dominated pairs i.e. the batch sequence and resource value, after defining dominance between solutions.A polynomial algorithm is constructed based on linear programming formulations of the corresponding problems.     

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

Minimizing makespan on a single burn-in oven in semiconductor manufacturing

This paper considers a scheduling problem for a single burn-in oven in semiconductor manufacturing industry where the oven is a batch processing machine and each batch processing time is represented by the largest processing time among those of all the jobs contained in the batch. The objective measure of the problem is the maximum completion time (makespan) of all jobs. This paper investigates a static case in which all jobs are available to process at time zero, and also analyzes a dynamic case with different job-release times, for which a branch-and-bound algorithm and several heuristics are exploited. The worst case error performance ratios of the heuristics are also derived.     

Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan

This paper studies the bicriteria problem of scheduling n jobs on a serial-batching machine to minimize maximum cost and makespan simultaneously. A serial-batching machine is a machine that can handle up to b jobs in a batch and jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the sum of the processing times of jobs in the batch. When a new batch starts, a constant setup time s occurs. We confine ourselves to the unbounded model, where b ≥ n. We present a polynomial-time algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem.     

极小化最大完工时间的单机分批加工问题

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b相似文献   

工件的运输和继列分批加工协作排序问题

近年来,工件的运输和加工协作排序问题在物流和供应链管理领域得到广泛关注. 讨论了先用 $\ m$ 台车辆将工件从等待区域运输到继列分批处理机处, 再进行分批加工的协作排序问题, 加工一批工件需要支付一定的费用, 目标为最小化工件的总完工时间与批的加工费用之和. 在工件的加工时间都相等的情况下, 如果工件运输方案确定, 给出了多项式时间的动态规划算法; 如果工件运输方案不确定, 证明了该问题是{\, NP}-难的, 给出了车辆返回时间 $\ t=0$ 时, 最差性能比等于 $\ 2-\frac{1}{m}$ 的近似算法.     

Scheduling on a Batch Processing Machine with Split Compatibility Graphs

We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. All jobs are available at the same date. The capacity of the batch processing machine is finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem and present polynomial algorithms for several special cases.     

ON-LINE PROBLEMS OF MINIMIZING MAKESPAN ON A SINGLE BATCH PROCESSING MACHINE WITH NONIDENTICAL JOB SIZES

The on-line problem of scheduling on a batch processing machine with nonidentical job sizes to minimize makespan is considered. The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. The paper deals with two variants： the case only with two distinct arrival times and the general case. For the first case, an on-line algorithm with competitive ratio 119/44 is given. For the latter one, a simple algorithm with competitive ratio 3 is given. For both variants the better ratios can be obtained if the problem satisfies proportional assumption.     

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.     

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.     

An iterative approach for the serial batching problem with parallel machines and job families

In this paper, we consider a parallel machine scheduling problem to minimize the total completion time. Each job belongs to a certain family. All jobs of one family have identical processing times. Major setups occur between jobs of different families, and we include sequence dependencies. Batches of jobs belonging to the same family can be formed to avoid these setups. Furthermore, we assume serial batching and batch availability. Therefore, the processing time of a batch is the sum of the processing times of all jobs grouped into the corresponding batch. An iterative method is developed for solving this specific problem. This approach alternates between varying batch sizes using an efficient heuristic and sequencing batches based on variable neighborhood search (VNS). Computational results demonstrate that the iterative heuristic outperforms heuristics based on a fixed batch size and list scheduling.     

带有分批费用的容量有界的单机平行分批排序问题

考虑的问题是在添加工资费用或包装费用等附加的分批费用下,如何使单机平行分批中总完工时间和分批费用之和达到最小.首先我们假定工件和批处理机都在零时刻到达,工件被成批地进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用.然后对具有m个不同的加工时间,批容量有界且为固定值b的情形下目标函数为∑C_j与分批费用之和这一排序问题,利用动态规划的方法给出了多项式时间算法,时间界为O(b²m2m²222^m).     

极小化总完工时间的同时加工排序

讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况.     

Scheduling a single machine with multiple job processing ability to minimize makespan

This paper investigates a new problem, called single machine scheduling with multiple job processing ability, which is derived from the production of the continuous walking beaming reheating furnace in iron and steel industry. In this problem, there is no batch and the jobs enter and leave the machine one by one and continuously, which is different from general single machine batch scheduling problem where the jobs in a batch share the same start and departure time. Therefore, the start time and the departure time of a job depend on not only the job sequence but also the machine capacity. This problem is also different from the single semi-continuous batching machine scheduling recently studied in the literature, where the jobs are processed in batch mode and a new batch cannot be started for processing until the processing of the previous batch is completed though jobs in the same batch enter and leave the machine one by one. The objective of this problem is to minimize the makespan. We formulate this problem as a mixed integer linear programming model and propose a particle swarm optimization (PSO) algorithm for this problem. Computational results on randomly generated instances show that the proposed PSO algorithm is effective.     

Minimizing due date related performance measures on two batch processing machines

This paper considers a scheduling problem in a two-machine flowshop of two batch processing machines. On each batch processing machine, jobs are processed in a batch, and each batch is allowed to contain jobs up to the maximum capacity of the associated machine. The scheduling problem is analyzed with respect to three due date related objectives including maximum tardiness, number of tardy jobs and total tardiness. In the analysis, several solution properties are characterized and based upon these properties, three efficient polynomial time algorithms are developed for minimizing the due date related measures.     

Batch scheduling with controllable setup and processing times to minimize total completion time

We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n³ log n) and O(n⁵) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems.     

Dynamic Scheduling on a Single Batch Processing Machine with Split Compatibility Graphs

We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. Jobs have release dates. The capacity of the batch processing machine is finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem and present polynomial algorithms for several special cases. Relating scheduling theory and graph theory appears to be an interesting and important concept.