Single machine sequencing with linear models of release dates

✍ Scribed by Adam Janiak

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 116 KB
• Volume: 45
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/(sici)1520-6750(199802)45:1<99::aid-nav6>3.0.co;2-g

✦ Synopsis

The paper deals with a problem of scheduling a set of jobs on a single machine. Before a job is released for processing, it must undergo some preprocessing treatment that consumes resources. It is assumed that the release date of a job is a linear decreasing continuous function of the amount of a locally and globally constrained, continuously divisible resource (e.g., energy, catalyzer, financial outlay, gas). The problem is to find a sequence of jobs and a resource allocation that will minimize the maximum job completion time. Such a problem appears, for example, in the ingot preheating and hot-rolling process in steel mills. It is shown that the problem is strongly NP-hard. Some polynomially solvable cases of the problem and approximate algorithms with both experimental and worst-case analysis are presented.