Premium
Single machine sequencing with linear models of release dates
Author(s) -
Janiak Adam
Publication year - 1998
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199802)45:1<99::aid-nav6>3.0.co;2-g
Subject(s) - preprocessor , sequence (biology) , computer science , mathematical optimization , resource (disambiguation) , scheduling (production processes) , job shop scheduling , operations research , ingot , mathematics , materials science , artificial intelligence , computer network , genetics , alloy , composite material , biology , operating system , schedule
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. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 99–113, 1998