Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)


We consider a single-machine scheduling problem in which every job has a given target start time and a due-date. A job is early if processing commences before its start time and is tardy if it is completed after its due-date. The objective is to minimize the weighted number of early and tardy jobs, with the restriction that the start times and due-dates are "agreeable", i.e., the start times must increase in the same sequence as the due-dates. We show that the problem is NP-complete in the strong sense. The complexity issues and algorithms for some special cases of this problem are discussed, and heuristic algorithms are developed for the general problem. Computational experiments are conducted to show the effectiveness of the heuristics.
Original languageEnglish
Pages (from-to)205-219
Number of pages15
JournalComputers and Operations Research
Issue number2
Publication statusPublished - 1 Jan 1995

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this