| Summary: | In this paper, we consider a two-machine job-shop scheduling problem of minimizing total completion time subject to <i>n</i> jobs with two operations and equal processing times on each machine. This problem occurs e.g., as a single-track railway scheduling problem with three stations and constant travel times between any two adjacent stations. We present a polynomial dynamic programming algorithm of the complexity <inline-formula> <math display="inline"> <semantics> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>5</mn> </msup> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula> and a heuristic procedure of the complexity <inline-formula> <math display="inline"> <semantics> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula>. This settles the complexity status of the problem under consideration which was open before and extends earlier work for the two-station single-track railway scheduling problem. We also present computational results of the comparison of both algorithms. For the 30,000 instances with up to 30 jobs considered, the average relative error of the heuristic is less than <inline-formula> <math display="inline"> <semantics> <mrow> <mn>1</mn> <mo>%</mo> </mrow> </semantics> </math> </inline-formula>. In our tests, the practical running time of the dynamic programming algorithm was even bounded by <inline-formula> <math display="inline"> <semantics> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>4</mn> </msup> <mo stretchy="false">)</mo> </mrow> </semantics> </math> </inline-formula>.
|
|---|