Two parallel-machine scheduling problems with function constraint

DOI10.1155/2020/2717095MaRDI QIDQ2187975zbMATH OpenOpenAlexFDO

Authors Chia-Lun Hsu, Jan-Ray Liao

Publication date 3 June 2020

Published in Discrete Dynamics in Nature and Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2020/2717095

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Review text

Summary: The objective of this paper is to minimize both the makespan and the total completion time. Since parallel-machine scheduling which contains the function constraint problem has been a new issue, this paper explored two parallel-machine scheduling problems with function constraint, which refers to the situation that the two machines have a same function but one of the machines has another. We pointed out that the function constraint occurs not only in the manufacturing system but also in the service system. For the makespan problem, we demonstrated that it is NP-hard in the ordinary sense. In addition, we presented a polynomial time heuristic for this problem and have proved its worst-case ratio is not greater than 5/4. Furthermore, we simulated the performance of the algorithm through computational testing. The overall mean percent error of the heuristic is 0.0565\%. The results revealed that the proposed algorithm is quite efficient. For the total completion time problem, we have proved that it can be solved in \(O\left( n^4\right)\) time.

Recommendations

• Parallel machine scheduling with time dependent processing times
• Scheduling to minimize the maximum total completion time per machine
• Parallel-machine scheduling with time dependent processing times
• Parallel-machine scheduling with time-dependent and machine availability constraints
• Scheduling parallel machines with a single server: Some solvable cases and heuristics

Cites work

• A state-of-the-art review of parallel-machine scheduling research
• An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan
• scientific article; zbMATH DE number 1783886 (Why is no real title available?)
• Makespan minimization for two parallel machines scheduling with a periodic availability constraint: mathematical programming model, average-case analysis, and anomalies
• Minimizing makespan in three-machine flow shops with deteriorating jobs
• Minimizing the makespan on two identical parallel machines with mold constraints
• Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties
• Parallel machine problems with equal processing times: a survey
• Parallel-machine scheduling with time dependent processing times
• Scheduling on parallel identical machines with job-rejection and position-dependent processing times

Cited in

(3)

• On the complexity of two machine job-shop scheduling with regular objective functions
• Optimization for due-window assignment scheduling with position-dependent weights
• Maximizing set function formulation of two scheduling problems

This page was built for publication: Two parallel-machine scheduling problems with function constraint

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