Spread time considerations in operational fixed job scheduling.
Saved in:
| Title: | Spread time considerations in operational fixed job scheduling. |
|---|---|
| Authors: | Eliiyi, D. T.1 (AUTHOR), Azizoglu, M.2 (AUTHOR) meral@ie.metu.edu.tr |
| Source: | International Journal of Production Research. 10/15/2006, Vol. 44 Issue 20, p4343-4365. 23p. |
| Subjects: | Production scheduling, Production control, Size reduction of materials, Spread (Finance), Deadlines, Working hours, Algorithms, Employees, Extensions |
| Abstract: | In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times. [ABSTRACT FROM AUTHOR] |
| Copyright of International Journal of Production Research is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 00207543 |
| DOI: | 10.1080/00207540500478645 |
