In this paper, we consider the multitasking scheduling with alternate odd-period and even-period. For the minimization of makespan on one single machine, we present a 2-approximation algorithm for the general case and...
详细信息
In this paper, we consider the multitasking scheduling with alternate odd-period and even-period. For the minimization of makespan on one single machine, we present a 2-approximation algorithm for the general case and a 4/3-approximation algorithm for a special case when jobs have identical release dates. And we prove that the problem is strongly NP-hard when jobs have different release dates. For the minimization of makespan on identical parallel machines, we present a (5/2 - 1/m)-approximation algorithm for the general case and a pseudo-polynomialtimealgorithm when the number of machines is constant. Furthermore, we prove that the single-machine scheduling of minimizing the lateness is strongly NP-hard.
This paper considers a two-stage medical supply chain scheduling problem from the perspective of the medicine manufacturer in which jobs have an assignable common due window and shelf life. Each job will incur an earl...
详细信息
This paper considers a two-stage medical supply chain scheduling problem from the perspective of the medicine manufacturer in which jobs have an assignable common due window and shelf life. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. The job's holding time, which is the time interval that passes from the completion time of the job to the delivery date of the job in the batch, must be no more than its shelf life. The objective is to minimize the total cost comprising earliness, weighted number of tardy jobs, holding time, due window starting time, window size, and batch delivery. We first show that the problem is NP-hard and then provide a pseudo-polynomial-time algorithm. We also prove that a special case of the problem can be optimally solved in polynomialtime.
In this paper, we consider the two-agent scheduling problem with rejection on a single machine. In the problem we have two agents A and B with job families J(A) and J(B), respectively. A job in J(A) or J(B) is either ...
详细信息
In this paper, we consider the two-agent scheduling problem with rejection on a single machine. In the problem we have two agents A and B with job families J(A) and J(B), respectively. A job in J(A) or J(B) is either accepted and processed on the machine, or rejected with a certain rejection penalty having to be paid. The objective is to minimize the sum of the given objective function f(A) of the accepted jobs and total rejection penalty of the rejected jobs of the first agent A, given that the second agent B only accepts schedules such that the sum of the given objective function f(B) of the accepted jobs and total rejection penalty of the rejected jobs of the agent B does not exceed a fixed value Q (Q is a positive integer), where f(A) and f(B) are non-decreasing functions on the completion times of their respective jobs. We show that, for all pairs (f(A), f(B)) is an element of {(C-max(A), C-max(B)), (L-max(A), L-max(B)), (Sigma C-j(A), L-max(B)), (Sigma C-j(A), L-max(B)), (Sigma C-j(A), Sigma w(j)(B)U(j)(B))}, the problems are NP-hard. When (f(A),f(B)) = (C-max(A), L-max(B)), we provide a pseudo-polynomial-time algorithm. Moreover, when (f(A),f(B)) = (C-max(A), L-max(B)) and all B-jobs are accepted, we give a 2-approximation algorithm and an fully polynomial-time approximation scheme. Finally, for (f(A),f(B)) is an element of {(Sigma C-j(A), L-max(B)), (Sigma C-j(A), Sigma w(j)(B)U(j)(B))}K, we present pseudo-polynomial-time algorithms, respectively. (C) 2014 Elsevier Inc. All rights reserved.
暂无评论