ON PARETO SET FOR A BI-CRITERIA SINGLE MACHINE SCHEDULING PROBLEM
Article Sidebar
Main Article Content
Abstract
This paper considers a bi-criteria planning problems on a single machine, with the goal of minimizing total square time duration and maximizing earliness. To solve this problem we have to find the Pareto set. We introduced a strong relation between lower bound, upper bound of the problem and the number of efficient solutions via a theorem which shows also that the lower bound is near to optimal solution if the number of efficient solutions is small.
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
Tikrit Journal of Pure Science is licensed under the Creative Commons Attribution 4.0 International License, which allows users to copy, create extracts, abstracts, and new works from the article, alter and revise the article, and make commercial use of the article (including reuse and/or resale of the article by commercial entities), provided the user gives appropriate credit (with a link to the formal publication through the relevant DOI), provides a link to the license, indicates if changes were made, and the licensor is not represented as endorsing the use made of the work. The authors hold the copyright for their published work on the Tikrit J. Pure Sci. website, while Tikrit J. Pure Sci. is responsible for appreciate citation of their work, which is released under CC-BY-4.0, enabling the unrestricted use, distribution, and reproduction of an article in any medium, provided that the original work is properly cited.
References
]1] Abdul-Razaq T. S. and Kawi H. Y., (2010), ‘Single Machine Scheduling to Minimize a Function Of Square Completion Time And Maximum Earliness Simultaneously’, AL-MUSTANSIRIYAH JOURNAL OF SCIENCE, 21-5, 375-390.
[2] Bagga P. C. and Kalra K. R., (1980), ‘A Node Elimination Procedure for Townsen's Algorithm for Solving The Single Machine Quadratic Penalty Function Scheduling Problem’, MANAGEMENT SCIENCE 26, 633-636.
[3] Gupta S. K. and Sen T., (1984), ‘On the Single Machine Scheduling Problem with Quadratic Penalty Function of Completion Times: An Improved Branching Procedure’, MANAGEMENT SCIENCE, 30, 644-647.
[4] Hoogeveen J. A., (2005), ‘Invited Review Multi-Criteria Scheduling’, EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 167, 592-623.
[5] Hoogeveen J. A. and Van de Velde S. L., (1995), ‘Minimizing Total Completion Time and Maximum Cost Simultaneously Is Solvable in Polynomial Time’, OPERATIONS RESEARCH LETTERS, 17, 205-208.
[6] Hoogeveen J. A. and Van de Velde S. L., (1990), ‘Polynomial Time Algorithms for Single Machine Multi-Criteria Scheduling’, MEMORANDUM COSOR 92-21.
[7] Krasimira G, Leoneed K., Vassil G., (2015), ‘A Survey of Solving Approaches for Multiple Objective Flexible Job Shop Scheduling Problems’, BULGARIAN ACADEMY OF SCIENCES, CYBERNETICS AND INFORMATION TECHNOLOGIES, 15-2, 3-22.
[8] Kurz M. E. and Canterbury S., (2005), ‘Minimizing Total Flow Time and Maximum Earliness on A Single Machine Using Multiple Measures of Fitness’, GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 803-809.
[9] Lazarev A., Arkhipov D., Werner F., (2015), ‘Single machine scheduling: finding the Pareto set for jobs with equal processing times with respect to criteria Lmax and Cmax’, 7TH MULTIDISCIPLINARY INTERNATIONAL CONFERENCE ON SCHEDULING: THEORY AND APPLICATIONS, 25-28.
[10] Lee C. Y. and Vairaktarakis G. L., (1993), ‘Complexity of Single Machine Hierarchical Scheduling: A Survey’, COMPLEXITY IN NUMERICAL OPTIMIZATION, 19, 269-298.
[11] Lei D., (2009), ‘Multi-Objective Production Scheduling: A Survey’, INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 43 (9-10), 926-938.
[12] Nguyen V. and Bao H. P., (2016), ‘An Efficient Solution to The Mixed Shop Scheduling Problem Using a Modified Genetic Algorithm’, PROCEDIA COMPUTER SCIENCE, 95, 475-482.
[13] T'kindt V. J. and Billaut C., (2001), ‘Multi-Criteria Scheduling Problems: A Survey’, RAIRO OPERATIONS RESEARCH, 35-2, 143-163.
[14] Townsend W., (1978), ‘The Single Machine Problem with Quadratic Penalty Function of Completion
Times: A Branch and Bound Solution’, MANAGEMENT SCIENCE, 24, 530-534.