Bounded parallel-batching scheduling with two competing agents

We consider a scheduling problem in which two agents, each with a set of non-preemptive jobs, compete to perform their jobs on a common bounded parallel-batching machine. Each of the agents wants to minimize an objective function that depends on the completion times of its own jobs. The goal is to schedule the jobs such that the overall schedule performs well with respect to the objective functions of both agents. We focus on minimizing the makespan or the total completion time of one agent, subject to an upper bound on the makespan of the other agent. We distinguish two categories of batch processing according to the compatibility of the agents. In the case where the agents are incompatible, their jobs cannot be processed in the same batch, whereas all the jobs can be processed in the same batch when the agents are compatible. We show that the makespan problem can be solved in polynomial time for the incompatible case and is NP-hard in the ordinary sense for the compatible case. Furthermore, we show that the latter admits a fully polynomial-time approximation scheme. We prove that the total completion time problem is NP-hard and is polynomially solvable for the incompatible case with a fixed number of job types.     

Single machine batch scheduling to minimize total completion time and resource consumption costs

In this paper we study the single-machine batch scheduling problem under batch availability, where both setup and job processing times are controllable by allocating a continuously divisible nonrenewable resource. Under batch availability a set of jobs is processed contiguously and completed together, when the processing of the last job in the batch is finished. We present polynomial time algorithms to find the job sequence, the partition of the job sequence into batches and the resource allocation, which minimize the total completion time or the total production cost (inventory plus resource costs).     

极小化加权完工时间和的无界批量机器并行调度问题

考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工B≥n个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).     

Algorithms for scheduling incompatible job families on single batching machine with limited capacity

Motivated by applications in food processing and semiconductor manufacturing industries, we consider the scheduling problem of a batching machine with jobs of multiple families. The machine has a limited capacity to accommodate jobs. The jobs are in arbitrary sizes and multiple families. Jobs from different families cannot be processed in a batch. We show the problems of minimizing makespan and total batch completion time are both NP-hard in the strong sense. We present a mixed integer programming model for the problems. Then we propose two polynomial time heuristics based on longest processing time first rule and first fit rule. For the special case where a larger job also has a longer processing time, the heuristic for minimizing makespan is optimal. For the general case, we show the performance guarantee of the methods for the two objectives respectively.     

Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains

We study a supply chain scheduling problem in which n jobs have to be scheduled on a single machine and delivered to m customers in batches. Each job has a due date, a processing time and a lateness penalty (weight). To save batch-delivery costs, several jobs for the same customer can be delivered together in a batch, including late jobs. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time has to be added before processing the first job in each batch. The objective is to find a schedule which minimizes the sum of the weighted number of late jobs and the delivery costs. We present a pseudo-polynomial algorithm for a restricted case, where late jobs are delivered separately, and show that it becomes polynomial for the special cases when jobs have equal weights and equal delivery costs or equal processing times and equal setup times. We convert the algorithm into an FPTAS and prove that the solution produced by it is near-optimal for the original general problem by performing a parametric analysis of its performance ratio.     

释放时间和工期同序的单机连续型批调度问题

本文研究的连续型批处理机调度问题, 是在钢铁工业管坯的加热过程中提出来的. 工件带有释放时间和工期, 工件进入和离开机器是按周期依次进行的. 本文针对单机连续型批调度问题中工件释放时间和工期同序的情况, 分析了极小化最大拖期和拖期工件数等问题的计算复杂性, 证明了两类问题都是强NP-难的. 对于工件的释放时间和加工时间、工期都同序的特殊情况, 分别给出了能够获得对应问题的最优解的多项式算法.     

Batching and scheduling in a multi-machine flow shop

We study the problem of batching and scheduling n jobs in a flow shop comprising m, m≥2, machines. Each job has to be processed on machines 1,…,m in this order. Batches are formed on each machine. A machine dependent setup time precedes the processing of each batch. Jobs of the same batch are processed on each machine sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs of the same batch formed on machine l become available for a downstream operation on machine l+1 at the same time when the processing of the last job of the batch on machine l has been finished. The objective is to minimize maximum job completion time. We establish several properties of an optimal schedule and develop polynomial time algorithms for important special cases. They are improvements over the existing methods with regard to their generality and time efficiency.     

