Subset-restricted interchange for dynamic min-max scheduling problems

DOI10.1137/S0895480198343418MaRDI QIDQ2706175zbMATH OpenOpenAlexFDO

Authors George Steiner, Paul Stephenson

Publication date 19 March 2001

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480198343418

zbMATH Keywords

branch and boundprecedence order

Mathematics Subject Classification ID

Partial orders, general (06A06) Stochastic scheduling theory in operations research (90B36) Minimax problems in mathematical programming (90C47) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Review text

This paper deals with scheduling two specific jobs within a sequence of \(n\) jobs, i.e. the so-called pair-wise job interchange problem. This problem is extended to the case that interchanging of the two given jobs is permitted only, if the intermediate jobs belong to a restricted subclass of jobs. The problem then is to determine the order of the two jobs which is optimal with respect to a cost function. In order to solve the problem efficiently a precedence order is derived and utilized by the subsequently applied branch and bound algorithm. By means of numerical examples it is shown that the algorithm with precedence order saves on an average about 58\% of the CPU time compared with an algorithm without precedence order necessary for solving the problem.

Recommendations

• Optimal job-shop scheduling with two jobs in systems with unrestricted paths
• Generalized pairwise interchanges and machine scheduling
• scientific article; zbMATH DE number 3984950
• scientific article; zbMATH DE number 3906215
• Improving job-shop schedules through critical pairwise exchanges

Cited in

(2)

• Generalized pairwise interchanges and machine scheduling
• Single machine batch scheduling with release times and delivery costs

This page was built for publication: Subset-restricted interchange for dynamic min-max scheduling problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2706175)