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

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

Common due date assignment and scheduling with ready times

We consider the problem of scheduling a set of nonsimultaneously available jobs on one machine. Each job has a ready time only at or after which the job can be processed. All the jobs have a common due date, which needs to be determined. The problem is to determine a due date and a schedule so as to minimize a total penalty depending on the earliness, tardiness and due date. We show that this problem is strongly NP-hard and give an efficient algorithm that finds an optimal due date and schedule when either the job sequence is predetermined or all jobs have the same processing time. We also propose three approximation algorithms for the general and special cases together with their experimental analysis.

Scope and purpose

We consider the single machine due date assignment problem for scheduling jobs which are ready for processing at different times. The problem under consideration arises in production planning and scheduling concerning the setting of appropriate due dates for a number of customer orders arriving over time. Most of the earlier publications on this subject assumed that the jobs are ready for processing simultaneously. This assumption is too restrictive for real-life production systems where jobs arrive at different times. We show that the problem with unequal ready times is NP-hard and develop fast heuristic algorithms for it, and exact algorithms for two special cases.     

一种求解车间作业调度问题的混合邻域结构搜索算法

车间作业调度问题是优化组合中一个著名的难题,问题的目标是在满足约束条件的前提下,使调度的加工周期尽可能小。文章中提出了利用新的混合邻域结构进行搜索来求解车间作业调度问题。对于算法关键的邻域构造问题以及跳坑策略给出了提高算法优度的解决方案。采用43个不同规模和难度的国际标准算例做为本算法的测试实验集,39个算例找到了最优解,其中包括著名的难例FT10。与当前国外学者提出的一种先进算法进行了比较,算法的优度高于被比较的先进算法。     

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.     

Minimizing Makespan and Preemption Costs on a System of Uniform Machines

It is well known that for preemptive scheduling on uniform machines there exist polynomial time exact algorithms, whereas for non-preemptive scheduling there are probably no such algorithms. However, it is not clear how many preemptions (in total, or per job) suffice in order to guarantee an optimal polynomial time algorithm. In this paper we investigate exactly this hardness gap, formalized as two variants of the classic preemptive scheduling problem. In generalized multiprocessor scheduling (GMS) we have a job-wise or total bound on the number of preemptions throughout a feasible schedule. We need to find a schedule that satisfies the preemption constraints, such that the maximum job completion time is minimized. In minimum preemptions scheduling (MPS) the only feasible schedules are preemptive schedules with the smallest possible makespan. The goal is to find a feasible schedule that minimizes the overall number of preemptions. Both problems are NP-hard, even for two machines and zero preemptions. For GMS, we develop polynomial time approximation schemes, distinguishing between the cases where the number of machines is fixed, or given as part of the input. Our scheme for a fixed number of machines has linear running time, and can be applied also for instances where jobs have release dates, and for instances with arbitrary preemption costs. For MPS, we derive matching lower and upper bounds on the number of preemptions required by any optimal schedule. Our results for MPS hold for any instance in which a job, J_j, can be processed simultaneously by ρ_j machines, for some ρ_j ≥ 1.     

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.     

Preemptive stochastic online scheduling on two uniform machines

This paper addresses a stochastic online scheduling problem in which a set of independent jobs are to be processed by two uniform machines whose speeds are 1 and s(s?1). Each job has a processing time, which is a random variable with an arbitrary distribution, and all the jobs are arriving overtime, which means that no information of the job is known in advance before its arrival. During the processing, jobs are allowed to be preempted and resumed later. The objective is to minimize the sum of expected weighted completion times. In this paper, the optimal policy, named SMPR, is designed for the single-machine preemptive stochastic scheduling problem where jobs have a common arriving time. Based on SMPR, the online approximative policy-UMPR, is devised for the preemptive stochastic online scheduling on two uniform machines. Then, UMPR is proved to have an approximation factor of 2. Furthermore, it is concluded that UMPR could not have a smaller approximation factor than 2, which means 2 is the approximation ratio of UMPR for the two-uniform-machine scheduling problem.     

