TY - JOUR
T1 - Parallel machine scheduling with earliness-tardiness penalties and additional resource constraints
AU - Ventura, José A.
AU - Kim, Daecheol
N1 - Funding Information:
This research was partially supported by the National Science Foundation under Grant DDM 90- 57066. The authors would like to thank two anonymous referees for their comments and suggestions. José A. Ventura is a professor of Industrial Engineering at Pennsylvania State University. He received his Ph.D. in industrial and systems engineering from the University of Florida. His research and teaching interests include network design and optimization, production scheduling, facility layout and material handling, and machine vision. Daecheol Kim received his Ph.D. in industrial and manufacturing engineering from The Pennsylvania State University. He is currently a manager consultant at AspenTech, Seoul, Korea. His research interests include production scheduling, supply chain management, and design and analysis of manufacturing systems.
PY - 2003/11
Y1 - 2003/11
N2 - This research considers the problem of scheduling jobs on parallel machines with noncommon due dates and additional resource constraints. The objective is to minimize the total absolute deviation of job completion times about the corresponding due dates. All job processing times are assumed to be the same. This problem is motivated by restrictions that occur in the handling and processing of jobs in certain phases of semiconductor manufacturing and other production systems. We examine two special cases. For the first of these, the number of additional resource types and the resource requirements per job are arbitrary. The problem is formulated as a zero-one integer linear program and the Lagrangian relaxation approach is used to obtain tight lower bounds. In the second case, there exist one single type of additional resource and the resource requirements per job are zero or one. This problem is shown to be equivalent to the asymmetric assignment problem. Scope and purpose This paper considers the problem of scheduling jobs on parallel machines where jobs have different due dates and may require, besides machines, certain additional limited resources for their handling and processing. The objective is to minimize the total absolute deviation of job completion times about the corresponding due dates. This objective function is consistent with the just-in-time production philosophy which espouses the notion that earliness as well as tardiness should be penalized. Two problems are addressed. In the first of these, the number of different types of additional resources and resource requirements per job are arbitrary. The problem is formulated as a zero-one integer linear program and the Lagrangian relaxation approach is used. In the second problem, there exists one single type of additional resource and the resource requirements per job are zero or one. This problem can be reformulated as an assignment problem.
AB - This research considers the problem of scheduling jobs on parallel machines with noncommon due dates and additional resource constraints. The objective is to minimize the total absolute deviation of job completion times about the corresponding due dates. All job processing times are assumed to be the same. This problem is motivated by restrictions that occur in the handling and processing of jobs in certain phases of semiconductor manufacturing and other production systems. We examine two special cases. For the first of these, the number of additional resource types and the resource requirements per job are arbitrary. The problem is formulated as a zero-one integer linear program and the Lagrangian relaxation approach is used to obtain tight lower bounds. In the second case, there exist one single type of additional resource and the resource requirements per job are zero or one. This problem is shown to be equivalent to the asymmetric assignment problem. Scope and purpose This paper considers the problem of scheduling jobs on parallel machines where jobs have different due dates and may require, besides machines, certain additional limited resources for their handling and processing. The objective is to minimize the total absolute deviation of job completion times about the corresponding due dates. This objective function is consistent with the just-in-time production philosophy which espouses the notion that earliness as well as tardiness should be penalized. Two problems are addressed. In the first of these, the number of different types of additional resources and resource requirements per job are arbitrary. The problem is formulated as a zero-one integer linear program and the Lagrangian relaxation approach is used. In the second problem, there exists one single type of additional resource and the resource requirements per job are zero or one. This problem can be reformulated as an assignment problem.
UR - http://www.scopus.com/inward/record.url?scp=0042812478&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0042812478&partnerID=8YFLogxK
U2 - 10.1016/S0305-0548(02)00118-1
DO - 10.1016/S0305-0548(02)00118-1
M3 - Article
AN - SCOPUS:0042812478
SN - 0305-0548
VL - 30
SP - 1945
EP - 1958
JO - Computers and Operations Research
JF - Computers and Operations Research
IS - 13
ER -