Scheduling a batch processing machine with incompatible job families

The problem of scheduling batch processors is important in some industries and, at a more fundamental level, captures an element of complexity common to many practical scheduling problems. We describe a branch and bound procedure applicable to a batch processor model with incompatible job families. Jobs in a given family have identical job processing times, arbitrary job weights, and arbitrary job sizes. Batches are limited to jobs from the same family. The scheduling objective is to minimize total weighted completion time. We find that the procedure returns optimal solutions to problems of up to about 25 jobs in reasonable CPU time, and can be adapted for use as a heuristic for larger problems.     

Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure

A batch processing machine can simultaneously process several jobs forming a batch. This paper considers the problem of scheduling jobs with non-identical capacity requirements, on a single-batch processing machine of a given capacity, to minimize the makespan. The processing time of a batch is equal to the largest processing time of any job in the batch. We present some dominance properties for a general enumeration scheme and for the makespan criterion, and provide a branch and bound method. For large-scale problems, we use this enumeration scheme as a heuristic method.Scope and purposeUsually in classical scheduling problems, a machine can perform only one job at a time. Although, one can find machines that can process several jobs simultaneously as a batch. All jobs of a same batch have common starting and ending times. Batch processing machines are encountered in many different environments, such as burn-in operations in semiconductor industries or heat treatment operations in metalworking industries. In the first case, the capacity of the machine is defined by the number of jobs it can hold. In the second case, each job has a certain capacity requirement and the total size of a batch cannot exceed the capacity of the machine. Hence, the number of jobs contained in each batch may be different. In this paper, we consider this second case (which is more difficult) and we provide an exact method for the makespan criterion (minimizing the last ending time).     

Common due date assignment and scheduling with a rate-modifying activity to minimize the due date,earliness, tardiness,holding, and batch delivery cost

e consider a single-machine batch delivery scheduling and common due date assignment problem. In addition to making decisions on sequencing the jobs, determining the common due date, and scheduling job delivery, we consider the option of performing a rate-modifying activity on the machine. The processing time of a job scheduled after the rate-modifying activity decreases depending on a job-dependent factor. Finished jobs are delivered in batches. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find a common due date for all the jobs, a location of the rate-modifying activity, and a delivery date for each job to minimize the sum of earliness, tardiness, holding, due date, and delivery cost. We provide some properties of the optimal schedule for the problem and present polynomial algorithms for some special cases.     

Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals

This paper considers a scheduling problem for a single burn-in oven in the 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. Each job belongs to one of the given number of families. Moreover, the release times of the jobs are different from one another. The objective measure of the problem is the maximum completion time (makespan) of all jobs. A dynamic programming algorithm is proposed in the order of polynomial time complexity for a situation where the number of job families is given (fixed). A computational experiment is performed to compare the time complexity of the proposed algorithm with that of another exact algorithm evaluating all possible job sequences based on batching-dynamic programming (BDP). The results of the experiment show that the proposed algorithm is superior to the other.Scope and purposeThis paper considers a scheduling problem on the burn-in operation in a semiconductor manufacturing process. The burn-in operation is a bottleneck process in the final testing process which is one of four major steps including wafer fabrication, wafer probe, assembly, and final testing steps. Thus, its scheduling is very important to improve the productivity of the whole manufacturing line. The objective of this paper is to find a solution technique that will find the optimal schedule that minimizes makespan for problems which are found in the semiconductor manufacturing industry.     

Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations

Scheduling with learning effects has attracted growing attention of the scheduling research community. A recent survey classifies the learning models in scheduling into two types, namely position-based learning and sum-of-processing-times-based learning. However, the actual processing time of a given job drops to zero precipitously as the number of jobs increases in the first model and when the normal job processing times are large in the second model. Motivated by this observation, we propose a new learning model where the actual job processing time is a function of the sum of the logarithm of the processing times of the jobs already processed. The use of the logarithm function is to model the phenomenon that learning as a human activity is subject to the law of diminishing return. Under the proposed learning model, we show that the scheduling problems to minimize the makespan and total completion time can be solved in polynomial time. We further show that the problems to minimize the maximum lateness, maximum tardiness, weighted sum of completion times and total tardiness have polynomial-time solutions under some agreeable conditions on the problem parameters.     

Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time-dependent learning effect