Approximation algorithms for scheduling real-time jobs with multiple feasible intervals

Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job is constrained to execute from start to completion in one of its feasible intervals. A job fails if the job remains incomplete at the end of the last feasible interval. Earlier works developed an optimal off-line algorithm to schedule all the jobs in a given job set and on-line heuristics to schedule the jobs in a best effort manner. This paper is concerned with how to find a schedule in which the number of jobs completed in one of their feasible intervals is maximized. We show that the maximization problem is -hard for both non-preemptible and preemptible jobs. This paper develops two approximation algorithms for non-preemptible and preemptible jobs. When jobs are non-preemptible, Algorithm Least Earliest Completion Time First (LECF) is shown to have a 2-approximation factor; when jobs are preemptible, Algorithm Least Execution Time First (LEF) is proved being a 3-approximation algorithm. We show that our analysis for the two algorithms are tight. We also evaluate our algorithms by extensive simulations. Simulation results show that Algorithms LECF and LEF not only guarantee the approximation factors but also outperform other multiple feasible interval scheduling algorithms in average.     

Two branch-and-bound algorithms for the robust parallel machine scheduling problem

Uncertainty is an inevitable element in many practical production planning and scheduling environments. When a due date is predetermined for performing a set of jobs for a customer, production managers are often concerned with establishing a schedule with the highest possible confidence of meeting the due date. In this paper, we study the problem of scheduling a given number of jobs on a specified number of identical parallel machines when the processing time of each job is stochastic. Our goal is to find a robust schedule that maximizes the customer service level, which is the probability of the makespan not exceeding the due date. We develop two branch-and-bound algorithms for finding an optimal solution; the two algorithms differ mainly in their branching scheme. We generate a set of benchmark instances and compare the performance of the algorithms based on this dataset.     

Power-aware scheduling for makespan and flow

We consider offline scheduling algorithms that incorporate speed scaling to address the bicriteria problem of minimizing energy consumption and a scheduling metric. For makespan, we give a linear-time algorithm to compute all non-dominated solutions for the general uniprocessor problem and a fast arbitrarily-good approximation for multiprocessor problems when every job requires the same amount of work. We also show that the multiprocessor problem becomes NP-hard when jobs can require different amounts of work. For total flow, we show that the optimal flow corresponding to a particular energy budget cannot be exactly computed on a machine supporting exact real arithmetic, including the extraction of roots. This hardness result holds even when scheduling equal-work jobs on a uniprocessor. We do, however, extend previous work by Pruhs et al. to give an arbitrarily-good approximation for scheduling equal-work jobs on a multiprocessor.     

Parallel machine scheduling to minimize the makespan with sequence dependent deteriorating effects

A new unrelated parallel machine scheduling problem with deteriorating effect and the objective of makespan minimization is presented in this paper. The deterioration of each machine (and therefore of the job processing times) is a function of the sequence of jobs that have been processed by the machine and not (as considered in the literature) by the time at which each job is assigned to the machine or by the number of jobs already processed by the machine. It is showed that for a single machine the problem can be solved in polynomial time, whereas the problem is NP-hard when the number of machines is greater or equal than two. For the last case, a set of list scheduling algorithms and simulated annealing meta-heuristics are designed and the effectiveness of these approaches is evaluated by solving a large number of benchmark instances.     

Improved algorithms for resource allocation under varying capacity

We consider the problem of scheduling a set of jobs on a system that offers certain resource, wherein the amount of resource offered varies over time. For each job, the input specifies a set of possible scheduling instances, where each instance is given by starting time, ending time, profit and resource requirement. A feasible solution selects a subset of job instances such that at any timeslot, the total requirement by the chosen instances does not exceed the resource available at that timeslot, and at most one instance is chosen for each job. The above problem falls under the well-studied framework of unsplittable flow problem on line. The generalized notion of scheduling possibilities captures the standard setting concerned with release times and deadlines. We present improved algorithms based on the primal–dual paradigm, where the improvements are in terms of approximation ratio, running time and simplicity.     

