BibTex RIS Cite

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

Year 2013, Volume: 26 Issue: 1, 97 - 106, 31.03.2013

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

References

  • Öztürkoğlu, Y. and Bulfin, R., A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying International
  • Technology, 57: 753-762, (2011). Advanced
  • Manufacturing [2] Browne, S., Yechiali U., Scheduling deteriorating jobs on a single processor. Operations Research, 38: 495- 498, (1990).
  • Lee, C.Y. and Leon, V.J., Machine scheduling with a rate-modifying
  • Operational Research, 128: 119-128, (2001). European Journal
  • 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).
  • Smith, W.E., Various optimizers for single state production. Naval Research Logistics Quarterly, 3: 59- 66, (1956).
  • 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).
  • Emmons, H., A note on a scheduling problem with dual criteria. Naval Research Logistics Quarterly, 22: 615-616, (1975).
  • Van-Wassenhove, L. N., Gelders, L.F., Solving a bicriterion scheduling problem. European Journal of Operational Research, 4: 42-8, (1980).
  • Chen, C. L. and Bulfin, R. L., Complexity of single machine, multi-criteria scheduling problems. European Journal of Operational Research, 70: 115-125, (1993).
  • Kondakci, S., Azizoglu, M., Koksalan, M., Note: Bicriteria scheduling for minimizing flow time and maximum tardiness. Naval Research Logistics, 43: 929- 36, (1996).
  • Chen, W.-J., Minimizing total flow time and maximum tardiness with periodic maintenance. Journal of Quality in Maintenance Engineering, 13-3: 293-303, (2007).
  • Burns, R. N., Scheduling to minimize weighted sum of completion times with secondary criteria. Naval Research Logistics Quarterly, 23-1:125-129, (1976).
  • 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).
  • Miyazaki, S., One machine scheduling problem with dual criteria. Journal of the Operations Research Society of Japan, 24-1: 37-50, (1982).
  • 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).
  • 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).
  • Posner, M. E., Minimizing weighted completion times with deadlines. Operations Research, 33: 562-574, (1985).
  • Bacghi,U. and Ahmadi, R. H., An improved lower
  • bound for minimizing weighted completion times with
  • deadlines. Operations Research, 35: 311-313, (1987).
  • Nelson, R.T., Sarin, R.K., Daniels, R.L., Scheduling with multiple performance measures: The one-machine case. Management Science, 32: 464-480, (1986).
  • 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).
  • 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).
  • 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).
Year 2013, Volume: 26 Issue: 1, 97 - 106, 31.03.2013

Abstract

References

  • Öztürkoğlu, Y. and Bulfin, R., A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying International
  • Technology, 57: 753-762, (2011). Advanced
  • Manufacturing [2] Browne, S., Yechiali U., Scheduling deteriorating jobs on a single processor. Operations Research, 38: 495- 498, (1990).
  • Lee, C.Y. and Leon, V.J., Machine scheduling with a rate-modifying
  • Operational Research, 128: 119-128, (2001). European Journal
  • 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).
  • Smith, W.E., Various optimizers for single state production. Naval Research Logistics Quarterly, 3: 59- 66, (1956).
  • 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).
  • Emmons, H., A note on a scheduling problem with dual criteria. Naval Research Logistics Quarterly, 22: 615-616, (1975).
  • Van-Wassenhove, L. N., Gelders, L.F., Solving a bicriterion scheduling problem. European Journal of Operational Research, 4: 42-8, (1980).
  • Chen, C. L. and Bulfin, R. L., Complexity of single machine, multi-criteria scheduling problems. European Journal of Operational Research, 70: 115-125, (1993).
  • Kondakci, S., Azizoglu, M., Koksalan, M., Note: Bicriteria scheduling for minimizing flow time and maximum tardiness. Naval Research Logistics, 43: 929- 36, (1996).
  • Chen, W.-J., Minimizing total flow time and maximum tardiness with periodic maintenance. Journal of Quality in Maintenance Engineering, 13-3: 293-303, (2007).
  • Burns, R. N., Scheduling to minimize weighted sum of completion times with secondary criteria. Naval Research Logistics Quarterly, 23-1:125-129, (1976).
  • 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).
  • Miyazaki, S., One machine scheduling problem with dual criteria. Journal of the Operations Research Society of Japan, 24-1: 37-50, (1982).
  • 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).
  • 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).
  • Posner, M. E., Minimizing weighted completion times with deadlines. Operations Research, 33: 562-574, (1985).
  • Bacghi,U. and Ahmadi, R. H., An improved lower
  • bound for minimizing weighted completion times with
  • deadlines. Operations Research, 35: 311-313, (1987).
  • Nelson, R.T., Sarin, R.K., Daniels, R.L., Scheduling with multiple performance measures: The one-machine case. Management Science, 32: 464-480, (1986).
  • 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).
  • 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).
  • 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).
There are 26 citations in total.

Details

Primary Language English
Journal Section Industrial Engineering
Authors

Yucel Ozturkoglu This is me

Publication Date March 31, 2013
Published in Issue Year 2013 Volume: 26 Issue: 1

Cite

APA Ozturkoglu, Y. (2013). A Bi-Criteria Single Machine Scheduling with Rate-Modifying-Activity. Gazi University Journal of Science, 26(1), 97-106.
AMA Ozturkoglu Y. A Bi-Criteria Single Machine Scheduling with Rate-Modifying-Activity. Gazi University Journal of Science. March 2013;26(1):97-106.
Chicago Ozturkoglu, Yucel. “A Bi-Criteria Single Machine Scheduling With Rate-Modifying-Activity”. Gazi University Journal of Science 26, no. 1 (March 2013): 97-106.
EndNote Ozturkoglu Y (March 1, 2013) A Bi-Criteria Single Machine Scheduling with Rate-Modifying-Activity. Gazi University Journal of Science 26 1 97–106.
IEEE Y. Ozturkoglu, “A Bi-Criteria Single Machine Scheduling with Rate-Modifying-Activity”, Gazi University Journal of Science, vol. 26, no. 1, pp. 97–106, 2013.
ISNAD Ozturkoglu, Yucel. “A Bi-Criteria Single Machine Scheduling With Rate-Modifying-Activity”. Gazi University Journal of Science 26/1 (March 2013), 97-106.
JAMA Ozturkoglu Y. A Bi-Criteria Single Machine Scheduling with Rate-Modifying-Activity. Gazi University Journal of Science. 2013;26:97–106.
MLA Ozturkoglu, Yucel. “A Bi-Criteria Single Machine Scheduling With Rate-Modifying-Activity”. Gazi University Journal of Science, vol. 26, no. 1, 2013, pp. 97-106.
Vancouver Ozturkoglu Y. A Bi-Criteria Single Machine Scheduling with Rate-Modifying-Activity. Gazi University Journal of Science. 2013;26(1):97-106.