A Bi-Criteria Single Machine Scheduling with Rate-Modifying-Activity

Abstract

In this paper, we consider a single machine scheduling problem with two criteria: minimizing both total flow time with total tardiness and minimize maximum tardiness with number of tardy jobs. Unlike the classical scheduling problems, we use a job position deterioration, which means that the job processing time increases as a function of the job position. Besides deteriorated jobs, we also consider rate-modifying-activities which alter the efficiency of the deteriorating processor. This is the first paper, to combine both time dependent processing times and problems with rate-modifying-activity in the bi-criteria objectives. To solve the new type of problem, we introduce a new scheduling mathematical model which is based on one developed Ozturkoglu and Bulfin [1]. To analyze the efficiency of the mathematical model, we use three different approaches. According to computational results, up to 50 jobs can be solved in less than one minute.

Keywords:

 

 

Single-Machine Scheduling, Bi-criteria, Deteriorated Jobs, Rate-Modifying- Activity

Keywords

• Single-Machine Scheduling, Bi-criteria, Deteriorated Jobs, Rate-Modifying- Activity

References

1. Öztürkoğlu, Y. and Bulfin, R., A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying International
2. Technology, 57: 753-762, (2011). Advanced
3. Manufacturing [2] Browne, S., Yechiali U., Scheduling deteriorating jobs on a single processor. Operations Research, 38: 495- 498, (1990).
4. Lee, C.Y. and Leon, V.J., Machine scheduling with a rate-modifying
5. Operational Research, 128: 119-128, (2001). European Journal
6. of Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy, K. A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A Survey. Annual Discrete Mathematics, 5: 287–326, (1979).
7. Smith, W.E., Various optimizers for single state production. Naval Research Logistics Quarterly, 3: 59- 66, (1956).
8. Heck, H., Roberts S., A note on the extension of a result on scheduling with secondary criteria. Naval Research Logistics Quarterly, 19: 403-405, (1972).

9. Emmons, H., A note on a scheduling problem with dual criteria. Naval Research Logistics Quarterly, 22: 615-616, (1975).
10. Van-Wassenhove, L. N., Gelders, L.F., Solving a bicriterion scheduling problem. European Journal of Operational Research, 4: 42-8, (1980).
11. Chen, C. L. and Bulfin, R. L., Complexity of single machine, multi-criteria scheduling problems. European Journal of Operational Research, 70: 115-125, (1993).
12. Kondakci, S., Azizoglu, M., Koksalan, M., Note: Bicriteria scheduling for minimizing flow time and maximum tardiness. Naval Research Logistics, 43: 929- 36, (1996).
13. Chen, W.-J., Minimizing total flow time and maximum tardiness with periodic maintenance. Journal of Quality in Maintenance Engineering, 13-3: 293-303, (2007).
14. Burns, R. N., Scheduling to minimize weighted sum of completion times with secondary criteria. Naval Research Logistics Quarterly, 23-1:125-129, (1976).
15. Bansal, S. P., Single machine scheduling to minimize the weighted sum of completion times with secondary criterion: A branch and bound approach. European Journal of Operations Research, 5: 177-181, (1980).
16. Miyazaki, S., One machine scheduling problem with dual criteria. Journal of the Operations Research Society of Japan, 24-1: 37-50, (1982).
17. Shanthikumar, J. G., Buzacott, J. A., On the use of decomposition approaches in a single machine scheduling problem. Journal of the Operations Research Society of Japan, 25: 29-47 (1982).
18. Potts, C. N., Van Wassenhove,L. N., An algorithm for single machine sequencing with deadlines to minimize total weighted completion time. European Journal of Operations Research, 12: 379-387, (1983).
19. Posner, M. E., Minimizing weighted completion times with deadlines. Operations Research, 33: 562-574, (1985).
20. Bacghi,U. and Ahmadi, R. H., An improved lower
21. bound for minimizing weighted completion times with
22. deadlines. Operations Research, 35: 311-313, (1987).
23. Nelson, R.T., Sarin, R.K., Daniels, R.L., Scheduling with multiple performance measures: The one-machine case. Management Science, 32: 464-480, (1986).
24. Shanthikumar, J. G., Scheduling n jobs on one machine to minimize the maximum tardiness with minimum number tardy. Computers and Operations Research, 10: 255-266, (1983).
25. Chen, C.L., Bulfin, R. L., Scheduling a single machine to minimize two criteria: Maximum tardiness and number of tardy jobs. IIE Transactions, 26: 76-84, (1994).
26. Huo Y., Leung, J.Y.T., Zhao, H., Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness. European Journal of Operational Research, 177: 116-134, (2007).