Machine scheduling with a rate-modifying activity.

*(English)*Zbl 0983.90020Summary: Motivated by a problem commonly found in electronic assembly lines, this paper deals with the problem of scheduling jobs and a rate-modifying activity on a single machine. A rate-modifying activity is an activity that changes the production rate of the equipment under consideration. Hence the processing times of jobs vary depending on whether the job is scheduled before or after the rate-modifying activity. The decisions under consideration are when to schedule the rate modifying activity and the sequence of jobs to optimize some performance measure.

We develop polynomial algorithms for solving problems of minimizing makespan, and total completion time, respectively. We also develop pseudo-polynomial algorithms for solving problems of total weighted completion time under the agreeable ratio assumption. We prove that the problem of minimizing maximum lateness is NP-hard and also provide a pseudo-polynomial time algorithm to solve it optimally.

We develop polynomial algorithms for solving problems of minimizing makespan, and total completion time, respectively. We also develop pseudo-polynomial algorithms for solving problems of total weighted completion time under the agreeable ratio assumption. We prove that the problem of minimizing maximum lateness is NP-hard and also provide a pseudo-polynomial time algorithm to solve it optimally.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

##### Keywords:

machine scheduling; job scheduling; rate-modifying activity; polynomial algorithms; performance measure
PDF
BibTeX
XML
Cite

\textit{C. Y. Lee} and \textit{V. J. Leon}, Eur. J. Oper. Res. 128, No. 1, 119--128 (2001; Zbl 0983.90020)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Adiri, I.; Yehudai, Z., Scheduling on machines with variable service rates, Computers & operations research, 14, 4, 289-297, (1987) · Zbl 0629.90049 |

[2] | Adiri, I.; Bruno, J.; Frostig, E.; Rinnooy Kan, A.H.G., Single machine flow-time scheduling with a single breakdown, Acta informatica, 26, 679-696, (1989) · Zbl 0657.68033 |

[3] | Baker, K.R., Elements of sequencing and scheduling, 1995. Amos Tuck School, Dartmouth College, Hanover, NH |

[4] | Lawler, E.L., Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976 · Zbl 0413.90040 |

[5] | Lee, C.-Y., Parallel machines scheduling with non-simultaneous machine available time, Discrete applied mathematics, 30, 53-61, (1991) · Zbl 0722.90032 |

[6] | Lee, C.-Y., Machine scheduling with an availability constraint, Journal of global optimization. (special issue on optimization on scheduling applications), 9, 395-416, (1996) · Zbl 0870.90071 |

[7] | Lee, C.-Y., Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint, Operations research letters, 20, 129-139, (1997) · Zbl 0882.90069 |

[8] | Lee, C.-Y.; Lei, L.; Pinedo, M., Current trend in deterministic scheduling, Annals of operations research, 70, 1-42, (1997) |

[9] | Lee, C.-Y.; Liman, S.D., Single machine flow-time scheduling with scheduled maintenance, Acta informatica, 29, 375-382, (1992) · Zbl 0738.68043 |

[10] | Lee, C.-Y.; Liman, S.D., Capacitated two-parallel machines scheduling to minimize sum of job completion times, Discrete applied mathematics, 41, 211-222, (1993) · Zbl 0778.90028 |

[11] | Lee, C.-Y.; Uzsoy, R., A new dynamic programming algorithm for the parallel machines total weighted completion time problem, Operations research letters, 11, 73-75, (1992) · Zbl 0760.90057 |

[12] | Leon, V.J.; Wu, S.D., On scheduling with ready-times, due-dates and vacations, Naval research logistics, 39, 53-65, (1992) · Zbl 0764.90049 |

[13] | Mosheiov, G., Minimizing the sum of job completion times on capacitated parallel machines, Mathematical and computer modelling, 20, 91-99, (1994) · Zbl 0810.90072 |

[14] | Pinedo, M.L., 1995. Scheduling: Theory, Algorithms and Systems, Prentice-Hall, Englewood Cliffs, NJ · Zbl 1145.90393 |

[15] | Sanlaville, E., Schmidt, G., 1997. Machine scheduling with availability constraints. Unpublished manuscript · Zbl 0917.68018 |

[16] | Schmidt, G., Scheduling on semi-identical processors, ZOR - zeitschrift fur operations research, 28, 153-162, (1984) · Zbl 0551.90044 |

[17] | Schmidt, G., Scheduling independent tasks with deadlines on semi-identical processors, Journal of the operations research society, 39, 271-277, (1988) · Zbl 0657.90051 |

[18] | Trick, M.A., Scheduling multiple variable-speed machines, Operations research, 42, 234-248, (1994) · Zbl 0805.90064 |

[19] | Whitaker, L.O., 1996. Integrated production and maintenance activities. M.S. Thesis, Department of Industrial Engineering, Texas A&M University, College Station, TX |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.