Two-Machine Flowshop Problem with Release Dates, Rejection and Non-Availability Interval on the First Machine

Abstract:

This paper studies a two-machine flowshop problem with release dates, rejection and non-availability interval on the first machine. The non-availability interval often origins from equipments maintain or man-power. Usually, in order to pursue maximal profit, some jobs which can be rejected, and in this situation the rejection penalty should be paid. Our objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. For this demonstrated NP-hard in strong sense, we propose a heuristic method and further demonstrate that its worst case performance is 3.

• Periodical: Applied Mechanics and Materials (Volume 620)
• Pages: 80-83
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.620.80
• Online since: August 2014
• Authors: Xie Xie*, Xiang Yu Kong, Yong Yue Zheng, Kun Wei
• Keywords: Heuristic, Non-Availability Interval, Rejection, Release Dates

References

[1] Y. Bartal, S. Leonardi, A.M. Spaccamela, J. Sgall and L. Stougie, Multi-processor Scheduling with Rejection, SIAM Journal on Discrete Mathematics, 13 (2000), 64-78.

DOI: 10.1137/s0895480196300522

[2] L.Q. Zhang, L.F. Lu, J.J. Yuan, Single Machine Scheduling with Release dates and Rejection, European Journal of Operation Research, 198 (2009), 975-978.

DOI: 10.1016/j.ejor.2008.10.006

[3] I. Kacem and A.R. Mahjoub, Fully Polynomical Time Approximation Scheme for the Weighted Flow-time Minimization on Single Machine with a Fixed Non-availability Interval, Computer & Industrial Engineering, 56 (2009), 1708-1712.

DOI: 10.1016/j.cie.2008.09.042

[4] I. Kacem, Approximation on Algorithms for the Makespan Minimization with Positive Tails on a Single Machine with a Fixed Non-availability Interval, Journal of Combinatorial Optimization, 17 (2009), 117-133.

DOI: 10.1007/s10878-007-9102-4

[5] H. Kellerer, M.A. Kubzin and V.A. Strusevich, Two Simple Constant Ratio Approximation Algorithms for Minimize the Total Weighted Completion Time on a Single Machine with a Fixed Non-availability Interval, European Journal of Operational Research, 199 (2009).

DOI: 10.1016/j.ejor.2008.11.003

[6] G. Mosheiov and A. Sarig, Scheduling a Maintenance Activity to Minimize Total Weighted Completion Time, Computers and Mathematics with Applications, 57 (2009), 619-623.

DOI: 10.1016/j.camwa.2008.11.008

[7] L.F. Lu, L.Q. Zhang and J.J. Yuan, The Unbounded Parallel batch Machine Scheduling with Release Dates and Rejection to Minimize Makespan, Theoretical Computer Science, 369 (2008), 283-289.

DOI: 10.1016/j.tcs.2008.02.015

[8] L.Y. Kang and C.T. Ng, A Fully Polynomial-time Approximation Scheme for Parallel-machine Scheduling with Deteriorating Jobs, International Journal of Production Economics, 109 (2007), 180-184.

DOI: 10.1016/j.ijpe.2006.11.014

[9] J.K. Lenstra, A.H. G Rinnooy Kan and P. Brucker, Complexity of Machine Scheduling Problems, Annals of Discrete Mathematics 1 (1977), 343-362.

DOI: 10.1016/s0167-5060(08)70743-x