A Mixed Integer Mathematical Programming Optimization Model for the NP-Hard Industrial Processes Scheduling Problem

Abstract:

This paper investigates single machine scheduling problem with unequal release times and deterioration jobs where the objective function of it is minimal makespan. A mixed integer mathematical programming optimization model is developed for the problem which belongs to the NP-hard problem. The model is tested on examples and compared with a heuristic algorithm introduced by Lee et al.. Moreover, the branch-bound algorithm proposed by Lee et al. also can obtained optimal solutions the same as the results from CPLEX but the CPU time of it for 28 jobs even needs more than 2 hours, thus, the results between them are not compared. According to results of computational tests, it is showed that the proposed model is very effective in solving problems because it can obtain optimal solutions within a short time. Therefore, it is very useful and valuable for decision maker who requires the optimal solutions.

• Periodical: Advanced Materials Research (Volume 645)
• Pages: 290-294
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.645.290
• Online since: January 2013
• Authors: Hua Ping Wu, Min Huang, Xing Wei Wang
• Keywords: Deterioration Jobs, Make Span, Mixed Integer Mathematical Programming, Single Machine Scheduling, Unequal Release Times

References

[1] D. Gupta, S. K. Gupta. Single facility scheduling with nonlinear processing times. Comput. Ind. Eng. Vol. 14 (1988), pp.387-393.

DOI: 10.1016/0360-8352(88)90041-1

[2] S. Browne, U. Yechiali. Scheduling deteriorating jobs on a single processor. Oper. Res. Vol. 38 (1990), pp.495-498.

DOI: 10.1287/opre.38.3.495

[3] A. Bachman, T. C. E. Cheng, A. Janiak, C. T. Ng. Scheduling start time dependent jobs to minimize the total weighted completion time. J. Oper. Res. Soc. Vol. 53 (2002), pp.688-693.

DOI: 10.1057/palgrave.jors.2601359

[4] T. C. E. Cheng, Q. Ding. Single machine scheduling with step-deteriorating processing times. Eur. J. Oper. Res. Vol. 134 (2001), pp.623-630.

DOI: 10.1016/s0377-2217(00)00284-8

[5] P-J Lai, W-C Lee. Single-machine scheduling with a nonlinear deterioration function. Inf. Process. Lett. Vol. 110 (2011), pp.455-459.

[6] T. C. E. Cheng, W-C Lee, C-C Wu. Single-machine scheduling with deteriorating functions for job processing times. Appl. Math. Model. Vol. 34 (2010), pp.4171-4178.

DOI: 10.1016/j.apm.2010.04.014

[7] J-B Wang, C. Wang. Single-machine due-window assignment problem with learning effect and deteriorating jobs. Appl. Math. Model. Vol. 35 (2011), pp.4017-4022.

DOI: 10.1016/j.apm.2011.02.023

[8] C-L Zhao, C-J Hsu, D-L Yang. Considerations of single-machine scheduling with deteriorating jobs. Appl. Math. Model. Vol. 35 (2011), pp.5134-5142.

DOI: 10.1016/j.apm.2011.04.018

[9] Wang, C-M Wei. Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties. Appl. Math. Comput. Vol. 217 (2011), pp.8093-8099.

DOI: 10.1016/j.amc.2011.03.010

[10] heng, W-H Wu, S-R Cheng, C-C Wu. Two-agent scheduling with position-based deteriorating jobs and learning effects. Appl. Math. Comput. Vol. 217 (2011), pp.8804-8824.

DOI: 10.1016/j.amc.2011.04.005

[11] Ng, S. Li, T. C. E. Cheng, J. Yuan. Preemptive scheduling with simple linear deterioration on a single machine. Theor. Comput. Sci. Vol. 411 (2011), pp.3578-3586.

DOI: 10.1016/j.tcs.2010.05.032

[12] sheiov, J. B. Sidney. Scheduling a deteriorating maintenance activity on a single machine. J. Oper. Res. Soc. Vol. 61 (2010), pp.882-887.

[13] E. Cheng, Q. Ding. The complexity of single machine scheduling with release times. Inf. Process. Lett. Vol. 65 (1998), pp.75-79.

[14] Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan. Optimization and approximation in the deterministic sequencing and scheduling: a survey. Ann. Discret. Math. Vol. 5 (1979), pp.287-326.

DOI: 10.1007/978-94-009-7801-0_3

[15] C-C Wu, Y-H Chung. Scheduling deteriorating jobs on a single machine with release times. Comput. Ind. Eng. Vol. 54 (2008), pp.441-452.

DOI: 10.1016/j.cie.2007.08.006

[16] Chu. A branch-and-bound algorithm to minimize total flow time with unequal release dates. Nav. Res. Logist. Vol. 39 (1992), pp.859-875.

DOI: 10.1002/1520-6750(199210)39:6<859::aid-nav3220390610>3.0.co;2-w