A study of the single-machine two-agent scheduling problem with release times

In many management situations, multiple agents compete on the usage of common processing resources. On the other hand, the importance of the ready times can be shown in Wafer fabrication with the presence of unequal ready times. It is sometimes advantageous to form a non-full batch, while in other situations it is a better strategy to wait for future job arrivals in order to increase the fullness of the batch. However, research on scheduling with two-agent and ready time simultaneously is relatively unexplored. This paper addresses a single-machine two-agent scheduling problem with ready times. The aim is to find an optimal schedule to minimize the total completion time of the jobs of the first agent with the restriction that total completion time is allowed an upper bound for the second agent. To the best of our knowledge, the problem under study has not been considered. Firstly, we show that the proposed problem is strongly NP-hard. Following that, we then develop a branch-and-bound, an ant colony, and four genetic algorithms for an optimal and near-optimal solution, respectively. In addition, the extensive computational experiments are also given.     

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.     

Job scheduling methods for reducing waiting time variance

Minimizing Waiting Time Variance (WTV) is a job scheduling problem where we schedule a batch of n$n$ jobs, for servicing on a single resource, in such a way that the variance of their waiting times is minimized. Minimizing WTV is a well known scheduling problem, important in providing Quality of Service (QoS) in many industries. Minimizing the variance of job waiting times on computer networks can lead to stable and predictable network performance. Since the WTV minimization problem is NP-hard, we develop two heuristic job scheduling methods, called Balanced Spiral and Verified Spiral, which incorporate certain proven properties of optimal job sequences for this problem. We test and compare our methods with four other job scheduling methods on both small and large size problem instances. Performance results show that Verified Spiral gives the best performance for the scheduling methods and problems tested in this study. Balanced Spiral produces comparable results, but at less computational cost. During our investigation we discovered a consistent pattern in the plot of WTV over mean of all possible sequences for a set of jobs, which can be used to evaluate the sacrifice of mean waiting time while pursuing WTV minimization.     

A Stronger Complexity Result for the Single Machine Multi-Operation Jobs Scheduling Problem to Minimize the Number of Tardy Jobs

We consider the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs. 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 setup time. A job completes when all of its operations have been processed. The objective is to minimize the number of tardy jobs. In the literature, this problem has been proved to be strongly NP-hard for arbitrary due-dates. We show in this paper that the problem remains strongly NP-hard even when the due-dates are common and all jobs have the same processing time.     

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.     

Job scheduling to minimize the weighted waiting time variance of jobs

This study considers the job scheduling problem of minimizing the weighted waiting time variance (WWTV) of jobs. It is an extension of WTV minimization problems in which we schedule a batch of n jobs, for servicing on a single resource, in such a way that the variance of their waiting times is minimized. WWTV minimization finds its applications for job scheduling in manufacturing systems with earliness and tardiness (E/T) penalties, in computer and networks systems for the stabilized QoS, and in other fields where it is desirable to minimize WWTV of jobs with different weights for priorities. We formulate a WWTV problem as an integer programming problem, prove the V-shape property for agreeably weighted WWTV problems and the nondelay property for general WWTV problems, and discover the strong V-Shape tendency of the optimal job sequences for this problem. Two job scheduling algorithms, Weighted Verified Spiral (WVS) and Weighted Simplified Spiral (WSS), are developed for the WWTV problems. Numerical testing shows that WVS and WSS significantly outperform existing WWTV algorithms.     

染缸排产建模及滑动时间窗启发式调度算法

针对染缸排产问题约束复杂、任务规模大、排产效率要求高的特点,为了提高问题模型和算法在实际场景中的适用性,建立了染缸排产增量调度模型,提出了滑动时间窗启发式调度（STWS）算法。该算法以最小化延误代价、洗缸成本、染缸切换成本为优化目标,使用启发式调度规则,按照优先级顺序调度产品;对于每个产品的调度,先用动态拼缸算法和拆缸算法进行批次划分,然后调用批次最佳排序算法调度批次。使用某染纱企业车间实际生产数据仿真调度,所提算法可在10 s内完成月度计划的调度。相对于人工排产方式,所提算法提高了排产效率,显著优化了三个目标,在增量调度中洗缸成本和染缸切换成本也有明显优化。实验结果表明所提算法具有很好的调度能力。     

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.     

Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence-dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on-time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches.     

基于效率函数求解单件车间调度问题算法的完善

单件小批量生产形式下的单件车间（Job-shop)调度是生产计划中的一个重要问题，本文在文献[1]提出的求解Job-shop调度问题的动排算法及调解算法的基础上，做出了进一步的修改和完善，在调解算法中引入了交换与移动相结合的机制以提高调解效率，并在VBA For Projcet2000中实现了该算法，经分析及实验验证，利用这种算法求解Job-shop调度问题，可得到十分满意的结果。     

A fluid approach to large volume job shop scheduling

We consider large volume job shop scheduling problems, in which there is a fixed number of machines, a bounded number of activities per job, and a large number of jobs. In large volume job shops it makes sense to solve a fluid problem and to schedule the jobs in such a way as to track the fluid solution. There have been several papers which used this idea to propose approximate solutions which are asymptotically optimal as the volume increases. We survey some of these results here. In most of these papers it is assumed that the problem consists of many identical copies of a fixed set of jobs. Our contribution in this paper is to extend the results to the far more general situation in which the many jobs are all different. We propose a very simple heuristic which can schedule such problems. We discuss asymptotic optimality of this heuristic, under a wide range of previously unexplored situations. We provide a software package to explore the performance of our policy, and present extensive computational evidence for its effectiveness.     

A heuristic approach for single-machine scheduling with due dates and class setups

