考虑分时电价的多目标批调度问题蚁群算法求解

对同时优化电力成本和制造跨度的多目标批处理机调度问题进行了研究,设计了两种多目标蚁群算法,基于工件序的多目标蚁群算法(J-PACO,Job-based Pareto Ant Colony Optimization)和基于成批的多目标蚁群算法(B-PACO,Batch-based Pareto Ant Colony Optimization)对问题进行求解分析。由于分时电价中电价是时间的函数,因而在传统批调度进行批排序的基础上,需要进一步确定批加工时间点以测定电力成本。提出的两种蚁群算法分别将工件和批与时间线相结合进行调度对此类问题进行求解。通过仿真实验将两种算法对问题的求解进行了比较,仿真实验表明B-PACO算法通过结合FFLPT(First Fit Longest Processing Time)启发式算法先将工件成批再生成最终方案,提高了算法搜索效率,并且在衡量算法搜索非支配解数量的Q指标和衡量非支配集与Pareto边界接近程度的HV指标上,均优于J-PACO算法。     

Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart

We consider the online scheduling of equal length jobs on unbounded parallel batch processing machines to minimize makespan with limited restart. In the problem \(m\) identical unbounded parallel batch processing machines are available to process the equal length jobs arriving over time. The processing batches are allowed limited restart. Here, “restart” means that a running task may be interrupted, losing all the work done on it, and the jobs in the interrupted task are then released and become independently unscheduled jobs, called restarted jobs. “Limited restart” means that only a running batch that contains no restarted jobs can be restarted. For this problem, we present a best possible online algorithm.     

Heuristic algorithms for the two-machine flowshop with limited machine availability

The paper studies a flowshop scheduling problem where machines are not available in given time intervals. The objective is to minimize the makespan. The problem is known to be NP-hard for two machines. We analyze constructive and local search based heuristic algorithms for the two-machine case. The algorithms are tested on easy and difficult test problems with up to 100 jobs and 10 intervals of non-availability. Computational results show that the algorithms perform well. For many problems an optimum solution is found.     

Just-in-time scheduling with controllable processing times on parallel machines

We study scheduling problems with controllable processing times on parallel machines. Our objectives are to maximize the weighted number of jobs that are completed exactly at their due date and to minimize the total resource allocation cost. We consider four different models for treating the two criteria. We prove that three of these problems are NP\mathcal{NP} -hard even on a single machine, but somewhat surprisingly, the problem of maximizing an integrated objective function can be solved in polynomial time even for the general case of a fixed number of unrelated parallel machines. For the three NP\mathcal{NP} -hard versions of the problem, with a fixed number of machines and a discrete resource type, we provide a pseudo-polynomial time optimization algorithm, which is converted to a fully polynomial time approximation scheme.     

Scheduling with machine cost and rejection

In this paper we consider the scheduling problem with machine cost and rejection penalties. For this problem, we are given a sequence of independent jobs, each being characterized by its processing time (size) and its penalty. No machine is initially provided, and when a job is revealed the algorithm has the option to purchase new machines. Right when a new job arrives, we have the following choices: (i) reject it, in which case we pay its penalty; (ii) non-preemptively process it on an existing machine, which contributes to the machine load; (iii) purchase a new machine, and assign it to this machine. The objective is to minimize the sum of the makespan, the cost for purchasing machines, and the total penalty of all rejected jobs. For the small job case, (where all jobs have sizes no greater than the cost for purchasing one machine, and which is the generalization of the Ski-Rental Problem) we present an optimal online algorithm with a competitive ratio of 2.     

Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties

In this paper, we consider the parallel-machine scheduling problem with release dates and submodular rejection penalties. In this problem, we are given m identical parallel machines and n jobs. Each job has a processing time and a release date. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the rejection penalty of the rejected jobs which is determined by a submodular function. Our main work is to design a 2-approximation algorithm based on the primal-dual framework.

     

A coordination mechanism for a scheduling game with parallel-batching machines

