-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathsingle-machine-min-tardy.html
88 lines (84 loc) · 4.49 KB
/
single-machine-min-tardy.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="Problems">
<meta name="author" content="Chao Xu">
<meta property="og:title" content="Single Machine Minimum Tardy Jobs" />
<meta property="og:type" content="article" />
<meta property="og:site_name" content="Problems" />
<meta property="article:tag" content="" />
<title>Single Machine Minimum Tardy Jobs</title>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-BdGj8xC2eZkQaxoQ8nSLefg4AV4/AwB3Fj+8SUSo7pnKP6Eoy18liIKTPn9oBYNG" crossorigin="anonymous">
<!-- The loading of KaTeX is deferred to speed up page rendering -->
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.js" integrity="sha384-JiKN5O8x9Hhs/UE5cT5AAJqieYlOZbGT3CHws/y97o3ty4R7/O5poG9F3JoiOYw1" crossorigin="anonymous"></script>
<!-- To automatically render math in text elements, include the auto-render extension: -->
<!-- <script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/contrib/auto-render.min.js" integrity="sha384-kWPLUVMOks5AQFrykwIup5lo0m3iMkkHrD0uJ4H5cjeGihAutqP0yW0J6dpFiVkI" crossorigin="anonymous"
onload="renderMathInElement(document.body);"></script>
-->
<script defer>
function render_katex_math(){
const macros={
"\\C":"\\mathbb{C}",
"\\F":"\\mathbb{F}",
"\\e": "\\varepsilon",
"\\eps": "\\varepsilon",
"\\mex": "\\mathop{\\operatorname{mex}}",
"\\lcm": "\\mathop{\\operatorname{lcm}}",
"\\dist": "\\mathop{\\operatorname{dist}}",
"\\bigtriangleright": "{\\mathop{\\Large \\triangleright}}",
"\\bigtriangleleft": "{\\mathop{\\Large \\triangleleft}}",
'\\set':'\\left\\{ #1 \\right\\}',
'\\floor':'\\left\\lfloor #1 \\right\\rfloor',
'\\ceil':'\\left\\lceil #1 \\right\\rceil',
'\\abs':'\\left\\| #1 \\right\\|'
};
const mathElements = document.getElementsByClassName("math");
for (var i = 0; i < mathElements.length; i++) {
var texText = mathElements[i].firstChild;
if (mathElements[i].tagName == "SPAN") {
katex.render(texText.data, mathElements[i],
{ displayMode: mathElements[i].classList.contains("display"), throwOnError: false, macros:macros}
);
}
};
};
window.onload = render_katex_math;
</script>
<link rel="shortcut icon" type="image/x-icon" href="/favicon.ico"/>
<link rel="stylesheet" href="/css/default.css" crossorigin="anonymous">
<link rel="stylesheet" href="/css/blog.css" crossorigin="anonymous">
</head>
<body>
<header class="hide-on-print">
<div id="site-title">
<a href="/">Problems</a>
</div>
</header>
<!--<nav class="hide-on-print">
<ul>
<li><a href="/">Home</a></li>
</ul>
</nav>-->
<main>
<article>
<h1 id="article-title">Single Machine Minimum Tardy Jobs</h1>
<br />
<div>
<h1 id="problem">Problem</h1>
<p>The <span class="math inline">j</span>th job takes <span class="math inline">p_j</span> time. There exist due date <span class="math inline">d_j</span> for the <span class="math inline">j</span>th job. Let <span class="math inline">C_j</span> is the completion time of the <span class="math inline">j</span>th job. <span class="math inline">U_j=0</span> if <span class="math inline">C_j\leq d_j</span>, otherwise <span class="math inline">U_j=1</span>. Find a scheule that minimizes <span class="math inline">\sum_{j=1}^n U_j</span>.</p>
<h1 id="algorithms">Algorithms</h1>
<p><span class="math inline">O(n\log n)</span> algorithm exists.</p>
</div>
<div class="hide-on-print">
<div class="info">Tags: .</div>
</div>
</article>
</main>
<!--
<footer class="hide-on-print">© 2010 - <time><script>document.write(new Date().getFullYear())</script></time> <a href="https://chaoxuprime.com" rel="author">Chao Xu</a>. Licensed under a <a rel="license" href="http://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution 4.0 International License</a>.
</footer>
-->
</body>
</html>