Scheduling with arranged multi-purpose machines

DOI10.1504/IJOR.2010.033545MaRDI QIDQ614212zbMATH OpenOpenAlexFDO

Authors Mourad Boudhar, Hamza Tchikou

Publication date 27 December 2010

Published in International Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1504/ijor.2010.033545

zbMATH Keywords

branch and boundcomplexityheuristicsmakespanMPMsmulti-purpose machinesscheduling theory

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Summary: In the present study, we consider a special case of multi-purpose machines (MPMs) in which there is a linear order given for the machines. In addition, for each job \(J_i(1\leq i\leq n)\), a ``first permissible machine \(h_i (1\leq h(i)\leq m)\) is given on which it can be processed. Thus, machines \(M_{h_i},\ldots , M_m\) are capable of processing job \(J_i\) while machines \(M_1,\ldots , M_{h_i - 1}\) cannot process job \(J_i\). Each job \(J_i\) requires a time \(p_i\) and the goal is to minimise the makespan. We prove the NP-hardness of the general problem and present some polynomial sub-problems. Heuristics with an exact algorithm of branch and bound type are also presented with numerical experimentations.

Recommendations

• scientific article; zbMATH DE number 890241
• Complexity of scheduling problems with multi-purpose machines
• Scheduling problem with multi-purpose parallel machines
• The complexity of two-job shop problems with multi-purpose unrelated machines.
• The computational complexities of two multi-purpose machines scheduling problem with setup times

Cited in

(7)

• Complexity of scheduling problems with multi-purpose machines
• A multi-period machine assignment problem
• The computational complexities of two multi-purpose machines scheduling problem with setup times
• Machine Scheduling for Multi-product Disassembly
• scientific article; zbMATH DE number 890241 (Why is no real title available?)
• Scheduling problem with multi-purpose parallel machines
• Scheduling High Multiplicity Jobs on Parallel Multi-Purpose Machines with Setup Times and Machine Available Times

This page was built for publication: Scheduling with arranged multi-purpose machines

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