Simultaneous Job Scheduling and Resource Allocation on Parallel Machines

Zhi-Long Chen ()

Annals of Operations Research, 2004, vol. 129, issue 1, 135-153

Abstract: Most deterministic production scheduling models assume that the processing time of a job on a machine is fixed externally and known in advance of scheduling. However, in most realistic situations, apart from the machines, it requires additional resources to process jobs, and the processing time of a job is determined internally by the amount of the resources allocated. In these situations, both the cost associated with the job schedule and the cost of the resources allocated should be taken into account. Therefore, job scheduling and resource allocation should be carefully coordinated and optimized jointly in order to achieve an overall cost-effective schedule. In this paper, we study a parallel-machine scheduling model involving both job processing and resource allocation. The processing time of a job is non-increasing with the cost of the allocated resources. The objective is to minimize the total cost including the cost measured by a scheduling criterion and the cost of all allocated resources. We consider two particular problems of this model, one with the scheduling criterion being the total weighted completion time, and the other with that being the weighted number of tardy jobs. We develop a column generation based branch and bound method for finding optimal solutions for these NP-hard problems. The method first formulates the problems as set partitioning type formulations, and then solves the resulting formulations exactly by branch and bound. In the branch and bound, linear relaxations of the set partitioning type formulations are decomposed into master problems and single-machine subproblems and solved by a column generation approach. The algorithms developed based on this method are capable of solving the two problems with a medium size to optimality within a reasonable computational time. Copyright Kluwer Academic Publishers 2004

Keywords: production scheduling; resource allocation; column generation; branch and bound (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://hdl.handle.net/10.1023/B:ANOR.0000030685.31167.11 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:129:y:2004:i:1:p:135-153:10.1023/b:anor.0000030685.31167.11

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/B:ANOR.0000030685.31167.11

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().