In this paper we consider the scheduling problem with parallel-batching machines from a game theoretic perspective. There are m parallel-batching machines each of which can handle up to b jobs simultaneously as a batch. The processing time of a batch is the time required for processing the longest job in the batch, and all the jobs in a batch start and complete at the same time. There are n jobs. Each job is owned by a rational and selfish agent and its individual cost is the completion time of its job. The social cost is the largest completion time over all jobs, the makespan. We design a coordination mechanism for the scheduling game problem. We discuss the existence of pure Nash Equilibria and offer upper and lower bounds on the price of anarchy of the coordination mechanism. We show that the mechanism has a price of anarchy no more than \(2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}\).     

Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem which has been extensively studied. Scheduling with testing is an online variant, where the processing time of a job is revealed by an extra test operation, otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take one unit of time each. We propose to first sort the jobs into non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves better competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case; when all test operations each takes one time unit, our algorithm achieves even better competitive ratios approaching 2.8081.

     

Related machine scheduling with machine speeds satisfying linear constraints

Journal of Combinatorial Optimization - We propose a related machine scheduling problem in which the processing times of jobs are given and known, but the speeds of machines are variables and must...     

Scheduling dedicated jobs with variative processing times

We consider the following optimization problem. There is a set of \(n\) dedicated jobs that are to be processed on \(m\) parallel machines. The job set is partitioned into subsets and jobs of each subset have a common due date. Processing times of jobs are interconnected and they are the subject of the decision making. The goal is to choose a processing time for each job in a feasible way and to construct a schedule that minimizes the maximum lateness. We show that the problem is NP-hard even if \(m=1\) and that it is NP-hard in the strong sense if \(m\) is a variable. We prove that there is no approximate polynomial algorithm with guaranteed approximation ratio less than 2. We propose an integer linear formulation for the problem and perform experiments. The experiments show that the solutions obtained with CPLEX within the limit of 5 min are on average about 5 % from the optimum value for instances with up to 150 jobs, 16 subsets and 11 machines. Most instances were solved to optimality and the average CPLEX running time was 32 s for these instances.     

Equal Processing Time Bicriteria Scheduling on Parallel Machines

We consider the problem of scheduling jobs on parallel, identical machines so as to minimize a primary and a secondary criteria. All the jobs are assumed to have identical processing times. Polynomial time algorithms, that generate optimal solutions, are presented for various combinations of primary and secondary criteria.     

Semi-online scheduling on 2 machines under a grade of service provision with bounded processing times

We study the problem of semi-online scheduling on 2 machines under a grade of service (GoS). GoS means that some jobs have to be processed by some machines to be guaranteed a high quality. The problem is online in the sense that jobs are presented one by one, and each job shall be assigned to a time slot on its arrival. Assume that the processing time p _i of every job J _i is bounded by an interval [a,α a], where a>0 and α>1 are two constant numbers. By knowing the bound of jobs’ processing times, we denote it by semi-online problem. We deal with two semi-online problems.     

Exact algorithms for scheduling programs with shared tasks

We study a scheduling problem where the jobs we have to perform are composed of one or more tasks. If two jobs sharing a non-empty subset of tasks are scheduled on the same machine, then these shared tasks have to be performed only once. This kind of problem is known in the literature under the names of VM-PACKING or PAGINATION. Our objective is to schedule a set of these objects on two parallel identical machines, with the aim of minimizing the makespan. This problem is NP-complete as an extension of the PARTITION problem. In this paper we present three exact algorithms with worst-case time-complexity guarantees, by exploring different branching techniques. Our first algorithm focuses on the relation between jobs sharing one or more symbols in common, whereas the two other algorithms branches on the shared symbols.

     

Randomized selection algorithm for online stochastic unrelated machines scheduling

Journal of Combinatorial Optimization - We consider an online stochastic unrelated machines scheduling problem. Specifically, a set of jobs arriving online over time must be randomly scheduled on...     

A Multi-Exchange Neighborhood for Minimum Makespan Parallel Machine Scheduling Problems