The single-machine sequence-independent class setup scheduling problem is examined in this paper. It is assumed that jobs are classified into classes and a setup is required between jobs of different classes, but not of the same class. Furthermore, this setup time is fixed and depends only on the current job. Since the problem is NP-hard, a heuristic algorithm is proposed to find an approximate schedule that minimizes the maximum lateness on a set of jobs. The algorithm can easily be modified to solve the maximum tardiness problems as well. The accuracy of the heuristic algorithm in generating near optimal solutions is empirically evaluated.Scope and purposeFor batch manufacturing, it maybe desirable to produce many items of the same type, or class, at the same run in order to save the setup cost. However, committing facilities to long production runs for one product may inevitably make others tardy. Small batch size may conform urgent jobs to their delivery date, but one of the consequences would be the loss of productive efficiency due to numerous setups. Therefore, scheduling is basically a trade-off between the inherently conflicting efficiency measure and due-date compliance. This paper considers a single-machine scheduling problem in which jobs are classified into classes and a setup is required between jobs of different classes. The setup time is fixed and depends only on the current job. This problem is called a sequence-independent class setup problem and is NP-complete.     

An effective neighborhood search algorithm for scheduling a flow shop of batch processing machines

This paper considers scheduling problem of flow shop with many batch processing machines and objective of maximum lateness. An effective neighborhood search algorithm (NSA) is proposed for the problem, in which a job permutation and a batch permutation are used to indicate the solution of two sub-problems, respectively. Each job permutation consists of several family-permutations for the representation of jobs from the same family. Two swaps are applied to two permutations to produce new solutions. NSA is applied to a number of instances and compared with some methods, and computational results validate the good performance of NSA.     

Single-machine batch delivery scheduling with job release dates,due windows and earliness,tardiness, holding and delivery costs

This paper deals with a single-machine scheduling problem in which jobs are released in different points in time but delivered to customers in batches. A due window is associated with each job. The objective is to schedule the jobs, to form them into batches and to decide the delivery date of each batch so as to minimize the sum of earliness, tardiness, holding, and delivery costs. A mathematical model of the problem is presented, and a set of dominance properties is established. To solve this NP-hard problem efficiently, a solution method is then proposed by incorporating the dominance properties with an imperialist competitive algorithm. Unforced idleness and forming discontinuous batches are allowed in the proposed algorithm. Moreover, the delivery date of a batch may be decided to be later than the completion time of the last job in the batch. Finally, computational experiments are conducted to evaluate the proposed model and solution procedure, and results are discussed.     

Minimizing Mean Completion Time in a Batch Processing System

We consider batch processing jobs to minimize the mean completion time. A batch processing machine can handle up to $B$ jobs simultaneously. Each job is represented by an arrival time and a processing time. Jobs processed in a batch have the same completion time, i.e., their common starting time plus the processing time of their longest job. For batch processing, non-preemptive scheduling is usually required and we discuss this case. The batch processing problem reduces to the ordinary uniprocessor system scheduling problem if $B=1$. We focus on the other extreme case $B=+\infty$. Even for this seemingly simple extreme case, we are able to show that the problem is NP-hard for the weighted version. In addition, we establish a polynomial time algorithm for a special case when there are only a constant number of job processing times. Finally, we give a polynomial time approximation scheme for the general case.     

用Lagrangian松弛法解化工批处理调度问题

研究基于Lagrangian松弛法的化工批处理过程的调度方法.建立了化工批处理过 程调度问题的一种混合整数规划(MILP)模型,并通过松弛离散变量和连续变量共存的约束, 将问题分解为一个两层次的优化问题,其中上层是原问题的对偶问题,下层由两个子问题构 成:一个与产品批量有关,另一个确定操作时间表,分别用线性规划和动态规划方法解这两个 子问题.然后从对偶问题的解构作原问题的可行解.数值试验结果证明了该方法的有效性.     

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).     

一种MapReduce实时调度算法设计及实现

MapReduce是云计算中重要的批数据处理框架,多任务共享MapReduce机群并满足任务实时性要求是调度算法急需解决的问题。提出两阶段实时调度算法,将调度划分为任务间调度和任务内调度。对于任务间调度,使用抽样法和经验值法确定子任务执行时间,利用该参数建立资源分配模型,动态确定任务优先级进行调度;对于子任务使用延迟调度策略进行调度,保证计算的本地性。实验结果显示,两阶段实时调度算法相比公平调度算法和FIFO算法,在保证吞吐量的同时能够满足任务实时性要求。     

Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters

This paper addresses the problem of minimizing the scheduling length (make-span) of a batch of jobs with different arrival times. A job is described by a direct acyclic graph (DAG) of parallel tasks. The paper proposes a dynamic scheduling method that adapts the schedule when new jobs are submitted and that may change the processors assigned to a job during its execution. The scheduling method is divided into a scheduling strategy and a scheduling algorithm. We also propose an adaptation of the Heterogeneous Earliest-Finish-Time (HEFT) algorithm, called here P-HEFT, to handle parallel tasks in heterogeneous clusters with good efficiency without compromising the makespan. The results of a comparison of this algorithm with another DAG scheduler using a simulation of several machine configurations and job types shows that P-HEFT gives a shorter makespan for a single DAG but scores worse for multiple DAGs. Finally, the results of the dynamic scheduling of a batch of jobs using the proposed scheduler method showed significant improvements for more heavily loaded machines when compared to the alternative resource reservation approach.     

基于动态规划的分批排序算法

研究了在给定截止期限（deadline）下的单机分批（batch）排序问题,目标函数是最大提前完工时间。由于工件不能延迟,因此先讨论了问题可行解的存在。当问题有可行解时,证明了工件按最早截止期限（Earliest Deadline,ED）规则的排序是一个最优排序,接着给出一个时间复杂度为O（n³）的动态规划算法来获得最优分批。