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.     

Scheduling unit length jobs with parallel nested machine processing set restrictions

This article explores the impact of restricting the machines upon which individual jobs may be scheduled. Even the simple case of a single stage of identical parallel machines cannot be solved to optimality in a reasonable time. We therefore focus on the case when job processing times are identical. In some applications the machine processing sets of jobs are structured in a nested fashion and do not partially overlap. We present efficient algorithms for solving this nested problem to optimality for each of the standard scheduling objective functions. In particular, an algorithm with constant running time minimises makespan on a fixed number of machines regardless of the number of jobs. Improvements in efficiency have been gained by attention to implementation issues, thus challenging the conventional approach to evaluating complexity.     

Scheduling nonpreemptive jobs on parallel machines subject to exponential unrecoverable interruptions

In this paper we consider the problem of scheduling n independent jobs on m parallel machines. If, while a machine is processing a job, a failure (unrecoverable interruption) occurs, the current job as well as subsequently scheduled jobs on that machine cannot be performed, and hence do not contribute to the overall revenue or throughput. The objective is to maximize the expected amount of work done before an interruption occurs. In this paper, we investigate the problem when failures are exponentially distributed. We show that the problem is NP-hard, and characterize a polynomially solvable special case. We then propose both an exact algorithm having pseudopolynomial complexity and a heuristic algorithm. A combinatorial upper bound is also proposed for the problem. Experimental results show the effectiveness of the heuristic approach.     

Flowshop scheduling problems with transportation or deterioration between the batching and single machines

In this paper, we consider two new types of the two-machine flowshop scheduling problems where a batching machine is followed by a single machine. The first type is that normal jobs with transportation between machines are scheduled on the batching and single machines. The second type is that normal jobs are processed on the batching machine while deteriorating jobs are scheduled on the single machine. For the first type, we formulate the problem to minimize the makespan as a mixed integer programming model and prove that it is strongly NP-hard. Furthermore, a heuristic algorithm along with a worst case error bound is derived and the computational experiments are also carried out to verify the effectiveness of the proposed heuristic algorithm. For the second type, the two objectives are considered. For the problem with minimizing the makespan, we find an optimal polynomial algorithm. For the problem with minimizing the sum of completion time, we show that it is strongly NP-hard and propose an optimal polynomial algorithm for its special case.     

Parallel machine selection and job scheduling to minimize machine cost and job tardiness

This paper discusses the problem of simultaneously selecting and scheduling parallel machines to minimize the sum of machine holding cost and job tardiness cost. A combinatorial optimization model is developed for this purpose. Solving the developed model is NP-hard. A heuristic algorithm is developed to locate the optimal or near optimal solutions based on a Tabu search mechanism specially designed to control the search process in the solution neighborhood for jobs scheduled on specific machines. Numerical examples show that the solutions of the model lead to compromises between the system cost related to machine selection and the operational cost related to job tardiness penalties. The examples also show that the developed algorithm is effective and computationally efficient.     

Parallel machine scheduling problem to minimize the earliness/tardiness costs with learning effect and deteriorating jobs

The focus of this work is to analyze parallel machine earliness/tardiness (ET) scheduling problem with simultaneous effects of learning and linear deterioration, sequence-dependent setups, and a common due-date for all jobs. By the effects of learning and linear deterioration, we mean that the processing time of a job is defined by an increasing function of its starting time and a decreasing function of the position in the sequence. We develop a mixed integer programming formulation for the problem and show that the optimal sequence is V-shaped: all jobs scheduled before the shortest jobs and all jobs scheduled after the shortest job are in a non-increasing and non-decreasing order of processing times, respectively. The developed model allows sequence-dependent setups and sequence-dependent early/tardy penalties. The illustrative example with 11 jobs for 2 machines and 3 machines shows that the model can easily provide the optimal solution, which is V-shaped, for problem.     

Scheduling jobs on identical machines with agreement graph

We consider the following problem of scheduling with agreements: a set of jobs must be scheduled non-preemptively on identical machines subject to constraints that only some specific jobs can be scheduled concurrently on different machines. These constraints are represented by an agreement graph and the aim is to minimize the makespan. This problem is NP-hard. We study the complexity of the problem for two machines and arbitrary bipartite agreement graphs, in particular we prove the NP-hardness of the open problem proposed in the literature which is the case of two machines with processing times at most 3. We propose list algorithms with empirical results for the problem in the general case.     

三台机并行工件排序问题的改进的下界

与经典的排序问题不同的是,并行工件排序指的是在加工某些工件时,需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标,而竞争比的下界则是算法设计的一个重要参考。利用反证法,通过构造一个特殊的反例,分析了由此产生的全部9种可能的情形,建立了它们对应的9种线性规划模型,借助计算软件证明了前8种情形是不可能的,然后详细分析了第9种情形也是不可能的,从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。     

Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control

