In this paper, we consider the bounded parallel-batch scheduling problem on unrelated parallel machines. Problems R-m vertical bar B vertical bar F are NP-hard for any objective function F. For this reason, we discuss...
详细信息
ISBN:
(纸本)9783642143540
In this paper, we consider the bounded parallel-batch scheduling problem on unrelated parallel machines. Problems R-m vertical bar B vertical bar F are NP-hard for any objective function F. For this reason, we discuss the special case with p(ij) = p(i) for i = 1, 2,..., m, j = 1, 2, ... n. We give optimal algorithms for the general scheduling to minimize total weighted completion time, makespan and the number of tardy jobs. And we design pseudo-polynomial time algorithms for the case with rejection penalty to minimize the makespan and the total weighted completion time plus the total penalty of the rejected jobs, respectively.
This paper considers online scheduling on two unit flowshop machines, which there exists unbounded parallel-batch scheduling with incompatible job families and lookahead intervals. The unit flowshop machine means that...
详细信息
This paper considers online scheduling on two unit flowshop machines, which there exists unbounded parallel-batch scheduling with incompatible job families and lookahead intervals. The unit flowshop machine means that the processing time of any job on each machine is unit processing time. The objective is to minimize the maximum completion time. The lookahead model means that an online algorithm can foresee the information of all jobs arriving in time interval (t, t + beta] at time t. There exist incompatible job families, that is, jobs belonging to different families cannot be processed in the same batch. In this paper, we address the lower bound of the proposed problem, and provide a best possible online algorithm of competitive ratio 1+ alpha f for 0 <= beta < 1, where alpha f is the positive root of the equation (f + 1)alpha(2) + (beta + 2)alpha + beta - f = 0 and f is the number of incompatible job families which is known in advance.
We consider the online scheduling of incompatible unit-length job families on an unbounded parallel-batch machine with lookahead. In this paper online means that jobs arrive over time. The objective is to mininize the...
详细信息
We consider the online scheduling of incompatible unit-length job families on an unbounded parallel-batch machine with lookahead. In this paper online means that jobs arrive over time. The objective is to mininize the makespan. In the lookahead model, at a time instant t, an online algorithm can foresee the information of all jobs arriving in the time segment (t, t + beta]. Incompatible job families mean that jobs which belong to different families cannot be assigned to the same batch. For this problem, we provide a best possible online algorithm of competitive ratio 1 + alpha(f) for 0 <= beta < 1, where alpha(f) is the positive root of the equation f . alpha(2)(f) + (1 + beta)alpha(f) + beta - f = 0 and f is the number of job families which is known in advance. (C) 2014 Elsevier B.V. All rights reserved.
作者：
Gao, YuanZhengzhou Univ
Sch Math & Stat Zhengzhou 450001 Henan Peoples R China Zhengzhou Univ
Sch Informat Engn Zhengzhou 450001 Henan Peoples R China
We study the Pareto optimization scheduling on an unbounded parallel-batch machine with jobs having agreeable release dates and processing times for minimizing makespan and maximum cost simultaneously. The jobs consid...
详细信息
We study the Pareto optimization scheduling on an unbounded parallel-batch machine with jobs having agreeable release dates and processing times for minimizing makespan and maximum cost simultaneously. The jobs considered in this paper are of two types: batch jobs and drop-line jobs. For batch jobs, the completion time of a job is given by the completion time of the batch containing this job. For drop-line jobs, the completion time of a job is given by the starting time of the batch containing this job plus the processing time of this job. For both of batch jobs and drop-line jobs, we present polynomial-time algorithms for finding all Pareto optimal points.
With the popularization of energy conservation and emission reduction, amounts of industrial production has taken energy conservation as a goal to achieve. The paper considers an online parallel-batch scheduling probl...
详细信息
With the popularization of energy conservation and emission reduction, amounts of industrial production has taken energy conservation as a goal to achieve. The paper considers an online parallel-batch scheduling problem with deteriorating and incompatible families on identical machines to minimize the makespan, which minimizes the maximum energy consumption of machines. Specifically, the processing time of job J(j) is defined by an increasing function of its starting time t, i.e., p(j) = alpha(j)(A + Bt), where alpha j > 0 is the deterioration rate of job J(j). For the problem, we propose an online algorithm with a competitive ratio of 2 + B alpha max, where alpha(max) is the largest deterioration rate in an instance. Furthermore, the paper presents a concise computational study of the numerical experiment to show that our algorithm performs very well in practice of this model.
暂无评论