In this paper, we investigate a time-dependent learning effect in a flowshop scheduling problem. We assume that the time-dependent learning effect of a job was a function of the total normal processing time of jobs scheduled before the job. The following objective functions are explored: the makespan, the total flowtime, the sum of weighted completion times, the sum of the kth power of completion times, and the maximum lateness. Some heuristic algorithms with worst-case analysis for the objective functions are given. Moreover, a polynomial algorithm is proposed for the special case with identical processing time on each machine and that with an increasing series of dominating machines, respectively. Finally, the computational results to evaluate the performance of the heuristics are provided.     

A DP algorithm for minimizing makespan and total completion time on a series-batching machine

This paper studies a bicriteria scheduling problem on a series-batching machine with objective of minimizing makespan and total completion time simultaneously. A series-batching machine is a machine that can handle up to b jobs in a batch and the completion time of all jobs in a batch is equal to the finishing time of the last job in the batch and the processing time of a batch is the sum of the processing times of jobs in the batch. In addition, there is a constant setup time s for each batch. For the problem we can find all Pareto optimal solutions in O(n²) time by a dynamic programming algorithm, where n denotes the number of jobs.     

One-machine scheduling problems with deteriorating jobs and position-dependent learning effects under group technology considerations

In this paper, we introduce a group scheduling model with general deteriorating jobs and learning effects in which deteriorating jobs and learning effects are both considered simultaneously. This means that the actual processing time of a job depends not only on the processing time of the jobs already processed, but also on its scheduled position. In our model, the group setup times are general linear functions of their starting times and the jobs in the same group have general position-dependent learning effects and time-dependent deterioration. The objective of scheduling problems is to minimise the makespan and the sum of completion times, respectively. We show that the problems remain solvable in polynomial time under the proposed model.     

Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem

We consider the single machine multi-operation jobs total completion time scheduling problem. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a set-up time. A job completes when all of its operations have been processed. The objective is to minimize the sum of the job completion times. In the literature, the computational complexity of this problem is posed as open. We show that the problem is strongly NP-hard even when the set-up times are common and the processing time of each operation is 0 or 1.     

Scheduling a variable maintenance and linear deteriorating jobs on a single machine

We investigate a single machine scheduling problem in which the processing time of a job is a linear function of its starting time and a variable maintenance on the machine must be performed prior to a given deadline. The goals are to minimize the makespan and the total completion time. We prove that both problems are NP-hard. Furthermore, we show that there exists a fully polynomial time approximation scheme for the makespan minimization problem. For the total completion time minimization problem we point out that there exists a fully polynomial time approximation scheme for a special case.     

具有最大作业延迟的生产调度优化算法及仿真

成组作业优化调度问题中的作业根据其加工特点要求可分成若干作业类。同一类的作业连续加工，其后的作业不需要机器设置花费，而不同类的作业连续加工，其后的作业需要机器设置花费。当优化目标是最大作业延迟时，单机成组作业优化调度是HP—hard。本文在利用优化性质的基础上，提出了一种适于大规模优化调度问题的多项式时间算法。仿真实验表明该算法具有良好的性能。     

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

Decision support for unrelated parallel machine scheduling with discrete controllable processing times

In a manufacturing or service system, the actual processing time of a job can be controlled by the amount of an indivisible resource allocated, such as workers or auxiliary facilities. In this paper, we consider unrelated parallel-machine scheduling problems with discrete controllable processing times. The processing time of a job is discretely controllable by the allocation of indivisible resources. The planner must make decisions on whether or how to allocate resources to jobs during the scheduling horizon to optimize the performance measures. The objective is to minimize the total cost including the cost measured by a standard criterion and the total processing cost. We first consider three scheduling criterions: the total completion time, the total machine load, and the total earliness and tardiness penalties. If the number of machines and the number of possible processing times are fixed, we develop polynomial time algorithms for the considered problems. We then consider the minimization problem of the makespan cost plus the total processing cost and present an integer programming method and a heuristic method to solve the studied problem.