Using unrelated parallel machine scheduling to minimize the total earliness and tardiness of jobs with distinct due dates is a nondeterministic polynomial-hard problem. Delayed customer orders may result in penalties and reduce customer satisfaction. On the other hand, early completion creates inventory storage costs, which increase the total cost. Although parallel machines can increase productivity, machine assignments also increase the complexity of production. Therefore, the challenge in parallel machine scheduling is to dynamically adjust the machine assignment to complete the job within the shortest possible time. In this paper, we address an unrelated parallel machine scheduling problem for jobs with distinct due dates and dedicated machines. The objective is to dynamically allocate jobs to unrelated parallel machines in order to minimize the total earliness and tardiness time. We formulate the problem as a mixed integer linear programming (MILP) model and develop a modified genetic algorithm (GA) with a distributed release time control (GARTC) mechanism to obtain the near-optimal solution. A preliminary computational study indicates that the developed GARTC not only provides good quality solutions within a reasonable amount of time, but also outperforms the MILP model, a classic GA and heuristic approaches described in the literature.     

Randomized mechanism design for decentralized network scheduling

ABSTRACT

In the network scheduling, jobs (tasks) must be scheduled on uniform machines (processors) connected by a complete graph so as to minimize the total weighted completion time. This setting can be applied in distributed multi-processor computing environments and also in operations research. In this paper, we study the design of randomized decentralized mechanism in the setting where a set of non-preemptive jobs select randomly a machine from a set of uniform machines to be processed on, and each machine can process at most one job at a time. We introduce a new concept of myopic Bayes–Nash incentive compatibility which weakens the classical Bayes–Nash incentive compatibility and derive a randomized decentralized mechanism under the assumption that each job is a rational and selfish agent. We show that our mechanism can induce jobs to report truthfully their private information referred to myopic Bayes–Nash implementability by using a graph theoretic interpretation of the incentive compatibility constraints. Furthermore, we prove that the performance of this mechanism is asymptotically optimal.     

Heuristics for the two‐machine scheduling problem with a single server

In this paper, the NP‐hard two‐machine scheduling problem with a single server is addressed. The problem consists of a given set of jobs to be scheduled on two identical parallel machines, where each job must be processed on one of the machines, and prior to processing, the job is set up on its machine using one server; the latter is shared between the two machines. An ant colony optimization (ACO) algorithm is introduced for the problem and its performance was assessed by comparing with an exact solution (branch and bound [B&B]), a genetic algorithm (GA), and simulated annealing (SA). The computational results reflected the superiority of “ACO” in large problems, with a performance similar to SA and GA in smaller problems, while solving the tested problems within a reasonable computational time.     

On the identical parallel-machine rescheduling with job rework disruption

This paper investigates an issue of rescheduling on identical parallel machines where the original jobs have already been scheduled to minimize the total completion time, when a single set of jobs to be reworked re-arrives and creates a job rework disruption. Two conflicting rescheduling criteria are considered: the total completion time, as the measure of scheduling cost (efficiency); and the number of jobs assigned to different machines in the original schedule and newly generated schedule, as the measure of disruption cost (stability). Further, the rescheduling problem is defined as a bi-criteria scheduling problem. Two polynomial time algorithms are proposed to lexicographically optimize the two criteria. Besides, the set of all efficient schedules with respect to the two criteria can be also generated in polynomial time.     

Scheduling parallel jobs to minimize the makespan

We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We prove that the makespan of any nonpreemptive list-schedule is within a factor of 2 of the optimal preemptive makespan. This gives the best-known approximation algorithms for both the preemptive and the nonpreemptive variant of the problem. We also show that no list-scheduling algorithm can achieve a better performance guarantee than 2 for the nonpreemptive problem, no matter which priority list is chosen. List-scheduling also works in the online setting where jobs arrive over time and the length of a job becomes known only when it completes; it therefore yields a deterministic online algorithm with competitive ratio 2 as well. In addition, we consider a different online model in which jobs arrive one by one and need to be scheduled before the next job becomes known. We show that no list-scheduling algorithm has a constant competitive ratio. Still, we present the first online algorithm for scheduling parallel jobs with a constant competitive ratio in this context. We also prove a new information-theoretic lower bound of 2.25 for the competitive ratio of any deterministic online algorithm for this model. Moreover, we show that 6/5 is a lower bound for the competitive ratio of any deterministic online algorithm of the preemptive version of the model jobs arriving over time.     

Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times

