Abstract
This paper presents the first efficient method to solve an earliness-tardiness single machine n job scheduling model with idle times permitted. In this model the earliness and tardiness penalties are proportional to the processing times of the jobs. A two stage decomposition process builds the optimal job arrangement as a sequence of single and multijob blocks. The arrangement of the jobs within each multijob block is unspecified since it depends on the start time of this block. This process is followed by a procedure that drastically reduces the number of candidate optimal n job sequences. Finally an available optimal timing algorithm is recommended and implemented to select the best schedule among those sequences. The solution procedure tested on a PC on 400 examples for n=40 and 50 proves to be very fast.
Similar content being viewed by others
References
E.M.Arkin and R.O.Roundy, “Weighted Tardiness Scheduling on Parallel Machines with Proportional Weights,” Operations Research, 39, 64–81 (1991).
M.R.Garey, R.E.Tarjan, and G.T.Wilfong, “One Processor Scheduling with Symmetric Earliness and Tardiness Penalties,” Mathematics of Operations Research 13, 330–348 (1988).
J.S.Davis and J.J.Kanet, “Single-Machine Scheduling with Early and Tardy Completion Costs,” Naval Research Loqistics, 40 (1993), 85–101.
R.Rachamadugu, “Scheduling Jobs Against a Common Due Date,” Working Paper #631, School of Business Administration, The University of Michigan, Ann Arbor, Michigan 48109 (1990).
W.Szwarc and J.J.Liu, “Weighted Tardiness Single Machine Scheduling with Proportional Weights,” Management Science, 39, 626–632 (1993).
W. Szwarc and S.K. Mukhopadhyay, “Optimal Timing Schedules in Earliness-Tardiness Single Machine Sequencing,” to appear in Naval Research Loqistics.
C.A.Yano and Y-DKim, “Algorithms for a Class of Single-Machine Weighted Tardiness and Earliness Problems,” European Journal of Operational Research 52, 167–178 (1991).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Szwarc, W., Mukhopadhyay, S.K. Earliness and tardiness single machine scheduling with proportional weights. J Glob Optim 9, 227–238 (1996). https://doi.org/10.1007/BF00121673
Issue Date:
DOI: https://doi.org/10.1007/BF00121673