Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs

DOI10.1016/0167-6377(94)90069-8zbMath0823.90060OpenAlexW2088060524MaRDI QIDQ1892102

Awi Federgruen, Gur Mosheiov

Publication date: 6 July 1995

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(94)90069-8

zbMATH Keywords

single-machine schedulingcommon due-dategreedy heuristicsgeneral earliness and tardiness costsworst-case optimality gaps

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Machine scheduling with earliness, tardiness and non-execution penalties, Single machine scheduling to minimize the number of early and tardy jobs, Minimizing the Earliness and Tardiness Cost of a Sequence of Tasks on a Single Machine, Exact and heuristic algorithms for minimizing tardy/lost penalties on a single-machine scheduling problem, A survey of the state-of-the-art of common due date assignment and scheduling research

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completion time variance minimization on a single machine is difficult
• Scheduling with monotonous earliness and tardiness penalties
• Minimizing the average deviation of job completion times about a common due date
• Sequencing with Earliness and Tardiness Penalties: A Review
• Minimizing mean absolute deviation of completion times about a common due date
• Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date
• Earliness–Tardiness Scheduling Problems, II: Deviation of Completion Times About a Restrictive Common Due Date
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function