This research is motivated by a scheduling problem found in the diffusion and oxidation areas of semiconductor wafer fabrication, where the machines can be modeled as parallel batch processors. We attempt to minimize total weighted tardiness on parallel batch machines with incompatible job families and unequal ready times of the jobs. Given that the problem is NP-hard, we propose two different decomposition approaches. The first approach forms fixed batches, then assigns these batches to the machines using a genetic algorithm (GA), and finally sequences the batches on individual machines. The second approach first assigns jobs to machines using a GA, then forms batches on each machine for the jobs assigned to it, and finally sequences these batches. Dispatching and scheduling rules are used for the batching phase and the sequencing phase of the two approaches. In addition, as part of the second decomposition approach, we develop variations of a time window heuristic based on a decision theory approach for forming and sequencing the batches on a single machine.     

Preemptive online scheduling with rejection of unit jobs on two uniformly related machines

We consider preemptive online and semi-online scheduling of unit jobs on two uniformly related machines. Jobs are presented one by one to an algorithm, and each job has a rejection penalty associated with it. A new job can either be rejected, in which case the algorithm pays its rejection penalty, or it can be scheduled preemptively on the machines, in which case it may increase the maximum completion time of any machine in the schedule, also known as the makespan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule of all accepted jobs and the total penalty of all rejected jobs. We study two versions of the problem. The first one is the online problem where the jobs arrive unsorted, and the second variant is the semi-online case, where the jobs arrive sorted by a non-increasing order of penalties. We also show that the variant where the jobs arrive sorted by a non-decreasing order of penalties is equivalent to the unsorted one. We design optimal online algorithms for both cases. These algorithms have smaller competitive ratios than the optimal competitive ratio for the more general problem with arbitrary processing times (except for the case of identical machines), but larger competitive ratios than the optimal competitive ratio for preemptive scheduling of unit jobs without rejection.     

基于到达时间两台并行机上在线批调度

考虑两台同构并行机上在线批调度问题．每个批具有不确定的到达时间,一旦机器可以利用,要在当前可以利用的批中选择出合适的批,并将其中的工件调度到机器上,且工件在加工过程中不允许中断．目标函数是使调度的最大完成时间最小．给出了一个批在线调度ＲＢＬＰＴ算法,即选择当前批中加工时间之和最大的批按ＬＰＴ 规则调度．另外,利用反证法,对算法的最坏情况进行了分析．     

Dynamic programming algorithms for scheduling parallel machines with family setup times

We address the problem of scheduling jobs with family setup times on identical parallel machines to minimize total weighted flowtime. We present two dynamic programming algorithms — a backward algorithm and a forward algorithm — and we identify characteristics of problems where each algorithm is best suited. We also derive two properties that improve the computational efficiency of the algorithms.Scope and purposeWhile most production schedulers must balance conflicting goals of high system efficiency and timely completion of individual jobs, consideration of this conflict is underdeveloped in the scheduling literature. This paper examines a model that incorporates a fundamental cause of the efficiency/timeliness conflict in practice. We propose solution methodologies and properties of an optimal solution for the purpose of exposing insights that may ultimately be useful in research on more complex models.     

On-line hierarchical job scheduling on grids with admissible allocation

In this paper, we address non-preemptive online scheduling of parallel jobs on a Grid. Our Grid consists of a large number of identical processors that are divided into several machines. We consider a Grid scheduling model with two stages. At the first stage, jobs are allocated to a suitable machine, while at the second stage, local scheduling is independently applied to each machine. We discuss strategies based on various combinations of allocation strategies and local scheduling algorithms. Finally, we propose and analyze a scheme named adaptive admissible allocation. This includes a competitive analysis for different parameters and constraints. We show that the algorithm is beneficial under certain conditions and allows for an efficient implementation in real systems. Furthermore, a dynamic and adaptive approach is presented which can cope with different workloads and Grid properties.     

Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times

We revisit the classic problem of preemptive scheduling on m uniformly related machines. In this problem, jobs can be arbitrarily split into parts, under the constraint that every job is processed completely, and that the parts of a job are not assigned to run in parallel on different machines. We study a new objective which is motivated by fairness, where the goal is to minimize the sum of the two maximal job completion times. We design a polynomial time algorithm for computing an optimal solution. The algorithm can act on any set of machine speeds and any set of input jobs. The algorithm has several cases, many of which are very different from algorithms for makespan minimization (algorithms that minimize the maximum completion time of any job), and from algorithms that minimize the total completion time of all jobs.     

A cutting plane approach for integrated planning and scheduling

In this paper we propose a branch-and-cut algorithm for solving an integrated production planning and scheduling problem in a parallel machine environment. The planning problem consists of assigning each job to a week over the planning horizon, whereas in the scheduling problem those jobs assigned to a given week have to be scheduled in a parallel machine environment such that all jobs are finished within the week. We solve this problem in two ways: (1) as a monolithic mathematical program and (2) using a hierarchical decomposition approach in which only the planning decisions are modeled explicitly, and the existence of a feasible schedule for each week is verified by using cutting planes. The two approaches are compared with extensive computational testing.