Jackson's semi-preemptive scheduling on a single machine

We propose an effective improvement of the well-known Jackson's preemptive schedule lower bound for the single machine scheduling problem with heads and tails. The semi-preemptive scheduling concept roughly consists in reducing the preemption impact by constraining some particular job parts to be processed in reduced time intervals. The impact of semi-preemptive scheduling is twofold: it yields a lower bound which dominates the preemptive one, and enables more effective adjustments of the heads and tails. Our experimental study revealed that suitably embedding our procedure within Carlier's algorithm makes feasible to solve all of the hard instances which could not be solved by its original variant.     

Improving responsiveness of soft aperiodic tasks using proportional slack time

In a real-time system with both hard real-time periodic jobs and soft real-time aperiodic jobs, it is important to guarantee that the deadline of each periodic job is met, as well as to provide a fast response time for each aperiodic job. We propose an algorithm, called Proportional Slack Reserve (PSR), that produces an efficient schedule for such an environment. For every execution unit of a periodic job, the PSR algorithm reserves time which can be used for execution of aperiodic jobs. If reserved time is not available, the algorithm assigns a deadline to an aperiodic job for achieving better responsiveness of aperiodic jobs. The proposed algorithm can fully utilize processing power while meeting all deadlines of periodic jobs. It can also easily reclaim the time unused by the periodic job. We analytically show that for each aperiodic job, the response time in a PSR schedule is no longer than that in a TBS schedule, which is known to be efficient for servicing aperiodic jobs. We also present simulation results in which the response time of PSR is significantly improved over that of TBS, and moreover the performance of PSR compares favorably with TB(N) considering scheduling overhead.     

Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness

In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.     

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

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

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.     

Multiprocessor Scheduling with Machine Allotment and Parallelism Constraints

Abstract. Modern computer systems distribute computation among several machines to speed up the execution of programs. Yet, setup and communication costs, as well as parallelism constraints, bound the number of machines that can share the execution of a given application, and the number of machines by which it can be processed simultaneously . We study the resulting scheduling problem, stated as follows. Given a set of n jobs and m uniform machines, assign the jobs to the machines subject to parallelism and machine allotment constraints, such that the overall completion time of the schedule (or makespan ) is minimized. Indeed, the multiprocessor scheduling problem (where each job can be processed by a single machine) is a special case of our problem; thus, our problem is strongly NP-hard. We present a (1+ α) -approximation algorithm for this problem, where α ∈ (0,1] depends on the minimal number of machine allotments and the minimal parallelism allowed for any job. Also, we show that when the maximal number of machines that can share the execution of a job is some fixed constant, our problem has a polynomial time approximation scheme ; for other special cases we give optimal polynomial time algorithms. Finally, through the relation of our problem to the classic preemptive scheduling problem on multiple machines, we shed some fresh light on what is known in scheduling folklore as the power of preemption.     

An integer programming approach to the multimode resource-constrained multiproject scheduling problem

The project scheduling problem (PSP) is the subject of several studies in computer science, mathematics, and operations research because of the hardness of solving it and its practical importance. This work tackles an extended version of the problem known as the multimode resource-constrained multiproject scheduling problem. A solution to this problem consists of a schedule of jobs from various projects, so that the job allocations do not exceed the stipulated limits of renewable and nonrenewable resources. To accomplish this, a set of execution modes for the jobs must be chosen, as the jobs’ duration and amount of needed resources vary depending on the mode selected. Finally, the schedule must also consider precedence constraints between jobs. This work proposes heuristic methods based on integer programming to solve the PSP considered in the Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA) 2013 Challenge. The developed solver was ranked third in the competition, being able to find feasible and competitive solutions for all instances and improving best known solutions for some problems.     

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.