Â¥Ö÷

Çë½Ì¡°Scheduling to minimize average completion time¡±ÎÊÌâ ¡ºËã·¨µ¼ÂÛ¡»µÄ×÷Òµ16£­2 Suppose you are given a set S = {a1, a2, ..., an} of tasks, where task ai requires pi units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let ci be the completion time of task ai , that is, the time at which task ai completes processing. Your goal is to minimize the average completion time, that is, to minimize . ¡­¡­ Suppose now that the tasks are not all available at once. That is, each task has a release time ri before which it is not available to be processed. Suppose also that we allow preemption, so that a task can be suspended and restarted at a later time.  Give an algorithm that schedules the tasks so as to minimize the average completion time in this new scenario. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm.    Êղؠ  ·ÖÏí   ¶¥(0)

	µÚ2Â¥

Õâ¸öÎÊÌâµÄËã·¨±¾Éí²»ÄÑ£¬¿ÉÊÇÎҺܾö¼²»ÄÜÏëµ½Ö¤Ã÷Ëã·¨ÕýÈ·µÄ°ì·¨¡£

	µÚ3Â¥

ÎÒ¾õµÃƽ¾ùÍê³Éʱ¼ä×îС»¯£¬ÔÚri=0,²»¿ÉÖжϵĵ÷¶ÈÎÊÌâÖУ¬¾ÍµÈÓÚ×ÜÍ깤ʱ¼ä×îС»¯¡£¿ÉÖжÏÎÊÌâµÄÒ»¸öÌØÀýÊDz»¿ÉÖжϡ£ËµÁ˺ÃÏñûÓÐ˵°¡£¬Ë®Æ½ÓÐÏÞ