Interleaving two-phased jobs on a single machine

Hanif D. Sherali, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


In this paper, we consider a single machine that processes a set of jobs having two (ordered) phases. After processing the first phase of a job, this job must be removed from the machine for some exact amount of time, after which the machine must immediately begin processing its second phase. During this "dead time" between job phases, the machine may be used to process other similar jobs. We first prove that the problem of interleaving these jobs in order to minimize the makespan (or to process as many jobs as possible by a given deadline) is strongly NP-hard. Next, we compare the effectiveness of a mixed-integer programming formulation based on a continuous time domain to that of a discrete-time integer programming model for solving problems having different data characteristics. These comparisons are performed on a set of realistic synthetic problems based on different scenarios arising in radar pulsing applications.

Original languageEnglish (US)
Pages (from-to)348-361
Number of pages14
JournalDiscrete Optimization
Issue number4
StatePublished - Dec 2005
Externally publishedYes


  • Integer programming
  • Pulse interleaving
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Interleaving two-phased jobs on a single machine'. Together they form a unique fingerprint.

Cite this