A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops.
Saved in:
| Title: | A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. |
|---|---|
| Authors: | Singer, Marcos1, Pinedo, Michael2 |
| Source: | IIE Transactions. Feb98, Vol. 30 Issue 2, p109-118. 10p. |
| Subjects: | Tardiness, Job shops, Production scheduling, Industrial engineering, Industrial management, Comparative studies |
| Abstract: | We present and compare a number of branch and bound algorithms for minimizing the total weighted tardiness in job shops. There arc basically two types of branching schemes. The first one inserts operations in a partial schedule, while the second one fixes arcs in the disjunctive graph formulation of the problem. The bounding schemes are based on the analysis of precedence constraints, and on the solution of nonpreemptive single machine subproblems that are subject to so-called delayed precedence constraints. We obtain optimal solutions for all the instances with ten jobs and ten machines that we consider, including three tardiness versions of a well-known 10 x 10 instance introduced by Muth and Thompson [1] in 1963. [ABSTRACT FROM AUTHOR] |
| Copyright of IIE Transactions 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 11897366 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Singer%2C+Marcos%22">Singer, Marcos</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Pinedo%2C+Michael%22">Pinedo, Michael</searchLink><relatesTo>2</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22IIE+Transactions%22">IIE Transactions</searchLink>. Feb98, Vol. 30 Issue 2, p109-118. 10p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Tardiness%22">Tardiness</searchLink><br /><searchLink fieldCode="DE" term="%22Job+shops%22">Job shops</searchLink><br /><searchLink fieldCode="DE" term="%22Production+scheduling%22">Production scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22Industrial+engineering%22">Industrial engineering</searchLink><br /><searchLink fieldCode="DE" term="%22Industrial+management%22">Industrial management</searchLink><br /><searchLink fieldCode="DE" term="%22Comparative+studies%22">Comparative studies</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We present and compare a number of branch and bound algorithms for minimizing the total weighted tardiness in job shops. There arc basically two types of branching schemes. The first one inserts operations in a partial schedule, while the second one fixes arcs in the disjunctive graph formulation of the problem. The bounding schemes are based on the analysis of precedence constraints, and on the solution of nonpreemptive single machine subproblems that are subject to so-called delayed precedence constraints. We obtain optimal solutions for all the instances with ten jobs and ten machines that we consider, including three tardiness versions of a well-known 10 x 10 instance introduced by Muth and Thompson [1] in 1963. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of IIE Transactions 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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=11897366 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1023/A:1007405915227 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 10 StartPage: 109 Subjects: – SubjectFull: Tardiness Type: general – SubjectFull: Job shops Type: general – SubjectFull: Production scheduling Type: general – SubjectFull: Industrial engineering Type: general – SubjectFull: Industrial management Type: general – SubjectFull: Comparative studies Type: general Titles: – TitleFull: A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Singer, Marcos – PersonEntity: Name: NameFull: Pinedo, Michael IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 02 Text: Feb98 Type: published Y: 1998 Identifiers: – Type: issn-print Value: 0740817X Numbering: – Type: volume Value: 30 – Type: issue Value: 2 Titles: – TitleFull: IIE Transactions Type: main |
| ResultId | 1 |
