Paper Info
Title
Interleaving two-phased jobs on a single machine
Abstract
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.
Year
DOI
Venue
2005
10.1016/j.disopt.2005.08.002
Discrete Optimization
Keywords
Field
DocType
discrete-time integer programming model,exact amount,single machine,similar job,continuous time domain,different data characteristic,integer programming,mixed-integer programming formulation,job phase,scheduling,pulse interleaving,different scenario,two-phased job,dead time,discrete time
Time domain,Radar,Integer programming model,Mathematical optimization,Dead time,Job shop scheduling,Computer science,Scheduling (computing),Integer programming,Interleaving
Journal
Volume
Issue
ISSN
2
4
Discrete Optimization
Citations 
PageRank 
References 
8
1.11
2
Authors
2
Name
Order
Citations
PageRank
Hanif D. Sherali13403318.40
J. Cole Smith261043.34