Жұмыс кестесін автоматтандыру: компьютерлік ғылымдағы маңызды мәселе. Бірнеше машинаға жұмыстарды тиімді бөлу арқылы орындау уақытын азайтуға көмектеседі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Бірыңғай машинаны жоспарлау (біркелкі байланысты машинаны жоспарлау немесе байланысты машинаны жоспарлау деп те аталады) – компьютерлік ғылым және операциялық зерттеулердегі оптимизация мәселесі. Бұл жұмыс кестесін оптималды етудің бір түрі. Бізге әртүрлі өңдеу уақыттары бар n жұмыс J1, J2, ..., Jn беріледі, оларды m түрлі машинада жоспарлау керек. Мақсат – жоспарды орындауға қажетті уақытты (makespan) барынша азайту. I машинаның j жұмысын өңдеуге кететін уақыты pi,j арқылы белгіленеді. Жалпы жағдайда, pi,j шамалары өзара байланысты емес және оң өңдеу уақытының кез келген матрицасы мүмкін. Бірыңғай машинаны жоспарлау деп аталатын ерекше нұсқада кейбір машиналар басқаларына қарағанда біркелкі жылдам. Бұл дегеніміз, әр машина i үшін жылдамдық коэффициенті si бар, және машина i-де j жұмысының орындалу уақыты pi,j = pj / si. Жұмыс кестесін оптималды жоспарлау мәселелерін стандартты үш өрістік нотацияда бірыңғай машина нұсқасы бірінші өрісте Q арқылы белгіленеді. Мысалы, "Q||" деп белгіленген мәселе – шектеулерсіз бірыңғай машинаны жоспарлау мәселесі, онда мақсат – ең көп аяқталу уақытын азайту. Бірыңғай машинаны жоспарлаудың ерекше жағдайы – бірдей машиналарды жоспарлау, онда барлық машиналардың жылдамдығы бірдей. Бұл нұсқа бірінші өрісте P арқылы белгіленеді. Мәселенің кейбір нұсқаларында, ең көп аяқталу уақытын азайтудың орнына, орташа аяқталу уақытын азайту қажет (барлық n жұмыстың орташасы); ол Q|| арқылы белгіленеді. Жалпы алғанда, кейбір жұмыстар басқаларына қарағанда маңыздырақ болған кезде, әр жұмыстың әртүрлі салмағы бар аяқталу уақытының салмақталған орташасын барынша азайту қажет болуы мүмкін. Бұл Q|| арқылы белгіленеді.
Uniform machine scheduling (also called uniformly related machine scheduling or related machine scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We are given n jobs J1, J2, , Jn of varying processing times, which need to be scheduled on m different machines. The goal is to minimize the makespan the total time required to execute the schedule. The time that machine i needs in order to process job j is denoted by pi,j. In the general case, the times pi,j are unrelated, and any matrix of positive processing times is possible. In the specific variant called uniform machine scheduling, some machines are uniformly faster than others. This means that, for each machine i, there is a speed factor si, and the run time of job j on machine i is pi,j = pj / si. In the standard three field notation for optimal job scheduling problems, the uniform machine variant is denoted by Q in the first field. For example, the problem denoted by " Q||" is a uniform machine scheduling problem with no constraints, where the goal is to minimize the maximum completion time. A special case of uniform machine scheduling is identical machines scheduling, in which all machines have the same speed. This variant is denoted by P in the first field. In some variants of the problem, instead of minimizing the maximum completion time, it is desired to minimize the average completion time (averaged over all n jobs); it is denoted by Q||. More generally, when some jobs are more important than others, it may be desired to minimize a weighted average of the completion time, where each job has a different weight. This is denoted by Q||.