This study investigates the prize-collecting single machine scheduling with bounds and penalties (PC-SMS-BP). In this problem, a set of n jobs and a single machine are considered, where each job Jj\documentclass[12pt]...
详细信息
This study investigates the prize-collecting single machine scheduling with bounds and penalties (PC-SMS-BP). In this problem, a set of n jobs and a single machine are considered, where each job Jj\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$J_j$$\end{document} has a processing time pj\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_{j}$$\end{document}, a profit pi j\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pi _{j}$$\end{document} and a rejection penalty wj\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w_{j}$$\end{document}. The upper bound on the processing number is U. The objective of this study is to find a feasible schedule that minimizes the makespan of the accepted jobs and the total rejection penalty of the rejected jobs under the condition that the number of the accepted jobs does not exceed a given threshold U while the total profit of the accepted jobs does not fall below a specified profit bound Pi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varPi $$\end{document}. We first demonstrate that this problem is NP-hard. Then, a pseudo-polynomialtime
We consider the time-dependent scheduling with proportional and delivery times on a single machine. Three models of the processing times are addressed here, they are proportional deterioration, proportional-linear sho...
详细信息
We consider the time-dependent scheduling with proportional and delivery times on a single machine. Three models of the processing times are addressed here, they are proportional deterioration, proportional-linear shortening and proportional-linear increasing. The objective is to minimize the time by which all jobs are delivered. For the first model, we prove that the problem is polynomial solvable when jobs have identical release dates. When jobs arrive dynamically, we first give the proof of the NP-hardness and present a two-approximation algorithm. Then we propose a fully polynomial time approximation scheme for the case where the number of distinct release dates is a constant by applying the "rounding-the-input-data " technique. For the second and third models, when jobs have identical release dates, we prove that they are polynomial solvable, when jobs have different release dates, we present two-approximation algorithms for each of them.
We study a scheduling problem with a given number of identical parallel machines, a common job due date and the total early work criterion, i.e., Pm vertical bar d(j) = d vertical bar max{X}, which is known to be NP-h...
详细信息
We study a scheduling problem with a given number of identical parallel machines, a common job due date and the total early work criterion, i.e., Pm vertical bar d(j) = d vertical bar max{X}, which is known to be NP-hard. A new dynamic programming algorithm is proposed, which is more efficient than the existing exact approach for this problem. Based on the proposed dynamic programming, we further design two new fully polynomial time approximation schemes. The effectiveness and efficiency of the new exact and approximation approaches are validated in the computational experiments.
In this paper, we discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The objective is to minimize the weighted makespan of jobs, i.e., the maximum weigh...
详细信息
In this paper, we discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The objective is to minimize the weighted makespan of jobs, i.e., the maximum weighted completion time of jobs. This scheduling problem is a generalization of minimizing the makespan on parallel machine scheduling problem. We present a (2-1m\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2-\fracapproximation{m}$$\end{document})-approximation algorithm and a randomized efficient polynomialtimeapproximationscheme (EPTAS) for the problem. We also design a randomized fully polynomial time approximation scheme (FPTAS) for the special case when the number of machines is fixed.
Given a graph G = ( V , E ) G = ( V , E ) G=(V,E) , a set of m m m source-sink pairs P = { ( s 1 , t 1 ) , ( s 2 , t 2 ) , … , 𝒫 = { ( s 1 , t 1 ) , ( s 2 , t 2 ) , … , 𝒫={(s1,t1),(s2,t2),…, ( s m ,...
详细信息
Given a graph G = ( V , E ) G = ( V , E ) , a set of m m source-sink pairs P = { ( s 1 , t 1 ) , ( s 2 , t 2 ) , … , 𝒫 = { ( s 1 , t 1 ) , ( s 2 , t 2 ) , … , ( s m , t m ) } ( s m , t m ) } and a profit bound B B , every edge e ∈ E e ∈ E has a cost c e c e
暂无评论