caa a22 4500 445838728 CHVBK 20180317145337.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s10951-010-0192-y doi (NATIONALLICENCE)springer-10.1007/s10951-010-0192-y Scheduling unit length jobs on parallel machines with lookahead information [Elektronische Daten] [Marvin Mandelbaum, Dvir Shabtay] This paper studies two closely related online-list scheduling problems of a set of n jobs with unit processing times on a set of m multipurpose machines. It is assumed that there are k different job types, where each job type can be processed on a unique subset of machines. In the classical definition of online-list scheduling, the scheduler has all the information about the next job to be scheduled in the list while there is uncertainty about all the other jobs in the list not yet scheduled. We extend this classical definition to include lookahead abilities, i.e., at each decision point, in addition to the information about the next job in the list, the scheduler has all the information about the next h jobs beyond the current one in the list. We show that for the problem of minimizing the makespan there exists an optimal (1-competitive) algorithm for the online problem when there are two job types. That is, the online algorithm gives the same minimal makespan as the optimal offline algorithm for any instance of the problem. Furthermore, we show that for more than two job types no such online algorithm exists. We also develop several dynamic programming algorithms to solve a stochastic version of the problem, where the probability distribution of the job types is known and the objective is to minimize the expected makespan. Springer Science+Business Media, LLC, 2010 Multipurpose machine scheduling nationallicence Lookahead information nationallicence Online algorithms nationallicence Eligibility constraint nationallicence Stochastic dynamic programming nationallicence Mandelbaum Marvin aut Shabtay Dvir Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/4(2011-08-01), 335-350 1094-6136 14:4<335 2011 14 10951 https://doi.org/10.1007/s10951-010-0192-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-010-0192-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Mandelbaum Marvin aut NATIONALLICENCE 700 1- Shabtay Dvir Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer-Sheva, Israel aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/4(2011-08-01), 335-350 1094-6136 14:4<335 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer