zbMATH — the first resource for mathematics

Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. (English) Zbl 0717.90034
The authors consider single machine sequencing problems in which processing time of a job is assumed to be split in a fixed and a variable part. For each job j, the variable part is sequence dependent in the sense that it is given by \(\max \{0,v_ j(S_ j-d_ j)\}\) where \(v_ j\) and \(d_ j\) are given and \(S_ j\) is the starting time of job j in the sequence under consideration. The objective is to minimize makespan.
A dynamic programming, a branch-and-bound and five heuristic algorithms are proposed. Computational experience with solving randomly generated problems with up to 15 jobs is reported. The paper suffers from such annoying phenomena as unstated assumptions and ambiguous formulations.
Reviewer: M.Vlach

90B35 Deterministic scheduling theory in operations research
90C39 Dynamic programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI
[1] Gupta, J.N.D.; Gupta, S.K., Single facility scheduling with nonlinear processing times, Computers and industrial engineering, 14, 4, 387-393, (1988)
[2] Gupta, S.K.; Kyparisis, J., Single machine scheduling research, Omega, 15, 3, 207-227, (1987)
[3] Gupta, S.K.; Kunnathur, A.S.; Dandapani, K., Optimal repayment policies for multiple loans, Omega, 15, 4, 323-330, (1987)
[4] Sen, T.; Gupta, S.K., A state-of-art survey of static scheduling research involving due dates, Omega, 12, 1, 63-76, (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.