We propose new local search algorithms for minimum makespan parallel machine scheduling problems, which perform multiple exchanges of jobs among machines. Inspired by the work of Thompson and Orlin (1989) on cyclic transfer neighborhood structures, we model multiple exchanges of jobs as special disjoint cycles and paths in a suitably defined improvement graph, by extending definitions and properties introduced in the context of vehicle routing problems (Thompson and Psaraftis, 1993) and of the capacitated minimum spanning tree problem (Ahuja et al., 2001). Several algorithms for searching the neighborhood are suggested.We report the results of a wide computational experimentation, on different families of benchmark instances, performed for the case of identical machines. This problem has been selected as a case study to perform a comparison among the alternative algorithms, and to discover families of instances for which the proposed neighborhood may be promising in practice. Based on the results of the experiments, we can suggest which among the many possible variants of the proposed approaches may be more promising for developing local search algorithms based on multi-exchange moves for related problems. Also, on some families of instances, which are very hard to solve exactly, the most promising multi-exchange algorithms were observed to dominate, in solution quality and in computational time, competitive benchmark heuristics.     

Parallel-machine scheduling of deteriorating jobs with potential machine disruptions

We consider parallel-machine scheduling of deteriorating jobs in a disruptive environment in which some of the machines will become unavailable due to potential disruptions. This means that a disruption to some of the machines may occur at a particular time, which will last for a period of time with a certain probability. If a job is disrupted during processing by a disrupted machine and it does not need (needs) to re-start after the machine becomes available again, it is called the resumable (non-resumable) case. By deteriorating jobs, we mean that the actual processing time of a job grows when it is scheduled for processing later because the machine efficiency deteriorates over time due to machine usage and aging. However, a repaired machine will return to its original state of efficiency. We consider two cases, namely performing maintenance immediately on the disrupted machine when a disruption occurs and not performing machine maintenance. In each case, the objective is to determine the optimal schedule to minimize the expected total completion time of the jobs in both non-resumable and resumable cases. We determine the computational complexity status of various cases of the problem, and provide pseudo-polynomial-time solution algorithms and fully polynomial-time approximation schemes for them, if viable.     

Scheduling of unrelated parallel machines when machine availability is specified

Scheduling problems typically assume uninterrupted availability of machines such that jobs can be processed at any time during this uninterrupted period. However, this assumption is seldom valid in reality. For a variety of reasons, e.g. machine adjustments, shift changes, planned maintenance, etc. machines are available only at specified times. The duration for which the machine is not available is known as the vacation. This paper considers the problem of scheduling jobs on unrelated parallel machines when machine vacations are specified. Two cases are considered, first, when the machine vacations are known apriori, and the second, when these constraints are not known apriori. Algorithms have been developed for both models, and computational results are also reported.     

Efficient Job Scheduling Algorithms with Multi-Type Contentions

In this paper, we consider an interesting generalization of the classic job scheduling problem in which each job needs to compete not only for machines but also for other types of resources. The contentions among jobs for machines and for resources could interfere with each other, which complicates the problem dramatically. We present a family of approximation algorithms for solving several variants of the problem by using a generic algorithmic framework. Our algorithms achieve a constant approximation ratio (i.e., 3) when there is only one type of resources or certain dependency relation exists among multiple types of resources. When the r resources are unrelated, the approximation ratio of our algorithm becomes k+2, where k≤ r is a constant depending on the problem instance. As an application, we also show that our techniques can be easily applied to optical burst switching (OBS) networks to design more efficient wavelength scheduling algorithms.This research was supported in part by an IBM faculty partnership award, and an IRCAF award from SUNY Buffalo.     

基于改进遗传算法的置换装配线调度问题研究

企业的置换装配线调度问题（Permutation Assembly-line Scheduling Problem,PASP）是一类典型的NP-hard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明：本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。     

Ordinal On-Line Scheduling for Maximizing the Minimum Machine Completion Time

This paper considers the on-line problem of scheduling nonpreemptively n independent jobs on m > 1 identical and parallel machines with the objective to maximize the minimum machine completion time. It is assumed that the values of the processing times are unknown but the order of the jobs by their processing times is known in advance. We are asked to decide the assignment of all the jobs to some machines at time zero by utilizing only ordinal data rather than the actual magnitudes of jobs. Algorithms to slove the problem are called ordinal algorithms. In this paper, we give lower bounds and ordinal algorithms. We first propose an algorithm MIN which is at most -competitive for any m machine case, while the lower bound is _i=1 ^m 1/i. Both are on the order of (ln m). Furthermore, for m = 3, we present an optimal algorithm.